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.
"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 < n; ++i) {
if (n % i == 0) {
return false;
}
}
return true;
}
The value i can take an a priori unbounded amount of memory.
It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.
Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).
Yup. Note that the method of specifically being fed the input sequentially, one by one, means that, for example, "Strings of odd length whose middle character is 'X'" does not comprise a regular language, even though one might naively reason this to be trivial to detect with O(1) memory ("Just go look at the middle character!").
Yeah, obviously, there are lots of ways to improve that code. First off all, much more efficient to to do (i * i <= n) instead of (i <= sqrt(n)), or at the very least you can cache sqrt(n) so you don't recalculate it every step.
You can also do a separate test for 2, then start at 3 and use i+=2 instead of i++, that cuts the test time in half. Once you've done that, you can observe that all primes are 6k +/- 1 except 2 and 3, which makes your code 3 times faster than the naive version.
At this point, you've basically got a simple wheel primality testing algorithm going, so why not go all the way?
I don't think the parent poster was making the point that his was the most efficient algorithm for testing primes. I think his point was that regular numbers are O(log n) in CS terms, not O(1), which is not obvious at first.
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.
Perl started with Henry Spenser's regular expression library, which was written in the mid-1980s. That got used in a lot of places, and may have been used in sed. It includes backreferences. I don't know what predates that.
Perl used that as a starting place and began adding extensions such as the difference between .* and .*?.
So using "non-regular thing" as a regular expression predates Perl. But the dialect we standardized on with the features people now expect is due to Perl's influence.
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.
They were named "regular" in the formal sense. Thus if they are not regular, it is a misnomer. It would have been just as useful to call them "Perl Matching Expressions", but without all the additional confusion about what a regular expression can do.
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.
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.
No, but he probably does use layman's terms when describing molecular lattices and electron shells. If he ever does.
The point here is that users of (colloquial) regular expressions, however professional they are or aren't, are just engaging with the surface of a deeper set of mathematical principles that require greater nuances of meaning to discuss than their applications do.
I basically agree, but I would say that a slightly deeper understanding of regular expressions is a really useful thing to know for basically all professional programmers. If for no other reason they can recognize the "pathological" cases where backtracking implementations (i.e. almost all modern regex implementations) would need until the heat death of the universe to evaluate.
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.
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.)
The lay definition isn't a definition, per se, it's a misappropriate of the term. Since the lay user only cares about text matching, the term for what they need is "text matching syntax" or some such thing.
And surely you don't think those implementing the regular expression engine are lay people. They should know better.
> there are two standards you could follow: the precise mathematical definition of "regular", or the lay definition
Considering this writeup leads with a giant headline saying "Regular Expressions - The Theory"... I think the complaints about how it's not actually a regular expression are even more valid than usual.
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.)
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.
You can actually quite easily add features to regular expressions, that are typically excluded while still being actually regular. Examples would be an `and` or a `not` operator.
What I am saying is that you can come up with a lot of extensions of the basic regular expression language. But there is no subjectivity at all in whether the extensions can be implemented by a DFA. Either you can, or you can't.
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.
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.
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".
I don't think so, not too much anyway, I think the "software engineering" aspects of it would place reasonably strong constraints on what is desirable and on what is feasible (for a DFA). That's probably how the (informal?) consensus emerged.
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.
Indeed. To support backreferences, "regex" libraries are forced to use algorithms that can be very slow in the worst case.
The sad thing is that the libraries use the same algorithms even if the expression doesn't contain backreferences. A while ago, Stack Overflow had a brief outage because of regular expression performance, although the expression that caused it didn't even use backreferences or other non-regular features:
In contrast, Google Code Search - when it still existed - supported regular expression searches over world's public codebases. One key ingredient making this possible was to only use proper regular expressions:
Regular is actually incredibly useful because it allows you to confidently parse or validate (large amounts of) untrusted data without having to worry about DoS attacks.
I'd argue that this is useful, even if you use it as part of a parser that doesn't just parse regular languages, as you'll have a slightly easier time reasoning about the time and space complexity of the construction.
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.
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 any nontrivial base.
Oh, just as opposed to unary. Writing numbers in the ordinary way in any ordinary base, which is to say, bases greater than 1; base 2, base 3, base ten, whatever.
It's worth pointing out that we are talking about representing numbers in unary, though. Or even more directly, plain ol' string length since the RE under discussion doesn't even care what symbols you are using, so "11111" = "abcde" under this RE.
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.
>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.
- 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 not prime.
Clever trick. Look forward to being asked it in your next google interview :)
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).
This regexp is totally brilliant. It solves this problem in an unexpected way, because you think numbers, but the solution thinks strings. Not only that, the paradox, or its beauty, is that it goes to the root of the number abstraction: counting sticks.
Okay, technically it's regex, but I didn't want to get into this distinction, since "regex" and "regular expression" are used pretty much interchangeably (unless you're in the academia :) ).
I guess if you imagine a person walking from the beginning of the text to the end, their front (the side with the face on it) would face the end of the text.
But English never conceives of text in this manner; we view text as being arranged in a chronological order, where text that occurs chronologically earlier comes "before" text that occurs chronologically later. This mirrors the application of "before" and "after" to time in the rest of the language. Whether you conceive of reading as the reader traveling through text from the beginning to the end, or as text arriving at the reader, the reader will always encounter text on the left before text on the right, and therefore the text on the left is in front of the text on the right.
(In the only other language I'm qualified to talk about this for, mandarin chinese, earlier and later time might be indicated by either of two spatial metaphors: "up" for the past and "down" for the future ["up" is also used as a metaphor for beginning things]; or "front" for earlier and "back" for later. When text is read from left to right, "front" is used to indicate text on the left.)
Here ( http://www.friesian.com/egypt.htm ) is someone writing about the ancient Egyptian writing system, inadvertently assuming that the front of text is its beginning and the back of text is its end:
> Note that Egyptian glyphs have a front and a back. All the images above and below face to the left, [...] which indicates that the text is to be read from left to right. This is conformable with the usage of English and other European languages. However, although this would be familiar and agreeable to the Egyptians, Egyptian usage was ordinarily to write from right to left, as today is done in Hebrew and Arabic. They indicated this direction by having all the glyphs face to the right instead of to the left
(Egyptian glyphs often depict a person or an animal with an actual face. They face towards the beginning of the text, not the end.)
You seem to speak English at a fully native level, based on your writeup here. (Although you don't seem to have picked up on the idea that if a quantifier "precedes" a '?', it must be "in front" of that '?'.) Do you have another native language? Are you based in a country that primarily speaks some other language? What is the metaphor that determines that later words are "in front" of earlier words?
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 stuff over and over seems almost like content farming to me.
You are probably right, but this function was my first head-to-head encounter with Perl, I researched just a little bit what I needed to know in order to write it.
Performing a Miller-Rabin primality test or filling a Sieve of Eratosthenes will almost always be the way to go. However, this line of code seems like magic and that's kind of impressive.
>> 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
Right, that makes sense. But in the explanation they go from 2, to 3 to 4 to 5, following along with the lie, yet picking the real solution. It's a bit confusing.
It's basically the Sieve of Eratosthenes[1] algorithm, and it's possible to do it with regular expressions because numbers here are represented in unary[2] number system, where number of characters/tokens equals the number itself. It's a common trick for testing various Turing-machine stuff.
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear, this is not going to make it in any real use.
Imagine naive absolute-beginner-programmer trial division. This is worse. Now add the overhead of counting via regex backtracking and integer comparison via matching strings. A fair number of regex engines will also start using enormous amounts of memory.
AKS is of theoretical interest, but not really a "normal test." It's very slow in practice, being beat by even decent trial division for 64-bit inputs (it's eventually faster, as expected, but it takes a while). But it is quickly faster than this exponential-time method. The regex is in another universe of time taken when compared to the methods typically used for general form inputs (e.g. pretests + Miller-Rabin or BPSW, with APR-CL or ECPP for proofs).
As others have noted, "has been popularized by Perl" is because it was created by Abigail, who is a well-known Perl programmer (though almost certainly a polyglot). It's also been brought up many times, though it's a nice new blog article. I hope the OP found something better when "researching the most efficient way to check if a number is prime." In general the answer is a hybrid of methods depending on the input size, form, input expectation, and language. The optimal method for a 16-bit input is different than for a 30k-digit input, for example.
It is a proven deterministic test of primality. We already had those before AKS, and they are significantly faster than AKS (even the various improvements). But they don't check all the boxes that are useful for stating things in computational complexity proofs without a paragraph of weasel words. So from the theory side of things, it's great since we don't particularly care about the actual execution time, but the asymptotic behavior and whether it is solidly shown to be in P.
Lots of math packages have deterministic primality tests, but none use AKS as a primary method, because AKS offers no benefits over other methods and is many orders of magnitude slower.
For inputs of special form, there are various fast tests. E.g. Mersenne numbers, Proth numbers, etc.
The fastest method depends on the input size and how much work you want to put in. For tiny inputs, say less than 1M, trial division is typically fastest. For 32-bit inputs, a hashed single Miller-Rabin test is fastest. For 64-bit inputs, BPSW is fastest (debatable vs. hashed 2/3 test). The BLS methods from 1975 are significantly faster than AKS up to at least 80 digits, but ECPP and APR-CL easily beat those. ECPP is the method of choice for 10k+ digit numbers, with current records a little larger than 30k digits.
Horrific. It's implicitly checking for every divisor (which is O(n)) but there's also the complexity from using a regex engine (which can be O(n*m)). So the overall complexity is probably of the order O(n^2).
Because of back references PCRE regular expressions can match non-regular languages as well.