mersenneforum.org  

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

Reply
 
Thread Tools
Old 2015-06-15, 13:00   #1
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3·54 Posts
Default Using PFGW and NewPGen

Apologies to all for posting such a naïve request, but I have started to play with "Maxima" software, and I am really struggling to produce a simple but effective program that will manage large quantities of cnewpgen output data and provide limited output of large gaps between those primes.

My main purpose is to look at selected integer ranges of a size between 10^20 and 10^21 which fall between the gapcoin search and the systematic search for prime gaps in the 10^18 range. Cnewpgen allows for example special forms b^n+2k with fixed b and n and variable k (for example b=7, n=24, and then sieving a range up to, in this instance, about 7^12.

The data produced in any cnewpgen output is huge but slightly awkward in that the output is not in the form of gaps but the values of k and n. This means first that extraneous and irrelevant data in the cnewpgen output must be stripped and the gaps computed efficiently. Then the vast majority of those gaps can be discarded, to keep only those that are above a certain size, which are then output to a results file.

The whole process somehow needs to be batch mechanised to allow very large ranges to be checked, and efficient in the use of memory.

So far I have managed to play around with Maxima to output a small file with the largest gaps based on an input of a relatively small cnewpgen output file. I can also mechanise the cnewpgen process to provide output files for ranges with different file names. However, my Maxima program is highly inefficient, because it orders all of the prime gaps instead of just selecting those over a certain size and keeping those. I also lose the link to the specific k to which the gap applies. Finally, I can't see how you can write code that allows you to control cnewpgen from within Maxima, which is probably important for any mechanisation. I can't seem to write a for loop that identifies the data input. I also fear that I will be building enormous stacks that might crash my machine.

Why Maxima? - I work in the Windows environment and I have never been successful in working with PARI/GP or other free maths software for example.

Ideally it would be cute to have a windows 64 executable that would allow for a painless input that others could also use in some small project. .


I'm sure this is not the most efficient way of carrying out an exercise but the reason I am doing this is to provide myself and others with a recreational tool that might provide some record gaps.
robert44444uk is offline   Reply With Quote
Old 2015-06-15, 19:51   #2
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

17·53 Posts
Default

I run my software on my Windows machine, and just started annoying my kids with putting it on their Win7 and Win8 boxes. Strawberry Perl has everything I use barring the script itself, which is about 20-30 lines, so it involved just running that .msi then running the Perl script. It pulls in the merits file so we only output new gaps, then loops through "appropriate" values doing a prev_prime and next_prime and seeing what the gap is. If large enough, it calculates merit and outputs text if it found a winner. Of course the fun work is in the prev_prime and next_prime implementations, which are faster than Pari/GP.

There's also the infrastructure to collect the output from the various output files, combine them, then produce the new gap file with only the winning gaps (no duplicates, no gaps smaller than the latest merits file, etc.).

If you don't care about the special forms, there are better ways using partial sieves (also in the module).
danaj is offline   Reply With Quote
Old 2015-06-16, 16:12   #3
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default

Thank you Danaj for your hints on this, especially on what works well in the Windows environment. If you want to share your code, I would be very happy to see whether I could adapt it for my purposes.

I am curious though about the use of "next_prime" - I can't see how this can be efficient compared to cnewpgen which can produce 20MB of primes (I weigh them rather than count them) in a matter of a couple of minutes at the 10^20 level, through sieving a suitable range up to the square root. My problem is therefore how to handle this information efficiently.
robert44444uk is offline   Reply With Quote
Old 2015-06-16, 22:49   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38516 Posts
Default

I'll post some code when I'm home. As for next_prime, I'm looking for k*n#/X-Y as the start, rather than generating large swathes of arbitrary numbers like GapCoin does. Given a k*n#/X, prev_prime gives me Y as the start and next_prime gives me the gap length. The three Win7 and Win8 boxes are finding 100-150 record gaps a day at the moment, while they are also used for playing games. I believe that's more than gapcoin is finding, though the ranges and methods are different. Gapcoin certainly is finding more merits > 30.

NewPGen would presumably be more efficient, but I'd have to check with an identical process. It looks like my next_prime in the 10^20 to 10^22 range takes about 22 microseconds on average, running on my Macbook. Using the completely naive method of calling gmp_printf("%Zd\n",n) for each one, it takes 25 seconds to make 24MB of primes. That seems weird that it is that much faster than cnewpgen, though we could easily be measuring different things (20MB in deltas, in binary, in ASCII, 20MB of primes involving some other search method, ...).

Using my sieve, looks like my Macbook takes 33s to generate the 1,973,279 primes after 10^22, which includes the time for partial sieve followed by BPSW. Just doing a partial sieve is about 2 seconds for 3M candidates in that range (including returning them all to Perl). If I recall correctly, JKA indicated he did some searches using something like this and then just cherry picked the already-large gaps to check edges.

My next_prime and prev_prime, in Math::Prime::Util::GMP (included in Strawberry Perl), work by doing a partial sieve to 30 merits followed by BPSW tests of the candidates until one is found or it has to extend the range and keep searching.

I don't know about cnewpgen, but I did try some constellation searches a few months ago, and polysieve2 as shown by henryzz was insanely faster.
danaj is offline   Reply With Quote
Old 2015-06-17, 05:58   #5
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default

Hi Danaj.

I ran 7^23-2k for 2k from 2 to 100,000,000 on newpgen quickly before I went to work this morning. The output file for 4.4 million primes was generated in 53 sec. It does seem like your set up is acceptably fast though so I would love to play!

Last fiddled with by robert44444uk on 2015-06-17 at 05:58
robert44444uk is offline   Reply With Quote
Old 2015-06-17, 07:41   #6
axn
 
axn's Avatar
 
Jun 2003

3×1,531 Posts
Default

The thing about NewPGen is that it can sieve _much_ larger area at about the same time.

For example, I sieved 10^20+2k-1 (k <= 4e9, i.e 10^20..10^20+8e9) range using NewPGen. It completed sieving in 3m30s (with p<=1e10), and wrote out a file with 180e6 primes in another 1:30s.

Another sieve at higher range: 10^22+2k-1 (k<=4e9) completed in 14m30s and wrote out a file with 160e6 primes.

I believe a custom program could do even better using a much larger bitmap, and not writing out the result to disk, but instead doing the gap check directly in memory. NewPGen (at least the one I have) can only handle a bitmap of 485MB at a time, so larger ranges would be split up and sieved separately.
axn is offline   Reply With Quote
Old 2015-06-21, 20:18   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

283510 Posts
Default

I created a small C program to check the logfile from cnewpgen and a bat file to run them both.

You just set Base, n and kmin in the 3 first lines in the .bat file and then run it, and it will continue to run chunks of 4 billion k's. I have not set it to delete the >2Gb files but you can add that to the .bat file in the loop.

Remember cnewpgen uses 2k so if kmin=40 (to 44) that means b^n+80e9 to b^n+88e9. I added the NewPGen.ini file because it is important to have BitmapThreshold = 4068474880 so it can sieve 4 billion k's, and it is nice that it does not save 2 save files each over 2Gb, and I set it to save every 60min only.

To stop the program you can CTRL+C during the primegap.exe run, or you can CTRL+C during the cnewpgen run and it will save sieve at the spot it reached, or you can CTRL+BREAK during newpgen to stop instantly without saving the current sieve.

Bat file:
Code:
SET /A base=10
SET /A n=22
SET /A kmin=40    :: kmin in billions
:START
SET /A kmax=%kmin%+4
SET kk=%kmin%000000000
IF %kmin%==0 SET /A kk=0
cnewpgen.exe -wp=%base%-%n%-%kmin%.txt -t=13 -base=%base% -n=%n% -kmin=%kk% -kmax=%kmax%000100000
primegap.exe %base% %n% %kmin%
SET /A kmin=%kmin%+4
goto START


Here is the sourcecode to the C program, it saves primegaps >= 1000 to primegaps.txt currently

Code:
#include <string.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main (int argc, char *argv[])
{
long a,i,base,n,k;
FILE *file,*fil;
char str[100],fstr[100];
long long knew,klast,gap,max,kk,end,k1,k2;

	base=strtol(argv[1],NULL,10);   n=strtol(argv[2],NULL,10);   k=strtol(argv[3],NULL,10);
	strcpy(str,argv[1]); strcat(str,"-"); strcat(str,argv[2]); strcat(str,"-"); strcat(str,argv[3]); strcat(str,".txt");
	file=fopen(str,"rb");
	do { a=fgetc(file); } while(a!=10);
	max=0; i=0;
	fscanf(file,"%lld",&kk); fscanf(file,"%i",&a);
	end=kk+4000090000ULL;
	klast=2*kk;
	do
	{
		i++;
		fscanf(file,"%lld",&kk); fscanf(file,"%i",&a);

		knew=kk*2;
		gap=knew-klast; if (gap>max) { max=gap; }
		if (gap>=1000)
		{
			if (base%2==0) { k1=klast-1; k2=knew-1; } else { k1=klast-2; k2=knew-2; }
			printf("\rGAP=%lld\t%i^%i+%lld to %i^%i+%lld           \n",gap,base,n,k1,base,n,k2);
			fil=fopen("primegaps.txt","ab");
			fprintf(fil,"GAP=%lld\t%i^%i+%lld to %i^%i+%lld",gap,base,n,k1,base,n,k2);
			fputc(13,fil); fputc(10,fil); fclose(fil);
		}
		klast=knew;

		if (i%1000000==0) { printf("\rk=%lld maxgap=%lld      ",kk,max); }
	} while(kk<end);
	printf("\rk=%lld maxgap=%lld      ",kk,max);
	fclose(file);

	return 0;
}
Attached Files
File Type: zip primegap.zip (102.6 KB, 75 views)

Last fiddled with by ATH on 2015-06-21 at 20:22
ATH is offline   Reply With Quote
Old 2015-06-22, 13:22   #8
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3·54 Posts
Default

Quote:
Originally Posted by ATH View Post
I created a small C program to check the logfile from cnewpgen and a bat file to run them both.
Oh wow, another new toy - thank you ATH. Lets give this a run out to see if we can generate some good small gaps.

Last fiddled with by robert44444uk on 2015-06-22 at 13:22
robert44444uk is offline   Reply With Quote
Old 2015-06-22, 17:58   #9
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default

Quote:
Originally Posted by ATH View Post
I created a small C program to check the logfile from cnewpgen and a bat file to run them both.
Oh, it did not work on my 64-bit Dell XPS 8700 Intel Core I7-4770 with 8gb physical and 32gb max memory with Windows 8.1 operating system..

Just never got started, I get an error message saying:

" a problem caused the program to stop working correctly. Windows will close the program and notify you if a solution is available. " - which it doesn't.

That's a shame. I'm not a programmer, so I have no way of knowing how to go about a fix.

As for the program itself, it would make more sense to have the minimum gap stated in the bat file and maybe the gap and its "merit" =gap/ln(b^n+2k) could be output.

But again thanks for this effort, it is key for smaller ranges and a relatively new approach.

Last fiddled with by robert44444uk on 2015-06-22 at 17:59
robert44444uk is offline   Reply With Quote
Old 2015-06-22, 18:42   #10
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3×54 Posts
Default

Quote:
Originally Posted by robert44444uk View Post

Just never got started, I get an error message saying:

" a problem caused the program to stop working correctly. Windows will close the program and notify you if a solution is available. " - which it doesn't.

.
Part of the problem was having a .bat and .exe file with the same name. I'm running the bat file now and will try the exe file after
robert44444uk is offline   Reply With Quote
Old 2015-06-22, 21:20   #11
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

3·54 Posts
Default

Quote:
Originally Posted by ATH View Post
I created a small C program to check the logfile from cnewpgen and a bat file to run them both.

Here is the sourcecode to the C program, it saves primegaps >= 1000 to primegaps.txt currently
Well the code is certainly working. I am amazed at how quickly the c program can inspect the massive cnewpgen files. Less than 1 minute. The results, because 1000 gap is set rather high means that I don't have any output to inspect and the screen output for cnewpgen is verbose so I only fleetingly saw the results for two iterations of the the primegaps program. From what I can remember the screen output shows an improving gap size and gives values of where it is up to every second. The final output that remains on the screen (largest gap) surprisingly in both instances was a very low k value - typically less than 100000 after the start of the range. The second was xxxx90038. So I went back to the c program and I see a line in there:

end=kk+4000090000ULL

I just ran it with a series I know well, 7^23 and the k from 0 to 4bn, and the screen output was 4000090024 which is the incorrect k value but the largest gap is correct.

I don't know enough about the program to know if this is related to the 100000 issue but then I think that what is happening is that the program is reading the massive file in 100000 k cycle, so the output should also have the relevant cycle number, and perhaps better still just the k. Maybe I haven't go this right. All I need is a gap of 1000 to see the file output. Maybe the output file should give the maximum for each newpgen file tested.

I tried the >> function. It gives and output of the 1/2 second updates but I am not sure these are the actual k values, just interim check points.

For 7^23, and the slowest part of the process is now newpgen trying to save the 2 gig file for testing. In 20 minutes it produced two gaps of merit >20 which is the benchmark for breakthrough, given that every additional 1 in the value of merit means a doubling of time that would be a 30 merit once a week. I can firm up on these numbers once I get some output for analysis. Maybe the 20 merits were a fluke.

I don't suppose there is a way to pipe the file being created straight to the c program? That way there would be no need to save the monster file at all.

But my word it seems jolly fast to me. I do take Danaj's point though - needle in a haystack and all of that. But when you see the first spiky graph above, the whole shebang falls off rapidly past the ToES values, and back into the realms of rapid possible improvement in some of the merits for the low 1500-1600 gaps.

Hah, and between Bill Gates and Mr Dell, they have managed to sell me a keyboard and software system without CNTRL BREAK !!!!!

Last fiddled with by robert44444uk on 2015-06-22 at 22:12
robert44444uk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
NewPgen Cybertronic Factoring 0 2014-03-22 10:07
NewPgen question pepi37 Software 12 2013-12-25 18:59
PFGW 3.3.6 or PFGW 3.4.2 Please update now! Joe O Sierpinski/Riesel Base 5 5 2010-09-30 14:07
Does NewPGen have a bug? MooooMoo Riesel Prime Search 16 2008-12-11 11:46
Linux newpgen pfgw llr jasong Linux 10 2008-02-16 23:55

All times are UTC. The time now is 20:38.

Tue Jun 2 20:38:32 UTC 2020 up 69 days, 18:11, 2 users, load averages: 1.58, 1.52, 1.61

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.