Thread: Pari/GP to PFGW View Single Post
2017-12-21, 06:04   #7
CRGreathouse

Aug 2006

32·5·7·19 Posts

Quote:
 Originally Posted by danaj 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
Code:
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.

Quote:
 Originally Posted by danaj 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.