mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-05-10, 06:37   #12
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

22×11×223 Posts
Default

Quote:
Originally Posted by hansl View Post
Is there a formula to get the modular classes given the nth primorial?
eulerphi()

Last fiddled with by LaurV on 2019-05-10 at 06:38
LaurV is offline   Reply With Quote
Old 2019-05-10, 06:56   #13
hansl
 
hansl's Avatar
 
Apr 2019

5·41 Posts
Default

Quote:
Originally Posted by LaurV View Post
eulerphi()
Excellent! I just updated my code and results.
hansl is offline   Reply With Quote
Old 2019-05-10, 08:21   #14
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

101011000111012 Posts
Default

Quote:
Originally Posted by hansl View Post
So, what if we just store the gap between adjacent primes?

Anyways, we could extend the prime gap representation further, by splitting into ranges based on the bitsize of the maximum gaps in the range. I haven't yet attempted to estimate the size for such a scheme, but it might save a few more percent in the total size.
Huffman coding of gaps.
xilman is offline   Reply With Quote
Old 2019-05-10, 19:39   #15
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101100111002 Posts
Default

If one's aim is to support e.g. get_nth_prime(n) or "quickly enumerate all primes up to some limit"-style functionality, the way my code does this is:

1. Use a simple sieve to generate candidates not divisible by really small primes;
2. Feed surviving candidates - batches of 4-8 here tend to allow for good hiding of integer MUL latencies - to a base-2 Fermat PRP routine;
3. Do a fast lookup of the surviving candidates in a precomputed table of known base-2 Fermat pseudoprimes;
4. If a candidate does not appear in said table, it's prime.

So there's still a table involved, but it's *much* smaller than any needed for explicit prime storage. Here is the associated commentary in my code:
Code:
/* There are 10403 ( = 101*103) base-2 Fermat pseudoprimes < 2^32.
[Cf. http://home.att.net/~numericana/answer/pseudo.htm#pseudoprime for this and
other tables related to the pseudoprimes of various types].
We split these into 2 subsets - [1] those divisible by 3 or 5 and [2] those not.

Some General Observations:

The largest base-2 Fermat pseudoprime < 2^32 is 4294901761 = 193*22253377 = 2^32 - 2^16 + 1, which is reminiscent
of the 64-bit (genuine) prime 2^64 - 2^32 + 1 used by Nick Craig-Wood in his pure-integer Mersenne-mod DWT-based
convolution code.

The only twin pseudoprimes < 2^32 are 4369 (which = 17*257, the product of the Fermat primes F2 and F3) and 4371.
Similarly to F2*F3, the product F3*F4 = 16843009 is a base-2 Fermat pseudoprime. Other products of Fermat primes
are "near pseudoprimes" in the sense that their base-2 Fermat residue is a power of 2, e.g. for n=17*65537,
2^(n-1)%n = 2^16.

The largest (gap/2) between adjacent pseudoprimes (either in the merged length-10403 table or the f2psp[] one below -
the number is set by two adjacent elements of the latter - is 4199775, requiring 3 bytes to store, so no significant
compactification via a difference table is possible, as there is for the primes.
*/
ewmayer is offline   Reply With Quote
Old 2019-05-10, 21:47   #16
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

2·52·11 Posts
Default

Given the speed computers have reached, I have stopped using any list, and I just run Kim Walisch primesieve. It can sieve up to 10^10 in less than 2s.
ldesnogu is offline   Reply With Quote
Old 2019-05-10, 23:16   #17
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·3·7·139 Posts
Default

Quote:
Originally Posted by ldesnogu View Post
Given the speed computers have reached, I have stopped using any list, and I just run Kim Walisch primesieve. It can sieve up to 10^10 in less than 2s.
Perhaps posting some of the key algorithmic methods said code uses to achieve these speeds would be useful to the OP (and the rest of us.)
ewmayer is offline   Reply With Quote
Old 2019-05-11, 06:53   #18
ldesnogu
 
