mersenneforum.org Sums of all Squares
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-14, 18:07 #144 lavalamp     Oct 2007 Manchester, UK 24758 Posts Ah, I snagged the stable binary for windows, I guess there's only a 32 bit version for that. I would quite like a forbigprime loop. Are you saying then that while 64bit pari can generate more primes, you can't use them in a regular forprime loop? Incidentally, do you know why the limit is 4,294,965,247 and not 4,294,967,295? Those last 93 primes before 2^32-1 could be vitally important!
2010-12-14, 19:54   #145
CRGreathouse

Aug 2006

2×29×103 Posts

Quote:
 Originally Posted by lavalamp Ah, I snagged the stable binary for windows, I guess there's only a 32 bit version for that.
Right. The mingw project that the Windows version of Pari/GP is built on is strictly 32-bit. There is a mingw64 fork, but the last time I used it there were serious problems with it. I've heard that it's better now, but I haven't tried recently.

Quote:
 Originally Posted by lavalamp Are you saying then that while 64bit pari can generate more primes, you can't use them in a regular forprime loop?
No, forprime can go as high as primelimit, and 64-bit Pari can handle more primes than you could fit in memory. I did the calculations up to 10^10 using forprime normally.

But it would often be convenient to loop over more primes than you can fit in memory. For example, there's no way I could fit the primes to 10^12 in memory, but I'd like to check the conjecture up to that point.

Quote:
 Originally Posted by lavalamp Incidentally, do you know why the limit is 4,294,965,247 and not 4,294,967,295? Those last 93 primes before 2^32-1 could be vitally important!
The implementation leaves free space of about 2000, as I recall, so there is room for status and whatnot in the word.

2010-12-14, 20:11   #146
CRGreathouse

Aug 2006

2×29×103 Posts

Quote:
 Originally Posted by lavalamp I would quite like a forbigprime loop.
Likewise -- I wanted one enough that I sat down and wrote one. But there are still fencepost errors, and also a few things I'd like to optimize before I send it out.

The version I have right now is reasonably efficient for long intervals (forprime(p=a,b, ...) with b - a >> sqrt(b) or so) but inefficient for small intervals. It would be very easy to write a function to handle short intervals (sieve out tiny primes then test with ispseudoprime), so I might break the code into four parts:

forprime
forbigprime
forsmallprime
forthinprime

where the existing forprime would move to forsmallprime, the new code would go into forbigprime (and maybe also new code in forbigprime_word*), forthinprime would be the near-trivial code for handling short intervals, and forprime would handle errors and decide which function to use.

I don't think these would be exposed to GP; it would probably be best to let users remain ignorant of the different workings. There are some sticking points, though.

First, it's usually good to warn the user if they try to exceed primelimit. If you want to loop over the primes up to 100 million, just calculate those primes, don't use forbigprime (which, by its nature, will be slower) and then throw them away!

Second, forprime currently allows code like
Code:
forprime(p=2,100,print1(p" ");if(p==3,p=80))
which changes the index midstream. My current version of bigprime doesn't handle this, and it would be very inefficient if it did.

One possibility would be to use a different function ("forbigprime") in GP, so users only use the appropriate function. This takes care of the above issues, but exposes more complexity to the user than is desirable.

Another would be to allow the index to change with forbigprime, but if it does just kick them into forthinprime.

Another would be to disallow changing the index entirely.

* which would handle cases where the upper limit is larger than primelimit but not larger than a word -- 2^32-1 or 2^64-1 on 32- and 64-bit, respectively.

 2010-12-14, 21:00 #147 lavalamp     Oct 2007 Manchester, UK 32·149 Posts This program is for use (ideally) by people who already know what they're doing, I don't see why these specific loops would need to be hidden. On a personal note, I would prefer knowing what code is going to do when I run it, rather than be unsure because I don't happen to know the current primelimit. It would be possible to get the best of both worlds though, have a generic loop that can call whichever loop seems most appropriate, and the numerous specific loops for people who already know what they want, it only takes a few lines in the documentation. If there's no way (or it is at least very hard) to make the forbigprime loop efficient AND able to jump around with the index, then it seems reasonable to deny the ability to change it, for that loop only.
