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

41–50 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#41

Post by bigiain »

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…

That'd be right - a 20 year old trick becomes Google's hottest new hiring roadblock/challenge...

newsgroup comp.lang.perl.misc, October 1997. Message-ID slrn64sudh.qp.abigail@betelgeuse.wayne.fnx.com

(I don't know if abigail "invented" that, but I remember discussing it on usenet when it appeared in her .sig back in the mid/late '90s...)

Re: Regular Expression That Checks If A Number Is Prime

#42

Post by bigiain »

mwpmaybe wrote: post #2

Very interesting. Thanks for writing this up. This is a bit more Perlish (not that I'm an authority): sub is_prime { (1x$_[0]) !~ /^(?:.?|(.{2,}?)\1+)$/; } But perhaps less clear to a novice reader. You can also leave off the semicolon.

perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number]

(My first exposure to that was in '97 or so as a .sig from abigail in comp.lang.perl.misc)

Re: Regular Expression That Checks If A Number Is Prime

#43

Post by [deleted] »

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

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 ex…

[deleted]

Re: Regular Expression That Checks If A Number Is Prime

#44

Post by Chinjut »

duaneb wrote: post #37
Chinjut wrote: post #27

Earlier quoted context omitted.

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.

Er... I'm not sure what you're saying here, in that it doesn't seem to be engaging with what I was saying, or trying to say, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked on", it's unclear what the limits are supposed to be.

I'm not actually a fan of using "regular expressions" in a sense broader than that of Kleene's regular, DFA-accepted languages, to be clear. That is exactly what I've been questioning.

Re: Regular Expression That Checks If A Number Is Prime

#45

Post by Chinjut »

btilly wrote: post #33
Chinjut wrote: post #27

Earlier quoted context omitted.

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.

I'll say to you what I said above, but even moreso: Er... I'm not sure what you're saying here, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked on", it's unclear what the limits are supposed to be.

I'm not actually a fan of using "regular expressions" in a sense broader than that of Kleene's regular, DFA-accepted languages, to be clear. That is exactly what I've been questioning.

Re: Regular Expression That Checks If A Number Is Prime

#46

Post by Chinjut »

db48x wrote: post #39
Chinjut wrote: post #25

Earlier quoted context omitted.

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 allow…

Right. My point (which may not be a particularly great point, but it was what I was trying to convey) is that the lay definition doesn't have any particular tight borders; presumably different regex libraries are capable of matching different things, use different syntax, etc.

(And this is part of why I find it confusing terminology and would prefer "regular expression" only to mean specifications of regular languages in the original formal sense. But, of course, I'm not the king of language, and it's natural that people would speak the way they speak, given the circumstances.)

Re: Regular Expression That Checks If A Number Is Prime

#47

Post by JoshTriplett »

Chinjut wrote: post #44
duaneb wrote: post #37

Earlier quoted context omitted.

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.

Er... I'm not sure what you're saying here, in that it doesn't seem to be engaging with what I was saying, or trying to say, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked…

I think the intent of the parent comments was to say that it's fine to consider a regex a standard "regular expression" in the mathematical sense if it still translates to a DFA and matches a regular language. For instance, mathematical regular expressions typically only include '*' (0 or more), not '+' (1 or more). However, you can still translate a regex including '+' to a DFA. Likewise arbitrary repetition mechanisms like {m,n}, case-insensitivity, and other features that add convenience without actually matching non-regular languages.

On the other hand, backreferences can allow matching non-regular languages.

Re: Regular Expression That Checks If A Number Is Prime

#48

Post by Chinjut »

JoshTriplett wrote: post #47
Chinjut wrote: post #44

Earlier quoted context omitted.

Er... I'm not sure what you're saying here, in that it doesn't seem to be engaging with what I was saying, or trying to say, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked…

I think the intent of the parent comments was to say that it's fine to consider a regex a standard "regular expression" in the mathematical sense if it still translates to a DFA and matches a regular language. For instance, mathematical regular expressions typically only include '*' (0 or more), not '+' (1 or more). However, you can still translate a regex including '+' to a DFA. Likewise arbitrary repetition mechani…

Ah, yeah, I see now that that is indeed probably what they meant; thanks! In that case, yes, I'm sympathetic to that, using regex to just mean "Anything that ultimately describes a regular language".

Re: Regular Expression That Checks If A Number Is Prime

#49

Post by jnordwick »

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.

It destroys mechanical sympathy. Many people can no longer understand why some of their regex calls are so slow or why some are so much quicker.

Re: Regular Expression That Checks If A Number Is Prime

#50

Post by Retric »

duaneb wrote: post #35
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.

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.

Regular expressions has implications in space time complexity. PCRE tosses that away.
Post reply on HN