ldesnogu's Avatar
 
Jan 2008
France

2·52·11 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Perhaps posting some of the key algorithmic methods said code uses to achieve these speeds would be useful to the OP (and the rest of us.)
Kim wrote a page that will hopefully help:


https://github.com/kimwalisch/primes.../ALGORITHMS.md
ldesnogu is offline   Reply With Quote
Old 2019-05-11, 09:00   #19
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

Quote:
Originally Posted by ewmayer View Post
If one's aim is to support e.g. get_nth_prime(n) or "quickly enumerate all primes up to some limit"-style functionality, the way my code does this is:

1. Use a simple sieve to generate candidates not divisible by really small primes;
2. Feed surviving candidates - batches of 4-8 here tend to allow for good hiding of integer MUL latencies - to a base-2 Fermat PRP routine;
3. Do a fast lookup of the surviving candidates in a precomputed table of known base-2 Fermat pseudoprimes;
4. If a candidate does not appear in said table, it's prime.

So there's still a table involved, but it's *much* smaller than any needed for explicit prime storage. Here is the associated commentary in my code:
Code:
/* There are 10403 ( = 101*103) base-2 Fermat pseudoprimes < 2^32.
[Cf. http://home.att.net/~numericana/answer/pseudo.htm#pseudoprime for this and
other tables related to the pseudoprimes of various types].
We split these into 2 subsets - [1] those divisible by 3 or 5 and [2] those not.

Some General Observations:

The largest base-2 Fermat pseudoprime < 2^32 is 4294901761 = 193*22253377 = 2^32 - 2^16 + 1, which is reminiscent
of the 64-bit (genuine) prime 2^64 - 2^32 + 1 used by Nick Craig-Wood in his pure-integer Mersenne-mod DWT-based
convolution code.

The only twin pseudoprimes < 2^32 are 4369 (which = 17*257, the product of the Fermat primes F2 and F3) and 4371.
Similarly to F2*F3, the product F3*F4 = 16843009 is a base-2 Fermat pseudoprime. Other products of Fermat primes
are "near pseudoprimes" in the sense that their base-2 Fermat residue is a power of 2, e.g. for n=17*65537,
2^(n-1)%n = 2^16.

The largest (gap/2) between adjacent pseudoprimes (either in the merged length-10403 table or the f2psp[] one below -
the number is set by two adjacent elements of the latter - is 4199775, requiring 3 bytes to store, so no significant
compactification via a difference table is possible, as there is for the primes.
*/
Thanks for the info. Which program is this for? Sorry, I'm still a bit new here and haven't memorized who's who of program authors yet. (There's so many programs!)

It seems like a fermat test would slow things down a bit though? What does the complexity look like for a good powm algorithm?
I've mostly just played a little with GMP so far, and started picking up a bit of PARI lately.

Quote:
Originally Posted by Idesnogu
Given the speed computers have reached, I have stopped using any list, and I just run Kim Walisch primesieve. It can sieve up to 10^10 in less than 2s.
That program is pretty impressive! Honestly I don't really have a specific reason for trying to store all primes from my original post, just trying to get some ideas of roughly how much data we are talking, and learn about how various algorithms like this work. I should try actually implementing some form of wheel factorization/sieve and see how it compares.

One thing I have started wondering about, is if there is some way to further compact a very large wheel, maybe some sort of recursive implementation could use smaller wheels to save space in the larger one? Not sure if that makes any sense, still thinking it over...
hansl is offline   Reply With Quote
Old 2019-05-11, 09:40   #20
hansl
 
hansl's Avatar
 
Apr 2019

