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

Regular Expression That Checks If A Number Is Prime

iluxonchik.github.io

Post reply on HN
Print view View original

31–40 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#31

Post by btilly »

jnordwick wrote: post #15
TimWolla wrote: post #3

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

That wasn't PCRE. That was Perl. PCRE just copied the features that people liked in Perl, and made them available elsewhere.

The same features have also been implemented independently many times. For example Ruby, Java and Python all have independent implementations of regular expressions with a lot of the same features.

Re: Regular Expression That Checks If A Number Is Prime

#33

Post by btilly »

Chinjut wrote: post #27
conistonwater wrote: post #26

Earlier quoted context omitted.

I always understood it as being whatever can be straightforwardly tacked onto a typical DFA implementation. I though that's how people came up with it—whichever extras were the easiest to implement without mucking anything else up, so in a way they "came for free". (It's possible I misunderstood, I don't know for sure.)

Well, sure, but "whatever can be straightforwardly tacked on" is highly subjective, no?

No, it is not.

You can invent a variety of notations to describe a DFA. But you can't change the formal definition of a DFA, or what kinds of things a DFA can match without making it not a DFA.

Re: Regular Expression That Checks If A Number Is Prime

#34

Post by cstrahan »

conistonwater wrote: post #23
jnordwick wrote: post #15

Earlier quoted context omitted.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

But why should people care about what is regular in the formal sense ? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.

PCRE doesn't implement that "restricted type of algorithm", and I think that's what the parent is suggesting is wrong, not so much the difference between formal understanding vs informal, intuition of the same subject (I would argue that the latter would be sufficient, but few even have that).

Understanding REs (a little more) formally, one can exploit their properties for e.g. performance and/or concision. For an example of what that understanding gives you, I'd recommend checking out the Ragel state machine compiler.

Re: Regular Expression That Checks If A Number Is Prime

#35

Post by duaneb »

jnordwick wrote: post #15
TimWolla wrote: post #3

It should be noted that this is not possible with regular expressions in the traditional sense (i.e. regular expressions only matching regular languages): http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.

One of my pet peeves is how PRCE destroyed the definition of "regular" in regular expressions. It has basically made a huge number of programmers illiterate as to what truly is regular in the formal sense.

Sure, but on the pragmatic hand, "regular" isn't super useful unless you're designing a language yourself. If you're parsing something, not understanding "regular" is going to hurt a lot less than attempting to use PCRE to do something it can't.

Re: Regular Expression That Checks If A Number Is Prime

#36

Post by jayshua »

Chinjut wrote: post #10
jlarocco wrote: post #8

Earlier quoted context omitted.

That's true, but it is actually possible to construct true regular expressions that check if a binary string of digits is divisible by an arbitrary integer. Obviously not the quickest or most intuitive way to do it, though. There's an interesting book that covers some unusual aspects of automata and regular expressions: https://www.amazon.com/Finite-Automata-Regular-Expressions-S...

Sure, for a fixed arbitrary integer M. (Supposing the input is fed in in big-endian order, you just keep track of the remainder modulo M as each new bit comes in, updating it by turning r into (r * 2 + new bit) mod M. Since this only requires finite state, it is regular). But that won't get you a primality checker. You can't get a primality checker. Primes don't comprise a regular language, neither in unary nor in an…

What do you mean by "non trivial base?"

Re: Regular Expression That Checks If A Number Is Prime

#37

Post by duaneb »

Chinjut wrote: post #27
conistonwater wrote: post #26

Earlier quoted context omitted.

I always understood it as being whatever can be straightforwardly tacked onto a typical DFA implementation. I though that's how people came up with it—whichever extras were the easiest to implement without mucking anything else up, so in a way they "came for free". (It's possible I misunderstood, I don't know for sure.)

Well, sure, but "whatever can be straightforwardly tacked on" is highly subjective, no?

Not really. A graph is either a valid DFA or it is not. At that point, it's a matter of tooling in terms of "straightforward"ness.

Re: Regular Expression That Checks If A Number Is Prime

#38

Post by hexane360 »

biot wrote: post #9
delsarto wrote: post #6

tl;dr if you know a little regex - convert your number to a string of that length (1 = 1, 2 = 11, 3 = 111) - handle 0 / 1 separately - ^(..+?)\1+$ - trick; the WHOLE thing has to match to return (^$) - first \1 match is "11", ergo string must be "11", "1111", "111111" to match - second \1 match "111", ergo string must be "111", "111111", "111111111" to match - and so on. if you find before length of string, it was no…

In other words, it's the Sieve of Eratosthenes implemented via regex: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Well, not really. It's closer to trial division, though even that doesn't go through every single multiple from 1-n.

The difference is the sieve works on a large batch of numbers, and only tests divisibility with numbers not known to be composite, and less than sqrt(n).

https://en.wikipedia.org/wiki/Trial_division

Re: Regular Expression That Checks If A Number Is Prime

#39

Post by db48x »

Chinjut wrote: post #25
conistonwater wrote: post #23

Earlier quoted context omitted.

But why should people care about what is regular in the formal sense ? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.

Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?

"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular".

However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allows them to concisely match strings, not that it allows them to match regular languages.

Thus there are two standards you could follow: the precise mathematical definition of "regular", or the lay definition.

Re: Regular Expression That Checks If A Number Is Prime

#40

Post by theseoafs »

Chinjut wrote: post #25
conistonwater wrote: post #23

Earlier quoted context omitted.

But why should people care about what is regular in the formal sense ? Rather, regular in this context would mean it can be recognized with a restricted type of algorithm, which resembles the formalism.

Is there a standard for which additional features one can add on top of regular expressions in the original limited sense and still be considered a regex?

If you can compile any string in the language to a DFA then it's equivalent in power to regular expressions.
Post reply on HN