←back to thread

One year, 41M digits: How Luke Durant found the largest known prime number

(www.washingtonpost.com)
60 points ortusdux | 1 comments | 06 Nov 24 20:56 UTC | HN request time: 0s | source
Show context
tholman ◴[07 Nov 24 04:35 UTC] No.42073444[source]▶
Fun hypothetical, or can someone solve? How long, would this regex prime check [1] (via hn 2009) take to run on this on todays average machine?

Hitchhiker's Guide's Deep Thought "42" was 7.5 million years, just for a guide-post.

- [1] https://news.ycombinator.com/item?id=707236

replies(2): >>42073530 #>>42074574 #
1. lifthrasiir ◴[07 Nov 24 08:00 UTC] No.42074574[source]▶
Heavily depends on how sophisticated are regex engines. Regex engines are like compilers, in that they are free to do anything as long as the result doesn't change (in a certain defined manner, of course), so engines can of course specialize for that particular regex. They don't even have to specially target the non-prime regex (yes, that matches 0, 1 or n*m copies of ones where n, m >= 2) by the way, because backreferences are already pretty rare and there are lots of potential optimizations to be made if they were much more popular. So the answer can greatly vary even when we limit ourselves to contemporary libraries. That said, it would be extremely more impractical to build a string made of 2^136279841 - 1 ones to run that regexp.

(Seriously though, it would make a very good April fools' day PR to recognize that particular regex and trigger a non-trivial prime check routine to match them.)