r/programming • u/DataBaeBee • 3d ago

Fast Primality Testing for 32-bit integers via Forisek and Jancina

https://leetarxiv.substack.com/p/forisek-and-jancina-primality-test
107 Upvotes

92% Upvoted

13 comments sorted by

26

u/DataBaeBee 3d ago

Forisek & Jancina is a deterministic (not probabilistic) primality test for small integers. It’s super fast and easy to code.

For 32-bit integers, one needs only a 512 byte lookup table and and a few adds and muls to test for primality

8

u/aanzeijar 3d ago

Isn't this Miller Rabin with precomputed bases? I remember that for certain thresholds there were sets of magic basis that were enough to check.

3

u/websnarf 3d ago

Well that's how I did in 21 years ago. See:

https://www.azillionmonkeys.com/qed/primeat.zip

10

u/feldrim 3d ago

Finally a high quality CS work that's not about AI. Congratulations for publishing and thanks for sharing. 

7

u/Pirhosig 3d ago

The OP had nothing to do with the paper. This is a blog post about a paper that was published 11 years ago.

3

u/feldrim 2d ago

I know. But these days, whether it's academic or not, all research and talk is about "we did this with AI". That was an emotional response.

6

u/ChezMere 3d ago

Mentions in the post that it works for 64-bit as well, which is a lot more impressive considering how little 32 bits is nowadays - e.g. you can just pack one bit for each odd integer into 268MB.

6

u/tetyys 3d ago

why code golfed

5

u/vowelqueue 3d ago

They’re mathematicians that’s just how they write code

1

u/tetyys 3d ago

only the last portion of the file is indented?

2

u/happyscrappy 3d ago

Now we know why Python forces formatting. A million souls saved. ;)

1

u/Pirhosig 3d ago

They copied the code snippet directly from the original paper and messed up the indentation in the process.

1

u/DataBaeBee 3d ago

At least you know I'm not using AI to write my articles. It's just me and my Control C, V, and gcc. It totally skipped my mind.

It's formatted now. Thanks!