mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2018-12-27, 16:52   #45
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Default

Here is 2-selfridge Baillie-PSW code:
Attached Files
File Type: c bpsw-2.c (4.3 KB, 73 views)

Last fiddled with by paulunderwood on 2018-12-27 at 17:17
paulunderwood is offline   Reply With Quote
Old 2018-12-28, 15:36   #46
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0716 Posts
Default

I have tidied all programs. I also fixed a problem with factorial primes/PRPs where a suitable jacobi symbols could not be found.

s2: (x+2)^(n+1) == 5+2*a (mod n, x^2-a*x+1) where a minimal such that jacobi(a^2-4,n) == -1.

lucasPRP: x^(n+1) == 1 (mod n, x^2-a*x+1) where minimal a>2 such that jacobi(a^2-4,n) == -1.

hybrid: as "s2" for a=0 or a=1 and otherwise (x+1)^(n+1) = 2+a (mod n, x^2-a*x+1) where minimal a>2 such that jacobi(a^2-4,n) == -1,

fusion: as "hybrid" except tests (2*x)^((n+1)/2) == jacobi(2*(a+2),n)*2 (mod m, x^2-a*x+1) for a>2 such that jacobi(a^2-4,n) == -1

bpsw-2: (2*x)^((n+1)/2) == jacobi(2*(a+2),n)*2 (mod n, x^2-a*x+1) for minimal a>2 such that jacobi(a^2-4,n) == -1
Attached Files
File Type: c s2.c (5.8 KB, 81 views)
File Type: c lucasPRP.c (3.8 KB, 82 views)
File Type: c hybrid.c (5.9 KB, 80 views)
File Type: c fusion.c (6.3 KB, 75 views)
File Type: c bpsw-2.c (4.5 KB, 80 views)

Last fiddled with by paulunderwood on 2018-12-28 at 15:56
paulunderwood is offline   Reply With Quote
Old 2018-12-30, 06:58   #47
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×23×29 Posts
Default

Below is the result of not using threads for this size of number. Obviously, I should test the input size to set the number of threads.

4 threads:
Code:
time ./pfgw64 -k -f0 -od -q'39924*10^30000+3*2^99654+455' | ../../coding/gwnum/prp2 -

Is 2-PRP!

real	0m17.745s
user	0m33.124s
sys	0m13.808s
1 thread:
Code:
time ./pfgw64 -k -f0 -od -q'39924*10^30000+3*2^99654+455' | ../../coding/gwnum/prp2 -
                                       
Is 2-PRP!

real	0m11.615s
user	0m11.776s
sys	0m0.004s
So I have done this to all of my programs, not knowing the sweet spot:

Code:
if (LEN > 1000000) gwset_num_threads ( gwdata, 4 );

Last fiddled with by paulunderwood on 2018-12-30 at 07:39
paulunderwood is offline   Reply With Quote
Old 2019-02-04, 20:10   #48
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Default Array Arithmetic

Although what I present here may not be applicable to GWNUM, it is useful where one has to construct one's own arbitrary arithmetic using arrays.

Let w be 2^64 in 64bit machines, be 2^54 in JavaScript etc. Find minimal r>0 such that jacobiSymbol(w^(2*r)-4,n)==-1 where n is the prime candidate. Then test:

(w*x)^((n+1)/2)==w*kronecker(w^r+2,n) (mod n, x^2-w^r*x+1)

Intermediate calculations in the left to right binary exponentiation are then:

Squaring: (s*x + t)^2 --> s*(w^r*s + 2*t)*x + (t - s)*(t + s) (mod n)

Multiplying by the base: (s*x + t)*w*x --> (w^(r + 1)*s + w*t)*x - w*s (mod n)

With some simple manipulation of array indices, this should be quite quick. I would be impressed by someone if they implemented this.

Last fiddled with by paulunderwood on 2019-02-04 at 20:44
paulunderwood is offline   Reply With Quote
Old 2019-02-05, 02:18   #49
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0716 Posts
Default

On second thoughts, a large "r" could really balloon the modular reductions in the above. However if w=2 and the test is:

