Pari/GP to PFGW

[carpetpool]

Hi,

The following code is to generate prime indices of prime Fibonacci numbers in GP in a certain index range.

v=[3, 4]; forprime(p=5, 1e5, if(ispseudoprime(fibonacci(p)), v=concat(v, p)));

I find this code very useful for when the fibonacci(p) sequence is replaced by another divisiblity sequence a(p) (defined in GP).

v=[]; forprime(p=1, 1e5, if(ispseudoprime(a(p)), v=concat(v, p)));

which will list the primes p such that a(p) is prime for (p given in a certain range).

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 high-order recurrence relations), can someone come up with a modification to fiabonacci(p) code so that PARI/GP generates the prime-index Fibonacci numbers, and PFGW 3-PRP tests them. (I am aware of PFGW's built-in 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.

[science_man_88]

Originally Posted by carpetpool

Hi,

The following code is to generate prime indices of prime Fibonacci numbers in GP in a certain index range.

v=[3, 4]; forprime(p=5, 1e5, if(ispseudoprime(fibonacci(p)), v=concat(v, p)));

I find this code very useful for when the fibonacci(p) sequence is replaced by another divisiblity sequence a(p) (defined in GP).

v=[]; forprime(p=1, 1e5, if(ispseudoprime(a(p)), v=concat(v, p)));

which will list the primes p such that a(p) is prime for (p given in a certain range).

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 high-order recurrence relations), can someone come up with a modification to fiabonacci(p) code so that PARI/GP generates the prime-index Fibonacci numbers, and PFGW 3-PRP tests them. (I am aware of PFGW's built-in 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.

technically, the new PARI 2.10.0 alpha ( or the newest one I have) has a fibonacci command. maybe test other conditions to weed things out a bit first ? programming efficiently relates to testing conditions that are faster first and only going for the big ones later. maybe try changing the flag to change the test being used behind the scenes ? edit: two edits to your first code made a small speed up ( changed to parforprime and called the fibonacci outside the ispseudoprime test part in parallel).

[CRGreathouse]

PFGW is definitely faster, but the comparison is not a fair one: it's just doing a 3-PRP test, while gp is doing a full BPSW test (~3x slower). A better comparison would be to use ispseudoprime(..., 1) which will perform 1 Miller-Rabin test with a random base.

I call PFGW within gp like so:

pfgw(n:int)=
{
	my(prog="~/mth/pfgw/pfgw64 -k -N -u0 -q");
	Vecsmall(externstr(Str(prog, n)));
}

and you may also find the extern and system commands useful.

[danaj]

Admittedly the BPSW test should exit early for the composites. Still, PFGW will be faster on the Fermat / M-R 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 in-order 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 x86-64.

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.

[danaj]

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.

[science_man_88]

Originally Posted by danaj

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?

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.

[CRGreathouse]

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

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

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.