mersenneforum.org Coding request for 2^64 up
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2018-06-28, 08:01 #1 robert44444uk     Jun 2003 Oxford, UK 190310 Posts Coding request for 2^64 up I am wondering if there is anyone out there who could recode our software to enable us to search for prime gaps larger than 2^64. The current version of the software is here: http://www.mersenneforum.org/showpos...&postcount=150
 2018-06-28, 16:38 #2 henryzz Just call me Henry     "David" Sep 2007 Cambridge (GMT/BST) 3·5·383 Posts It might be worth getting the modular exponentiation right first as that is probably the hardest bit to get fast. What percent of the 64-bit runtime was the prp tests?
2018-06-29, 05:31   #3
ldesnogu

Jan 2008
France

10000110002 Posts

Quote:
 Originally Posted by robert44444uk I am wondering if there is anyone out there who could recode our software to enable us to search for prime gaps larger than 2^64. The current version of the software is here: http://www.mersenneforum.org/showpos...&postcount=150
Isn't the source code rather found here: http://www.mersenneforum.org/showpos...&postcount=141 ?

2018-06-30, 07:03   #4
robert44444uk

Jun 2003
Oxford, UK

11×173 Posts

Quote:
 Originally Posted by ldesnogu Isn't the source code rather found here: http://www.mersenneforum.org/showpos...&postcount=141 ?
Ahh, yes it is! Sorry about that.

 2018-07-01, 11:46 #5 Bobby Jacobs     May 2018 2×32×11 Posts We should change the 64-bit integers to 128-bit integers. Then, we can go up to 2128.
2018-08-17, 23:36   #6
rudy235

Jun 2015
Vallejo, CA/.

967 Posts

Quote:
 Originally Posted by Bobby Jacobs We should change the 64-bit integers to 128-bit integers. Then, we can go up to 2128.
I really don't believe it is that easy. If it were then it would have already been done.

Speaking as a layperson in coding, I can only assume that while technically possible to recode to go up to 2^65 (thats' all that is needed really) it is not an easy task and it will require perhaps 50-100 hours of coding time.

I believe it is well worth it. Even at 1/10 the efficiency of the last coding we could get perhaps 7e9 n/sec and that would be enought to find one or two new Maximal Gaps and lift the Unknown first occurrence gaps to 1450.

If I knew how to program I would certainly do it myself.

Last fiddled with by rudy235 on 2018-08-17 at 23:42

2018-08-18, 22:23   #7
CRGreathouse

Aug 2006

2·2,969 Posts

Quote:
 Originally Posted by rudy235 I really don't believe it is that easy. If it were then it would have already been done. Speaking as a layperson in coding, I can only assume that while technically possible to recode to go up to 2^65 (thats' all that is needed really) it is not an easy task and it will require perhaps 50-100 hours of coding time.
That sounds like a reasonable first estimate. It certainly won't take any less effort.

Quote:
 Originally Posted by rudy235 I believe it is well worth it. Even at 1/10 the efficiency of the last coding we could get perhaps 7e9 n/sec and that would be enought to find one or two new Maximal Gaps and lift the Unknown first occurrence gaps to 1450.
1/10 would be harsh. I expect more like 1/4 and hope for something like 1/2. But until someone takes a serious look at the code and what would be required we won't know. I'm unfortunately not available at present.

 2018-08-19, 01:00 #8 ATH Einyen     Dec 2003 Denmark 1011101000112 Posts There is actually a 128 bit variable. It works for me in MSYS2 with G++ 7.3.0: __uint128_t and __int128_t Calculation seems pretty fast with them, but the problem is there is no way to print the result with printf. You have to print 1 character at the time, for example using a recursive function. But I guess you could minimize how often to output 128 bit variables. I have not tried to print negative values with the signed __int128_t . Code: #include #include void print_uint128(__uint128_t n) { if (n == 0) { return; } print_uint128(n/10); putchar(n%10+0x30); } int main(void) { __uint128_t a,b,c; a=(__uint128_t)9223372036854775808ULL; // 2^63 b=a*a*2-1; // 2*2^63*2^63-1 print_uint128(b); printf("\n"); } Output: 170141183460469231731687303715884105727 which is 2^127-1 I will try to change one of my programs to use these variables to see if they are useful, but not right now at 3am. Looking at gap12.c is daunting for me, as I have no idea how the 1900+ lines of code works, but maybe some of you who worked on it could change it to use these 128 bit variables? Last fiddled with by ATH on 2018-08-19 at 01:04
 2018-08-19, 08:23 #9 Thomas11     Feb 2003 1,907 Posts A non-recursive algorithm for a 128 bit printf is given here. But the crucial part would be to find efficient 128 bit (or at least 65 bit) replacements for mulmod / powmod. And extending the segmented sieve (bit buckets) to more than 64 bits might also be tricky...
2018-08-25, 12:17   #10
preda

"Mihai Preda"
Apr 2015

101001100002 Posts

Quote:
 Originally Posted by ATH There is actually a 128 bit variable. It works for me in MSYS2 with G++ 7.3.0: __uint128_t and __int128_t Calculation seems pretty fast with them, but the problem is there is no way to print the result with printf. You have to print 1 character at the time, for example using a recursive function. But I guess you could minimize how often to output 128 bit variables.
If you don't mind printing in hex instead of decimal, you could print 128 bit as two 64-bit values, e.g.:
Code:
printf("%16llx%016llx\n", (unsigned long long) (x >> 64), (unsigned long long) (x));

 2018-09-19, 19:13 #11 Bobby Jacobs     May 2018 2×32×11 Posts When are we going to continue our search beyond 264?

 Similar Threads Thread Thread Starter Forum Replies Last Post jrafanelli Software 2 2018-01-11 15:16 kelzo Programming 3 2016-11-27 05:16 flouran Programming 0 2009-07-25 02:43 starrynte Programming 1 2008-12-30 22:31 R.D. Silverman Programming 18 2005-08-09 13:14

All times are UTC. The time now is 00:22.

Thu Nov 26 00:22:33 UTC 2020 up 76 days, 21:33, 3 users, load averages: 1.36, 1.20, 1.27