20171220, 23:59  #1 
"Sam"
Nov 2016
2^{2}×3^{4} Posts 
Pari/GP to PFGW
Hi,
The following code is to generate prime indices of prime Fibonacci numbers in GP in a certain index range. Code:
v=[3, 4]; forprime(p=5, 1e5, if(ispseudoprime(fibonacci(p)), v=concat(v, p))); Code:
v=[]; forprime(p=1, 1e5, if(ispseudoprime(a(p)), v=concat(v, p))); Now the bad thing or catch about this is PARI's pseudoprime(n) function is seemingly slow if n is a (considerably large, say 1000+ digits) pseudoprime (probable prime). Since PARI/GP seems to be fast at generating the terms for a(p), (which PFGW cannot do for all sequences and highorder recurrence relations), can someone come up with a modification to fiabonacci(p) code so that PARI/GP generates the primeindex Fibonacci numbers, and PFGW 3PRP tests them. (I am aware of PFGW's builtin fibonacci function, however I don't want that being used here because if PARI is able to generate the fibonacci terms, it will also be able to for other sequences, which PFGW can easily PRP test. Thanks for help. The following GP code is from here. 
20171221, 00:17  #2  
"Forget I exist"
Jul 2009
Dumbassville
20C0_{16} Posts 
Quote:
Last fiddled with by science_man_88 on 20171221 at 01:14 

20171221, 00:58  #3 
Aug 2006
3×1,993 Posts 
PFGW is definitely faster, but the comparison is not a fair one: it's just doing a 3PRP test, while gp is doing a full BPSW test (~3x slower). A better comparison would be to use ispseudoprime(..., 1) which will perform 1 MillerRabin test with a random base.
I call PFGW within gp like so: Code:
pfgw(n:int)= { my(prog="~/mth/pfgw/pfgw64 k N u0 q"); Vecsmall(externstr(Str(prog, n))); } 
20171221, 01:50  #4 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
908_{10} Posts 
Admittedly the BPSW test should exit early for the composites. Still, PFGW will be faster on the Fermat / MR once the result hits somewhere between 2000 and 6000 digits  at least that's where it's faster than GMP's mpz_powm.
As an aside, I have an example Fibonacci prime finder in my Perl module that has a couple parallel implementations. Starting at the beginning searching for each, my timing results are 26244 seconds for Fp36 (p = 148091) on a 3930K (12 proc) 12000 seconds for Fp36 (p = 148091) on a c4.8xlarge (36 proc) 6465 seconds for Fp36 (p = 148091) on a r4.16xlarge (64 proc) Someday I'll get a big c5 for a day to benchmark. [Edit: that it not the timing for one test, but the time from starting search for all Fp until we see the output of the inorder 36th Fibonacci prime] I've tried it on a Power8 with 152 logical processors but it's a shared machine so really couldn't let it run very long, and it looks like GMP is better optimized for x8664. It's pretty simple, just running primality tests in order on each core, with the most interesting part just being making sure the results are shown in order. Last fiddled with by danaj on 20171221 at 01:51 
20171221, 02:15  #5 
"Dana Jacobsen"
Feb 2011
Bangkok, TH
2^{2}·227 Posts 
Thanks for the Pari/GP function to use PFGW. That's handy.
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. Pari/GP's fibonacci() is pretty basic. Does Mod(fibonacci(n),p) optimize? It seems unlikely. 
20171221, 02:39  #6 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
well a basic parity argument might be able to be used mod 2 for example. if both P and Q are the same parity that results in producing certain patterns in parity in the sequence. at least if I understand this request correctly.

20171221, 06:04  #7  
Aug 2006
3×1,993 Posts 
Quote:
I use Code:
fibmod(n, m)=((Mod([1, 1; 1, 0], m))^n)[1, 2] Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
LLL in GP/Pari  paul0  Programming  2  20151117 13:04 
PARI vs GAP  skan  Miscellaneous Math  0  20121216 00:13 
pari  devarajkandadai  Programming  21  20120831 18:08 
PFGW 3.3.6 or PFGW 3.4.2 Please update now!  Joe O  Sierpinski/Riesel Base 5  5  20100930 14:07 
64bit Pari?  CRGreathouse  Software  2  20090313 04:22 