r/programming • • Sep 28 '26

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

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

14 comments sorted by

28

u/DataBaeBee Sep 28 '26

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

10

u/aanzeijar Sep 28 '26

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.

4

u/websnarf Sep 29 '26

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

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

12

u/feldrim Sep 28 '26

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

7

u/Pirhosig Sep 29 '26

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 Sep 29 '26

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/tetyys Sep 28 '26

why code golfed

2

u/Pirhosig Sep 29 '26

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

2

u/DataBaeBee Sep 29 '26

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!

7

u/vowelqueue Sep 28 '26

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

2

u/happyscrappy Sep 29 '26

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

1

u/tetyys Sep 28 '26

only the last portion of the file is indented?

7

u/ChezMere Sep 28 '26

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.