5×41 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Code:
/* There are 10403 ( = 101*103) base-2 Fermat pseudoprimes < 2^32.
[Cf. http://home.att.net/~numericana/answer/pseudo.htm#pseudoprime for this and
other tables related to the pseudoprimes of various types].
The link is dead now, btw. I was able to view it in wayback machine though.

Playing around some more in PARI, I decided to write a pseudoprime counting function:
Code:
fermat_test(b,p)=Mod(b,p)^(p-1)==1

pseudoprimepi(b,limit)={
    my(prev=4,count=0);
    forprime(p=3,limit,forstep(n=prev,p-1,2,if(fermat_test(b,n),count++));prev=p+2); 
    count
}
Results:
Code:
? pseudoprimepi(2,2^32)
%70 = 10403
? ##
  ***   last result computed in 32min, 5,043 ms.
Well, at least I got the same value as above. But man, PARI is slow for enumerating primes like this.

Note: it skips even numbers so the count is not technically correct if counting base 3 for example. Here's a version that should count all of them, but is slightly slower:
Code:
pseudoprimepi(b,limit)={
    my(prev=4,count=0);
    forprime(p=3,limit,for(n=prev,p-1,if(gcd(b,n)==1&&fermat_test(b,n),count++));prev=p+1); 
    count
}
The "b" in gcd call could be replaced with a wheel primorial (like 30) to narrow down relevant ones for the method that ewmayer talks about.
hansl is offline   Reply With Quote
Old 2019-05-12, 13:25   #21
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

19×271 Posts
Default

Quote:
Originally Posted by ewmayer View Post
If one's aim is to support e.g. get_nth_prime(n) or "quickly enumerate all primes up to some limit"-style functionality, the way my code does this is:

1. Use a simple sieve to generate candidates not divisible by really small primes;
2. Feed surviving candidates - batches of 4-8 here tend to allow for good hiding of integer MUL latencies - to a base-2 Fermat PRP routine;
3. Do a fast lookup of the surviving candidates in a precomputed table of known base-2 Fermat pseudoprimes;
4. If a candidate does not appear in said table, it's prime.

So there's still a table involved, but it's *much* smaller than any needed for explicit prime storage. Here is the associated commentary in my code:
Code:
/* There are 10403 ( = 101*103) base-2 Fermat pseudoprimes < 2^32.
[Cf. http://home.att.net/~numericana/answer/pseudo.htm#pseudoprime for this and
other tables related to the pseudoprimes of various types].
The only twin pseudoprimes < 2^32 are 4369 (which = 17*257, the product of the Fermat primes F2 and F3) and 4371.
<snip>
*/
As previously noted, the link given above is dead.

The paper Carmichael numbers and pseudoprimes may be instructive.

In particular, by the result labelled 2.1, both 17 and 257 are == 1 (mod 16) and both divide 2^16 - 1, so their product is automatically 2-psp.

Statistics for various types of pseudoprimes up to 10k for k = 9 to 14 are compiled here.

Tables of base-2 pseudoprimes up to 264 (list of numbers, list of factorizations, annotated list with factorizations and indicating Carmichael numbers, all compressed, .txt.bz2) may be downloaded from here.
Dr Sardonicus is offline   Reply With Quote
Old 2019-05-12, 19:26   #22
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·3·7·139 Posts
Default

FYI, It seems the pseudoprime page I linked in my code comment has moved to http://www.numericana.com/answer/pseudo.htm#pseudoprime .
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Intel Compute Stick (1GB RAM/8GB storage w/ Ubuntu 64-bit) ssybesma Hardware 4 2019-03-10 06:19
Prime gaps and storage HellGauss Computer Science & Computational Number Theory 18 2015-11-16 14:21
feature request: P-1 file storage on server tha Software 13 2014-03-04 15:09
Two (unrelated) questions about storage and hypert Dubslow Hardware 11 2011-07-30 06:08
A Lot Of Storage moo Hardware 0 2005-11-23 03:16

All times are UTC. The time now is 10:03.


Thu Dec 9 10:03:27 UTC 2021 up 139 days, 4:32, 0 users, load averages: 1.98, 1.52, 1.41

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.