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

31–40 of 102 posts

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

#31

Post by davidgay »

shagie wrote: post #13
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.

Correct. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole. Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending... > Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of…

> The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG

Hmm, there's a reduction of 3-cnf-sat to perl regexps, making them NP-complete. As CFGs are in NP...

https://perl.plover.com/NPC/NPC-3SAT.html

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

#32

Post by noctune »

retrac wrote: post #17
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.

> 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 machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. Informally, regular expressions like in…

Personally, I use "regex" for the informal string-matching/rewriting engines found in most languages and "regular expression" for the formal definition.

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

#33

Post by petters »

finitemonkey wrote: post #27
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…

> 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?

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

#34

Post by johnfn »

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.

Come now, every time a colleague says they parsed a file with a regex in javascript, do you turn to them and tell them "well, you didn't actually use a _regular_ expression..."

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

#37

Post by stefncb »

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.

Think about it a different way: the regex thing can only deal with unary numbers, like your computer can only deal with binary. It's really no different. I'm not sure if you can write a decimal-to-unary converter in regex but I reckon it's possible. At least using the non-regular regex like the original prime program did.

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

#38

Post by unhammer »

johnfn wrote: post #34
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.

Come now, every time a colleague says they parsed a file with a regex in javascript, do you turn to them and tell them "well, you didn't actually use a _regular_ expression..."

Only every time they claim a major mathematical breakthrough using regular expressions.

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

#39

Post by School-Cotton »

dheera wrote: post #30
tylerhou wrote: post #28

Earlier quoted context omitted.

But that argument is not interesting. "We can't count arbitrarily high because the universe is finite." Yeah, duh. (Observable universe, for the pedants.) It's more interesting to ask: suppose you did have a magical stick of RAM that had infinite storage, and suppose you augmented your computer to store and query that memory. Then -- yes -- your computer could determine whether any number, however large, is prime. An…

If you have an infinite stick of RAM, regular expressions wouldn't be FSMs, either, they could have infinite state space. They would terminate in finite time that is exponential in the size of the prime but nevertheless would still halt.

The point being made is that “regular expressions”, in the original CS meaning, do not have stack space or anything analogous. “Regular expressions” in modern programming practice are often different and more powerful, of course.

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

#40

Post by staunton »

finitemonkey wrote: post #25
retrac wrote: post #17

Earlier quoted context omitted.

> 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 machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. Informally, regular expressions like in…

> The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. Right. And if you really want to push that argument further then there are numbers for which your machine can't decide whether they are prime or not. Most of them, in fact, i.e., for all but a finite number of primes and non-primes, your machine can't tell. For the…

> And then people would need to take those classes as well, and not just claim they can write React apps just fine without a degree.

Weird tangent. They can write React apps without a degree, can't they? What's wrong with that?

The amount of complexity reasoning you need for something like that is around "this part seems slow, maybe there's a better algorithm somewhere" or "that's a lot of nested loops, maybe I can do with less". Knowing more might help in some pretty rare cases but doesn't seem like a requirement. On the other hand, knowing the complexity of all algorithms and blindly assuming "good complexity = good performance" while never checking is a recipe for desaster.

Post reply on HN