mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2021-10-29, 10:51   #12
Dobri
 
"刀-比-日"
May 2018

2×7×17 Posts
Default

Quote:
Originally Posted by Batalov View Post
That's not good, calling a double function, and casting? why (long int)? Maybe (long long int)?
How about simply
Code:
Mp=(1ULL<<p)-1;
And where are the obligatory exits for the natural limitations of this trivial method?
Hint:
Code:
if(p>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'.
Dobri is offline   Reply With Quote
Old 2021-10-29, 13:47   #13
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×29×59 Posts
Default

Quote:
Originally Posted by Dobri View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2021-10-29, 13:57   #14
Dobri
 
"刀-比-日"
May 2018

2·7·17 Posts
Default

Quote:
Originally Posted by Dobri View Post
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.
Dobri is offline   Reply With Quote
Old 2021-10-29, 14:25   #15
Dobri
 
"刀-比-日"
May 2018

3568 Posts
Default

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.
Dobri is offline   Reply With Quote
Old 2021-10-29, 23:54   #16
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

2·23·137 Posts
Default

Quote:
Originally Posted by Dobri View Post
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
retina is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Gaussian-Mersenne & Eisenstein-Mersenne primes siegert81 Math 2 2011-09-19 17:36
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
Mersenne Wiki: Improving the mersenne primes web site by FOSS methods 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.