Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Generating All 32-Bit Primes (Part I)

hnlyman.github.io

Post reply on HN
Print view View original

21–30 of 35 posts

Re: Generating All 32-Bit Primes (Part I)

#21

Post by hnlyman »

tromp wrote: post #18
mark-r wrote: post #8

You can combine the Sieve and Wheel techniques to reduce the memory requirements dramatically. There's no need to use a bit for numbers that you already know can't be prime. You can find a Python implementation at https://stackoverflow.com/a/62919243/5987

Or a C implementation at https://tromp.github.io/pearls.html#sieve which runs in well under 10s.

I'd be interested in seeing an explanation of the code, since it looks pretty incomprehensible to me. Per the arbitrary rules I set for myself, I'm not allowed to precompute/hardcode the wheel (looks like this implementation uses a hardcoded wheel of size 2x3x5=30). I wonder if/by how much the performance would suffer by computing and storing the coprime remainders in memory instead of handing them directly to the compiler.

Re: Generating All 32-Bit Primes (Part I)

#24

Post by flancian »

susam wrote: post #13

I have a little tool called Prime Grid Explorer at https://susam.net/primegrid.html that I wrote for my own amusement. It can display all primes below 3317044064679887385961981 (an 82-bit integer). The largest three primes it can show are 3317044064679887385961783 3317044064679887385961801 3317044064679887385961813 Visit https://susam.net/primegrid.html#3317044064679887385961781-2... to see them plotted. Click the bu…

Very cool, thank you! Both the visualization tool and the description of Miller-Rabin.

I didn't know an algorithm with these properties existed!

Furthermore, your tool gave me a more intuitive feel of the rate at which primes "thin out" than every treatment of the topic I read previously.

Re: Generating All 32-Bit Primes (Part I)

#26

Post by csense »

I'm pretty sure you can get rid of the 0xFFFFFFFF / p and get some more speedup by manually implementing the bitarray ops. You can get another boost by using BSF instruction [1] to quickly scan for the next set bit. And you really only need to store odd numbers; storing the even numbers is just wasteful.

You can get even more speedup by taking into account cache effects. When you cross out all the multiples of 3 you use 512MB of bandwidth. Then when you cross out all multiples of 5 you use 512MB more. Then 512MB again when you cross out all multiples of 7. The fundamental problem is that you have many partially generated cache-sized chunks and you cycle through them in order with each prime. I'm pretty sure it's faster if you instead fully generate each chunk and then never access it again. So e.g. if your cache is 128k you create a 128k chunk and cross out multiples of 3, 5, 7, etc. for that 128k chunk. Then you do the next 128k chunk again crossing out multiples of 3, 5, 7, etc. That way you only use ~512MB of memory bandwidth in total instead of 512MB per prime number. (Actually it's only really that high for small primes, it starts becoming less once your primes get bigger than the number of bits in a cache line.)

[1] https://en.wikipedia.org/wiki/Find_first_set

Re: Generating All 32-Bit Primes (Part I)

#27

Post by tromp »

hnlyman wrote: post #21
tromp wrote: post #18

Earlier quoted context omitted.

Or a C implementation at https://tromp.github.io/pearls.html#sieve which runs in well under 10s.

I'd be interested in seeing an explanation of the code, since it looks pretty incomprehensible to me. Per the arbitrary rules I set for myself, I'm not allowed to precompute/hardcode the wheel (looks like this implementation uses a hardcoded wheel of size 2x3x5=30). I wonder if/by how much the performance would suffer by computing and storing the coprime remainders in memory instead of handing them directly to the co…

I wrote this in a semi obfuscated style to make it fit on one screen. It's indeed a hardcoded 2x3x5 wheel; but I suspect computing all those constants would have made the program significantly longer.

Re: Generating All 32-Bit Primes (Part I)

#29

Post by adgjlsfhk1 »

dahart wrote: post #14
senfiaj wrote: post #5

There is also the segmented Sieve of Eratosthenes. It has a simlar performance but uses much less memory: the number of prime numbers from 2 to sqrt(n). For example, for n = 1000000, the RAM has to store only 168 additional numbers. I use this algorithm here https://surenenfiajyan.github.io/prime-explorer/

The Pseudosquares Sieve will drop the memory requirements much further from sqrt(n) to log^2(n). https://link.springer.com/chapter/10.1007/11792086_15

IMO that algorithm is barely a sieve. It is technically pareto optimal, but it seems like in practice it would just end up worse than either an optimized segmented sieve (it is ~log(n)^2 slower) or an O(1) memory method (probable prime test followed by a deterministic prime test) depending on how large and how wide the numbers you're testing are.

Re: Generating All 32-Bit Primes (Part I)

#30

Post by adgjlsfhk1 »

esterna wrote: post #28

Very nice! One small note: In an Eratosthenes sieve, you can start crossing out numbers from p^2, since i*p for i for (size_t i=2; i by for (size_t i=p; i

and you can get another 2x improvement by incrementing i by 2

for (size_t i=p; i since every other one will be a multiple of 2

Post reply on HN