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

A regular expression to check for prime numbers (2007)

noulakaz.net

Post reply on HN
Print view View original

61–70 of 102 posts

Re: A regular expression to check for prime numbers (2007)

#61

Post by cubefox »

petters wrote: post #33
finitemonkey wrote: post #27

Earlier quoted context omitted.

> and now they are incredibly powerful but can take basically infinite memory and time. Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time. Also, nitpicking, but they take unbounded time. It's still finite.

They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?

I think with "unbounded but finite" he meant potential infinity rather than actual infinity.

Re: A regular expression to check for prime numbers (2007)

#62

Post by albert_e »

vignesh_warar wrote: post #4

Interesting! If anyone is seeking a math formula for primes, here is one: https://en.wikipedia.org/wiki/Formula_for_primes There is also a good YouTube video that explains this: https://www.youtube.com/watch?v=j5s0h42GfvM

Thanks for sharing

the video was very interesting

Re: A regular expression to check for prime numbers (2007)

#63

Post by cubefox »

tiborsaas wrote: post #49
stevage wrote: post #29

Took me a while to realise that it is not actually validating whether a given number is a prime number or not. It is validating whether a string of consecutive 1's has a prime length. In other words, it can't tell whether "3" is prime, unless you express it as "111". Much less exciting.

Sorry, but how is this different than pointing to three apples and explaining someone that this is what three is? Would you say it's not three because they are apples? I think it does not really matter how you represent the number. After all, all you see on your screen is "fake" it's just binary under the hood.

The problem with the unary numeral system is that numerals grow linearly with value, while for binary (ternary etc) they only grow logarithmically. So they need much less space and can be much faster read and written. An algorithm with relies on unary numerals probably has worse computational complexity than one that uses binary or higher.

Re: A regular expression to check for prime numbers (2007)

#64

Post by eru »

tylerhou wrote: post #7

Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.

If you want something with an actual regular expression, have a look at https://codegolf.stackexchange.com/questions/3503/hard-code-... which is a code golf for regular expressions to test divisibility by 7.

Re: A regular expression to check for prime numbers (2007)

#65

Post by eru »

pkoird wrote: post #9

Clever! I'm kinda being pedantic but I guess using \1 makes it a non-regular expression? I'm not even sure if it's CFG anymore.

If you want something with an actual regular expression, have a look at https://codegolf.stackexchange.com/questions/3503/hard-code-... which is a code golf for regular expressions to test divisibility by 7.

Re: A regular expression to check for prime numbers (2007)

#66

Post by eru »

knome wrote: post #19
chrismorgan wrote: post #16

Earlier quoted context omitted.

Although general PCRE syntax has clearly won, that’s distinct from the infinite-memory-and-time matter. Engines that don’t use backtracking and can search in linear time (O(regex-size × search-text-size)) have been making a serious comeback in recent years, at only the cost of not supporting lookaround assertions or backreferences. For example, the re2 library, or Rust’s regex crate, both of which are very popular.

Russ Cox has an excellent write up on it. "Regular Expression Matching Can Be Simple And Fast" (2007) https://swtch.com/~rsc/regexp/regexp1.html

Alas that approach only works well for your basic regular expressions that support Kleene-Star, concatenation and union.

Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_prope...), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.

Re: A regular expression to check for prime numbers (2007)

#67

Post by krupan »

neilk wrote: post #21

The original exegesis, which prompted this blog post, was by me. I am currently transitioning to a different blog engine, so the page is offline right now, but it's still available here https://web.archive.org/web/20220513113609/neilk.net/blog/20...

Much better explanation, thank you

Re: A regular expression to check for prime numbers (2007)

#68

Post by elros »

tannhaeuser wrote: post #51
wongarsu wrote: post #11

Earlier quoted context omitted.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and t…

[flagged]

So what is it that they mean, in your opinion?

Re: A regular expression to check for prime numbers (2007)

#69

Post by mmarx »

cubefox wrote: post #63
tiborsaas wrote: post #49

Earlier quoted context omitted.

Sorry, but how is this different than pointing to three apples and explaining someone that this is what three is? Would you say it's not three because they are apples? I think it does not really matter how you represent the number. After all, all you see on your screen is "fake" it's just binary under the hood.

The problem with the unary numeral system is that numerals grow linearly with value, while for binary (ternary etc) they only grow logarithmically. So they need much less space and can be much faster read and written. An algorithm with relies on unary numerals probably has worse computational complexity than one that uses binary or higher.

Actually, an algorithm working on unary input tends to have better computational complexity than an algorithm working on binary input: an algorithm that is polynomial in the numeric value will be a polynomial algorithm on unary input, but an exponential algorithm on binary input. Such algorithms are usually called pseudo-polynomial[0]; indeed, this kind of primality testing is pseudo-polynomial.

[0] https://en.wikipedia.org/wiki/Pseudo-polynomial_time

Re: A regular expression to check for prime numbers (2007)

#70

Post by taejo »

Tainnor wrote: post #58
aleph_minus_one wrote: post #47

Earlier quoted context omitted.

Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.

Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.

And via Parikh's theorem, with a one-symbol alphabet, regular and context-free languages are the same.
Post reply on HN