Thread: Pari/GP to PFGW
View Single Post
Old 2017-12-21, 06:04   #7
CRGreathouse's Avatar
Aug 2006

32·5·7·19 Posts

Originally Posted by danaj View Post
Pari/GP's fibonacci() is pretty basic. Does Mod(fibonacci(n),p) optimize? It seems unlikely.
No, and it couldn't -- order of operations forces fibonacci(n) to be computed in full before reducing it mod p.

I use
fibmod(n, m)=((Mod([1, 1; 1, 0], m))^n)[1, 2]
which works decently. I have a version in C, nothing special, which is faster.

Originally Posted by danaj View Post
Connecting to another thread on Lucas sequences, I saw the nice OEISWiki page. Are there some good Pari/GP functions for lucasu(P,Q,n) and lucasv(P,Q,n) possibly with n = Mod(x,y)? Good in the sense of either (or both) (1) clean, (2) fast?

It looks like maybe polcoef could do it. Not sure about efficiently handling the modulo case though.
I'll look into it tomorrow. I don't think that signature will work, though; just because you're working mod m doesn't mean you can reduce the index mod m, right? So I think you'll need separate arguments for those two.
CRGreathouse is offline   Reply With Quote