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

81–90 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#81

Post by gerty »

School-Cotton wrote: post #67
jdnier wrote: post #56

Earlier quoted context omitted.

For some great exposition on what "regular" actually means, check out http://nikic.github.io/2012/06/15/The-true-power-of-regular-... "Thus the question arises: Can regular expressions match only regular grammars, or can they also match more? The answer to this is both yes and no"...

"regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i

FWIW, (i < n) can be replaced by (i <= floor(sqrt(n))) to avoid unnecessary iterations.

Re: Regular Expression That Checks If A Number Is Prime

#82

Post by etatoby »

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.

Back-references may not be part of the mathematical definition of regular language, but they are definitely part of the traditional (UNIX) definition of regular expressions.

The regexp in the article is perfectly compatible with UNIX grep:

    $ s=.; for i in `seq 50`; do echo $s | grep -qE '^.?$|^(..+)\1+$' || echo -n $i\ ; s=$s.; done; echo
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
(Tested on Mac OS X)

In this case, bashing PCRE is completely off-topic.

Re: Regular Expression That Checks If A Number Is Prime

#84

Post by stplsd »

etatoby wrote: post #82
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.

Back-references may not be part of the mathematical definition of regular language, but they are definitely part of the traditional (UNIX) definition of regular expressions. The regexp in the article is perfectly compatible with UNIX grep: $ s=.; for i in `seq 50`; do echo $s | grep -qE '^.?$|^(..+)\1+$' || echo -n $i\ ; s=$s.; done; echo 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 (Tested on Mac OS X) In this case, bas…

Nobody is bashing PCRE.

>but they are definitely part of the traditional (UNIX) definition of regular expressions.

This is not exactly true. In 1968 or ealier Ken Thompson wrote first grep implementation using NFA simulation, an algorithm which is now known as Thompson Construction [1][2] There were no back-references in that grep.

In 1975 Al Aho wrote an egrep which used DFA instead of NFA [3] (both NFA and DFA accepts regular languages, but in some cases DFA will have exponentially more states than the same regular language accepting NFA automata [4]) This added features such as alternation and grouping which was not supported by grep, but it not supported back-references.

Current GNU grep have -E switch which accepts extended regular expressions as described in Posix standard. Theses extended regular expressions supports back-references as do PCRE available in grep with -P switch

So no, back-references are not in traditional Unix definition of regular language.

[1] https://en.wikipedia.org/wiki/Thompson%27s_construction

[2] http://dl.acm.org/citation.cfm?doid=363347.363387

[3] http://dl.acm.org/citation.cfm?id=55333

[4] http://cs.stackexchange.com/questions/3381/nfa-with-exponent...

Re: Regular Expression That Checks If A Number Is Prime

#85

Post by chongli »

greydius wrote: post #55
db48x wrote: post #39

Earlier quoted context omitted.

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

I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.

Programmers might not be mathematicians or computer scientists, but they should be professionals

What? No. Many programmers out there are just working on fun projects in their spare time. I'm sure there exist some aerospace engineers doing that, but it's not many. I don't see why your average bedroom open source programmer should be treated like an aerospace engineer.

Re: Regular Expression That Checks If A Number Is Prime

#86

Post by nothrabannosir »

snicky wrote: post #77

Is it just me or the author of this blog post has a very annoying way of writing? He keeps explaining things and then a couple of lines below he writes something like "remember the discussion above?" or "if you remember correctly ...". Hell, sure I remember, because I just read about this 10 seconds ago. Do people really have such a short attention span and can't remember what was in a previous paragraph? Repeating s…

It's seo. The entire article is optimised for search terms relating to regular expression, prime, etc.

On a tangent, I really wish Google would release a new algorithm that punished this stuff. It's killing articles about common search terms. :/

Re: Regular Expression That Checks If A Number Is Prime

#87

Post by jk563 »

daenney wrote: post #83

Why does the example given by the author with L=15 state that the regex matches once it reaches 5, instead of 3? > So first, we’ll be testing the divisibility by 2, then by 3, then by 4 and then by 5, after which we would have a match.

It tests from the highest number first I believe.

>> As a heads-up, I just want to say that I’m lying a little in the explanation in the paragraph about the ^(..+?)\1+$ regex. The lie has to do with the order in which the regex engine checks for multiples, it actually starts with the highest number and goes to the lowest, and not how I explain it here. But feel free to ignore that distinction here, since the regular expression still matches the same thing

Re: Regular Expression That Checks If A Number Is Prime

#88

Post by Merovius »

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.

http://davidvgalbraith.com/how-i-fixed-atom/ http://stackstatus.net/post/147710624694/outage-postmortem-j... https://swtch.com/~rsc/regexp/regexp3.html

The difference isn't academical. It has huge practical implications, from software that is just annoyingly slow to DoS attacks.

People need to understand that. And stop using non-regular regexes (or better yet: regex in general) in production code. It increases world-suck.

Re: Regular Expression That Checks If A Number Is Prime

#89

Post by [deleted] »

snicky wrote: post #77

Is it just me or the author of this blog post has a very annoying way of writing? He keeps explaining things and then a couple of lines below he writes something like "remember the discussion above?" or "if you remember correctly ...". Hell, sure I remember, because I just read about this 10 seconds ago. Do people really have such a short attention span and can't remember what was in a previous paragraph? Repeating s…

[deleted]

Re: Regular Expression That Checks If A Number Is Prime

#90

Post by baristaGeek »

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

Filling the Sieve has a time complexity of O(n log log n), and accessing a value is clearly O(1). This is far away from that.
Post reply on HN