(2*x)^((n+1)/2) == 2*jacobi(2*(2^r+2)) (mod n, x^2-2^r*x+1)

then the squaring part would be:

(s*x+t)^2 --> s*(s<<r+t<<1)*x + (t-s)*(t+s) mod n,

thus saving a multiplication (by "a") in favour of shifts by "r". I don't think that there would be too much excess to modularly reduce most of the time. A similar situation arises for multiplication by the base, 2*x:

(s*x+t)*2*x --> (s<<(r+1)+t<<1)*x - s<<1 mod n.

Last fiddled with by paulunderwood on 2019-02-05 at 02:27
paulunderwood is offline   Reply With Quote
Old 2019-05-08, 15:43   #50
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

D0716 Posts
Default

During left to right binary exponentiation of S*x+T to a power over x^2+1, the square of the intermediate value s*x+t is 2*s*t*x+t^2-s^2.

My question is about FFT. Is it quicker to do 2 forward FFTs, 3 convolutions, and 3 reverse FFTs than it is to do 4 forward FFTs, 2 convolutions and 2 reverse FFTs? Or, to put it another way, is it better to compute the difference of squares in this case?

Last fiddled with by paulunderwood on 2019-05-08 at 16:30
paulunderwood is offline   Reply With Quote
Old 2019-05-08, 19:38   #51
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·13·53 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
During left to right binary exponentiation of S*x+T to a power over x^2+1, the square of the intermediate value s*x+t is 2*s*t*x+t^2-s^2.

My question is about FFT. Is it quicker to do 2 forward FFTs, 3 convolutions, and 3 reverse FFTs than it is to do 4 forward FFTs, 2 convolutions and 2 reverse FFTs? Or, to put it another way, is it better to compute the difference of squares in this case?
Why not:
t^2-s^2=(t-s)*(t+s)
and also note that (t-s)+(t+s)=2*t, but you'd loss in precision if you calculate one transform with this.
R. Gerbicz is offline   Reply With Quote
Old 2019-05-08, 20:01   #52
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·13·53 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
Why not:
t^2-s^2=(t-s)*(t+s)
and also note that (t-s)+(t+s)=2*t, but you'd loss in precision if you calculate one transform with this.
And ofcourse (t+s)-(t-s)=2*s !!!
But you could do this also using the transforms of s,t to get t+s,t-s.
R. Gerbicz is offline   Reply With Quote
Old 2019-05-08, 20:21   #53
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
And ofcourse (t+s)-(t-s)=2*s !!!
But you could do this also using the transforms of s,t to get t+s,t-s.
Answering my own question: It is quicker to go down the (t-s)*(t+s) route I conclude after running my own tests. It seems that forward and inverse FFTs need less computation than point-wise multiplication.

Last fiddled with by paulunderwood on 2019-05-08 at 20:50
paulunderwood is offline   Reply With Quote
Old 2020-07-31, 11:03   #54
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5·23·29 Posts
Arrow

Here is a gwnum program that tests Euler+Frobenius as per https://mersenneforum.org/showpost.p...6&postcount=74.

power_quadratic.c tests over x^2-2*x-2^s which arguably safer than quadratic.c (x^2-2*x-b).
Attached Files
File Type: c quadratic.c (4.7 KB, 9 views)
File Type: c power_quadratic.c (5.4 KB, 4 views)

Last fiddled with by paulunderwood on 2020-08-04 at 20:10
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
LLR V3.8.2 using gwnum 26.2 is available! Jean Penné Software 25 2010-11-01 15:18
GWNUM? Unregistered Information & Answers 3 2010-09-12 19:52
GWNUM library and llr leizhoucn Programming 2 2007-11-05 09:34
Compiling GMP-ECM With GWNUM tmorrow GMP-ECM 5 2007-04-04 00:39
GWNUM as DLL? Cyclamen Persicum Software 1 2007-01-02 20:53

All times are UTC. The time now is 06:10.

Mon Aug 10 06:10:24 UTC 2020 up 24 days, 1:57, 2 users, load averages: 1.57, 1.38, 1.36

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.