mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2010-12-14, 18:07   #144
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

24758 Posts
Default

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!
lavalamp is online now   Reply With Quote
Old 2010-12-14, 19:54   #145
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×29×103 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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 View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-14, 20:11   #146
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×29×103 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-14, 21:00   #147
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

32·149 Posts
Default

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.
lavalamp is online now   Reply With Quote
Old 2010-12-14, 21:04   #148
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2010-12-14, 21:20   #149
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

32·149 Posts
Default

Well, not exactly, but sort of:
http://primes.utm.edu/notes/gaps.html

Trivia: this is where god lives.
lavalamp is online now   Reply With Quote
Old 2010-12-14, 21:37   #150
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by lavalamp View Post
Well, not exactly, but sort of:
http://primes.utm.edu/notes/gaps.html

Trivia: this is where god lives.
well I've drowned lol.
science_man_88 is offline   Reply With Quote
Old 2010-12-14, 21:48   #151
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

given primes p and q<p we can show that the composites ruled out are q%((p^2-q^2)%q) mod q above p^2. but i can't take this any further.
science_man_88 is offline   Reply With Quote
Old 2010-12-14, 21:49   #152
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

32·149 Posts
Default

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 View Post
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.
lavalamp is online now   Reply With Quote
Old 2010-12-14, 21:52   #153
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by lavalamp View Post
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
science_man_88 is offline   Reply With Quote
Old 2010-12-14, 21:54   #154
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
given primes p and q<p we can show that the composites ruled out are q%((p^2-q^2)%q) mod q above p^2. but i can't take this any further.
I forgot to mention p^2-q^2 can be made into 2* (the sum of the numbers (q-p)) -(p+q)
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Regarding Squares a1call Miscellaneous Math 42 2017-02-03 01:29
Basic Number Theory 12: sums of two squares Nick Number Theory Discussion Group 0 2016-12-11 11:30
Integers = sums of 2s and 3s. 3.14159 Miscellaneous Math 12 2010-07-21 11:47
Sums of three squares CRGreathouse Math 6 2009-11-06 19:20
squares or not squares 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

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.