mersenneforum.org Mersenne Primes Help!!
 Register FAQ Search Today's Posts Mark Forums Read

2021-10-29, 10:51   #12
Dobri

"刀-比-日"
May 2018

2×7×17 Posts

Quote:
 Originally Posted by Batalov That's not good, calling a double function, and casting? why (long int)? Maybe (long long int)? How about simply Code: Mp=(1ULL<63) {perror("Can only handle 64-bit values, hence p must be < 64\n");exit(-1);}
Indeed, this is unprotected demo code for the OP to get some ideas and choose their own way of coding the task.
Here "long long int" is needed only when computing s*s for the prime exponent p = 19, and just "long int" is sufficient for p = 2, 3, 5, 7, 13 and 17.
The "pow" function could be avoided by using bit-by-bit operations to compute Mp by simply setting multiple bits to '1'.

2021-10-29, 13:47   #13
Dr Sardonicus

Feb 2017
Nowhere

3×29×59 Posts

Quote:
 Originally Posted by Dobri Here "long long int" is needed only when computing s*s for the prime exponent p = 19, and just "long int" is sufficient for p = 2, 3, 5, 7, 13 and 17.
Correct me if I'm wrong, but AFAIK a C long multiply will cause an integer overflow if the product is greater than 231 - 1. So if s > 215.5 then s*s will overflow. Since 17 > 15.5 I found your statement suspect.

I told Pari-GP to do the LL calculations for p = 17, flagging with a * any residues large enough to cause trouble:

EDIT: I realized that my script was a bit too mindless. I rewrote it only to flag residues r such that both r and 217 - 1 - r were large enough to cause trouble.

Code:
? b=sqrtint(2^31-1);print(b)
46340

? n=2^17-1;s=Mod(4,n);for(i=1,15,s=s^2-2;r=lift(s);if(n-b>r&&r>b,c="*",c="");print(i" "r" "c))
1 14
2 194
3 37634
4 95799
5 119121
6 66179 *
7 53645 *
8 122218
9 126220
10 70490 *
11 69559 *
12 99585
13 78221 *
14 130559
15 0

Last fiddled with by Dr Sardonicus on 2021-10-29 at 14:10 Reason: Improved script

2021-10-29, 13:57   #14
Dobri

"刀-比-日"
May 2018

2·7·17 Posts

Quote:
 Originally Posted by Dobri Here "long long int" is needed only when computing s*s for the prime exponent p = 19.
To be precise, "long long int" is also needed for the prime exponent p = 17.

 2021-10-29, 14:25 #15 Dobri   "刀-比-日" May 2018 3568 Posts Here is a hint how the LL (and PRP) computations could be made much faster for small prime exponents. The modulo operation "%" (which in essence is a division) can be replaced by multiplication and shift operations. Said multiplication+shift approach requires roughly four times less computing cycles than division. For large prime exponents, more memory would be needed. I couldn't find a discussion in the forum comparing the computation time of the FFT approach used by the prime95 app, standard modulo division, and the multiplication+shift approach. Please share a link if there is such a thread.
2021-10-29, 23:54   #16
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts

Quote:
 Originally Posted by Dobri The modulo operation "%" (which in essence is a division) can be replaced by multiplication and shift operations.
It can be even simpler with just shift and add.

But with the exponents used here all this extra code is overkill. Simple TF and done in a few (milli?)seconds.

Last fiddled with by retina on 2021-10-29 at 23:55

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 siegert81 Math 2 2011-09-19 17:36 Unregistered Information & Answers 0 2011-01-31 15:41 optim PrimeNet 13 2004-07-09 13:51

All times are UTC. The time now is 05:12.

Sun Dec 5 05:12:51 UTC 2021 up 134 days, 23:41, 0 users, load averages: 1.86, 1.72, 1.56