mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2018-06-28, 08:01   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

190310 Posts
Default 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
robert44444uk is offline   Reply With Quote
Old 2018-06-28, 16:38   #2
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

3·5·383 Posts
Default

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?
henryzz is offline   Reply With Quote
Old 2018-06-29, 05:31   #3
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

10000110002 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
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 ?
ldesnogu is offline   Reply With Quote
Old 2018-06-30, 07:03   #4
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

11×173 Posts
Default

Quote:
Originally Posted by ldesnogu View Post
Isn't the source code rather found here: http://www.mersenneforum.org/showpos...&postcount=141 ?
Ahh, yes it is! Sorry about that.
robert44444uk is offline   Reply With Quote
Old 2018-07-01, 11:46   #5
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

2×32×11 Posts
Default

We should change the 64-bit integers to 128-bit integers. Then, we can go up to 2128.
Bobby Jacobs is offline   Reply With Quote
Old 2018-08-17, 23:36   #6
rudy235
 
rudy235's Avatar
 
Jun 2015
Vallejo, CA/.

967 Posts
Default

Quote:
Originally Posted by Bobby Jacobs View Post
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
rudy235 is online now   Reply With Quote
Old 2018-08-18, 22:23   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by rudy235 View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2018-08-19, 01:00   #8
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011101000112 Posts
Default

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 <stdio.h>
#include <inttypes.h>

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
ATH is offline   Reply With Quote
Old 2018-08-19, 08:23   #9
Thomas11
 
Thomas11's Avatar
 
Feb 2003

1,907 Posts
Default

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...
Thomas11 is offline   Reply With Quote
Old 2018-08-25, 12:17   #10
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

101001100002 Posts
Default

Quote:
Originally Posted by ATH View Post
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));
preda is offline   Reply With Quote
Old 2018-09-19, 19:13   #11
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

2×32×11 Posts
Default

When are we going to continue our search beyond 264?
Bobby Jacobs is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Anyone know enough about coding to do this? jrafanelli Software 2 2018-01-11 15:16
Python Coding Help? kelzo Programming 3 2016-11-27 05:16
Zhang's OPQBT coding help? flouran Programming 0 2009-07-25 02:43
coding midlet for TF starrynte Programming 1 2008-12-30 22:31
Coding Challenges 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

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.