2010-12-14, 21:04   #148
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by CRGreathouse Likewise -- I wanted one enough that I sat down and wrote one. But there are still fencepost errors, and also a few things I'd like to optimize before I send it out. The version I have right now is reasonably efficient for long intervals (forprime(p=a,b, ...) with b - a >> sqrt(b) or so) but inefficient for small intervals. It would be very easy to write a function to handle short intervals (sieve out tiny primes then test with ispseudoprime), so I might break the code into four parts: forprime forbigprime forsmallprime forthinprime where the existing forprime would move to forsmallprime, the new code would go into forbigprime (and maybe also new code in forbigprime_word*), forthinprime would be the near-trivial code for handling short intervals, and forprime would handle errors and decide which function to use. I don't think these would be exposed to GP; it would probably be best to let users remain ignorant of the different workings. There are some sticking points, though. First, it's usually good to warn the user if they try to exceed primelimit. If you want to loop over the primes up to 100 million, just calculate those primes, don't use forbigprime (which, by its nature, will be slower) and then throw them away! Second, forprime currently allows code like Code: forprime(p=2,100,print1(p" ");if(p==3,p=80)) which changes the index midstream. My current version of bigprime doesn't handle this, and it would be very inefficient if it did. One possibility would be to use a different function ("forbigprime") in GP, so users only use the appropriate function. This takes care of the above issues, but exposes more complexity to the user than is desirable. Another would be to allow the index to change with forbigprime, but if it does just kick them into forthinprime. Another would be to disallow changing the index entirely. * which would handle cases where the upper limit is larger than primelimit but not larger than a word -- 2^32-1 or 2^64-1 on 32- and 64-bit, respectively.
if theres a easy formula for calculating the distance between primes that doesn't use a random n in 6n I could see a way to extend it the way it is, but using a shift in vectors.

 2010-12-14, 21:20 #149 lavalamp     Oct 2007 Manchester, UK 32·149 Posts Well, not exactly, but sort of: http://primes.utm.edu/notes/gaps.html Trivia: this is where god lives.
2010-12-14, 21:37   #150
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by lavalamp Well, not exactly, but sort of: http://primes.utm.edu/notes/gaps.html Trivia: this is where god lives.
well I've drowned lol.

 2010-12-14, 21:48 #151 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26×131 Posts given primes p and q
2010-12-14, 21:49   #152
lavalamp

Oct 2007
Manchester, UK

32·149 Posts

Perhaps this then:
http://www.ieeta.pt/~tos/gaps.html

While you're at it could you explain what this means:
Quote:
 Originally Posted by science_man_88 if theres a easy formula for calculating the distance between primes that doesn't use a random n in 6n I could see a way to extend it the way it is, but using a shift in vectors.

2010-12-14, 21:52   #153
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by lavalamp Perhaps this then: http://www.ieeta.pt/~tos/gaps.html While you're at it could you explain what this means:
I think I was thinking to find 6n+1 primes from a 6n+1 prime guessing random numbers that are multiples of 6.

Last fiddled with by science_man_88 on 2010-12-14 at 21:54

2010-12-14, 21:54   #154
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by science_man_88 given primes p and q
I forgot to mention p^2-q^2 can be made into 2* (the sum of the numbers (q-p)) -(p+q)

 Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 42 2017-02-03 01:29 Nick Number Theory Discussion Group 0 2016-12-11 11:30 3.14159 Miscellaneous Math 12 2010-07-21 11:47 CRGreathouse Math 6 2009-11-06 19:20 m_f_h Puzzles 45 2007-06-15 17:46

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

Fri Mar 5 20:39:52 UTC 2021 up 92 days, 16:51, 0 users, load averages: 1.68, 2.25, 2.78