9 ms·
Regular Expression That Checks If A Number Is Prime
- mwpmaybe 10y agoVery 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.
- iluxonchik 10y agoThank you :) 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.
- bigiain 10y agoperl -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)
- peteretep 10y agoSome asshole gave me this in an interview for a Perl dev job, and asked me what it did.
- bigiain 10y agoWasn't at an interview, but I remember quizzing the "new guy" Perl dev with "So explain what this one does": @sorted = map { $_->[0] } sort { $a->[1] cmp $b->[1] } map { [$_, foo($_)] } @unsorted; (Twenty years or so back, I could occasionally be "that asshole"... I'm better now, honest...)
- rrauenza 10y ago> How would we go about that? Well, all we have to do is add ? in front of the +. This will lead us to the <.+?> regex. I was very confused until I realized the author's definition of 'in front' wasn't the same as mine...
- iluxonchik 10y agoWhat do you mean? Could you please clarify that? What did your understand by "in front"?
- Chinjut 10y agoPresumably, they thought of A as in front of B in the expression "AB" rather than in the expression "BA". (Which is also how I would normally think of "in front", for what it's worth!)
- iluxonchik 10y agoOh, that was probably it. That would be true if we were talking about FIFO queues :)
- Normal_gaussian 10y agoWhich, in my experience, is how writing then reading text works.
- thaumasiotes 10y agoI'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?
- iluxonchik 10y agoWell, we read from left to right, naturally that is the order of the letters, so the one on the right is "in front" of the left one.
- TimWolla 10y agoIt 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 http://math.stackexchange.com/a/181233/21405 Because of back references PCRE regular expressions can match non-regular languages as well.
- jlarocco 10y agoThat'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-Solutions/dp/1887187162/ https://www.amazon.com/Finite-Automata-Regular-Expressions-S...
- Chinjut 10y agoSure, 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.
- jemfinch 10y agoI wish they'd stop calling these expressions "regular".
- iluxonchik 10y agoOkay, 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 :) ).
- delsarto 10y agotl;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 not prime. Clever trick. Look forward to being asked it in your next google interview :)
- mmagin 10y agoDoesn't this have some relation to https://en.wikipedia.org/wiki/Church_encoding https://en.wikipedia.org/wiki/Church_encoding
- loeg 10y agoIt's basically a prime sieve done on a string encoding.
- deleted 10y ago[deleted]
- biot 10y agoIn other words, it's the Sieve of Eratosthenes implemented via regex: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
- Veedrac 10y agoNo, that's completely different. This is just trial division, with really slow division.
- hexane360 10y agoWell, 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 https://en.wikipedia.org/wiki/Trial_division
- ipozgaj 10y agoIt'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. [1] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes [2] https://en.wikipedia.org/wiki/Unary_numeral_system https://en.wikipedia.org/wiki/Unary_numeral_system
- conistonwater 10y agoNo it's not, this is the trial division algorithm for primality testing.
- jsrn 10y agoInvented in 1998 by Perl hacker Abigail: http://neilk.net/blog/2000/06/01/abigails-regex-to-test-for-prime-numbers/ http://neilk.net/blog/2000/06/01/abigails-regex-to-test-for-... (check out Abigail's other JAPHs if you like stuff like this)
- iluxonchik 10y agoYep, you are correct :)
- jimjimjim 10y agohow many problems do we have now?
- JBiserkov 10y agoApproximately n / ln n according to https://en.wikipedia.org/wiki/Prime-counting_function https://en.wikipedia.org/wiki/Prime-counting_function
- passwordreset 10y ago98. Checking for primality ain't one.
- ldom22 10y agohave regular expressions gone too far?
- Senji 10y agoOur hubris will be our undoing.
- 0xmohit 10y agoI suppose that this has been around for a while: https://news.ycombinator.com/item?id=9039537 https://news.ycombinator.com/item?id=9039537 http://montreal.pm.org/tech/neil_kandalgaonkar.shtml http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
- kgdinesh 10y agohow does it fare on time complexity compared to normal tests like say AKS?
- cyphar 10y agoHorrific. 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).
- YomiK 10y agoIt'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.
- kgdinesh 10y agoWhy is AKS only of theoretical interest? Isn't it proven to be a deterministic test of primality? Also, what is the fastest way to test for primality that's practically feasible?
- YeGoblynQueenne 10y agoCan't quite get this to work in vim [1]: \(^1\{-,1}$\)\|\(^\(11\+\)\1\+$\) The two parts match what you'd expect on their own but the OR-ing screws it up: it means the whole regex matches everything. Is this something vim gets right and every other engine wrong, the other way around, or...? _____________ [1] I'm matching 1's rather than dots to avoid highlighting every bit of text ever anywhere all the time. Also, that way it's so much more pleasing to the eye and easy to read, don't you think?
- thaumasiotes 10y ago> Also, that way it's so much more pleasing to the eye and easy to read, don't you think? No, it's harder to read. For ease of reading, you need to match something that isn't already part of the expression, like 2s or Ks.
- YeGoblynQueenne 10y ago>> No, it's harder to read. Don't worry, I had my humour removed at birth also. It grows back, eventually.
- snicky 10y agoIs 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.
- nothrabannosir 10y agoIt'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. :/
- deleted 10y ago[deleted]
- daenney 10y agoWhy 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.
- jk563 10y agoIt 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
- daenney 10y agoRight, 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.
- baristaGeek 10y agoPerforming 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.
- fxn 10y agoThis 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. I explored this technique some years later to solve a bunch of other problems, coprimality, prime factorization, Euler's phi, continued fractions, etc. (see https://github.com/fxn/math-with-regexps/blob/master/one-liners.sh https://github.com/fxn/math-with-regexps/blob/master/one-lin...).
- caub 10y agoit's highly inefficient tho
- unsiebui 10y agoHi! I wet & wanna masturbate with you now. We will play? Im here - http://u.to/aeg3Dw http://u.to/aeg3Dw