8 ms·
A regular expression to check for prime numbers (2007)
- userbinator 5y agoIt's basically https://en.wikipedia.org/wiki/Trial_division https://en.wikipedia.org/wiki/Trial_division using the + operator, and enforcing the bounds of the match to require a zero remainder.
- rofr999 5y agoI'm going to test this on large numbers and post the results!
- saagarjha 5y agoYou’ll probably not be able to finish before the 14-day reply period expires.
- xcambar 5y agoI can see you have a very efficient method for wasting time and energy. Why? The method works. Size doesn't matter. But it's extremely inefficient. Which can be calculated rather than measured.
- rofr999 5y ago
- reactspa 5y agoIs this a case of P != NP?
- pxx 5y agoprimality testing is in P by the AKS construction (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/primality_journal.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...)
- tmalsburg2 5y agoI think OP understands this and their comment was a joke.
- mrjin 5y agoYep. It seems doesn't matter what, there is always people trying to use it in a way it wasn't meant to.
- wittycardio 5y agoNot sure if anything about his comment suggests that tbh.
- brightffw 5y ago
- cqcn1991 5y agothis is very useful; thanks!
- tasty_freeze 5y agoWhat it is really doing is checking if the length of a string is a prime number or not. And as coded, it is checking specifically if the length of a string consisting of some number of '1' characters is prime or not.
- rawling 5y agoI've done some Codewars problems where you have to write a regex to check whether an input number is divisible by a specific number, so I was really interested to see how that would work for primes. Nope, it's just playing with lengths.
- randv 5y ago- it is turning the number into a string of 1s 3 => 111 4 => 1111 and so on - then trying to simulate divisibility test by trying to find perfect groups of '11' to simulate division by 2 failing which (that is the backtracking part) and trying find perfect groups of '111' to simulate division by 3 and so on... Clever but very inefficient
- nvader 5y agoAnd takes space exponential to the number of bits in the input.
- ahmed_ds 5y agoI feel like Charlie Kelly from IASIP reading this regex. "1. Starts out with 1, then there is other stuff...." https://youtu.be/AFDU_R6ShmI?t=74 https://youtu.be/AFDU_R6ShmI?t=74
- Dylan16807 5y agoHuh, looking at some regex explaining sites, they don't seem to do a good job of simplifying. Which is a shame because it's really easy to simplify away most of this regex. / does nothing ^ and $ only exist to make it do the whole string | is just saying "or", and only the part to the right really matters. And the ? doesn't do anything meaningful. Throw all that out and all you have is (11+)\1+ It's still a mash of symbols, but it's much simpler. And changing it to (cc+)\1+ would probably help naive readability too.
- aghilmort 5y agomy fave regex explainer gives this, idk that it adds much? https://regexper.com/#%2F%5E1%3F%24%7C%5E%2811%2B%3F%29%5C1%2B%24%2F https://regexper.com/#%2F%5E1%3F%24%7C%5E%2811%2B%3F%29%5C1%...
- Dylan16807 5y agoThat's the best I've seen so far, at least. Much better than a bunch of bullet points of various indentation.
- mordechai9000 5y agoThe question mark isn't meaningless - it changes the matching behavior of + from greedy to non-greedy. The non-greedy version will try to match shorter strings first. This should be more efficient, because non-primes will fail sooner. Most numbers will fail a lot sooner.
- Dylan16807 5y agoIt takes just as long on primes, so the overall runtime will be very similar. So sure it's an optimization but it's not one to care about when you're trying to understand it.
- deleted 5y ago[deleted]
- mmaunder 5y agoI prefer the source which I think is a clearer explanation. The key is that perl’s x operator turns the number into a string of 1s that is the length of the number. The rest is a hack to use regex to perform division using minimal capturing and back references. http://montreal.pm.org/tech/neil_kandalgaonkar.shtml http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
- btdmaster 5y agoIt's crazy how fast Perl's regex engine does this!
- dhosek 5y agoAt first I was thinking this was actually operating on a binary representation of the numbers. Some interesting things become apparent when you look at numbers in binary, for example, numbers of the form 2^n-1 can be represented as a string of n 1s. From there, it's pretty obvious that if n is composite that 2^n is also composite since you can take that string of n=kp 1s and write it as k groups of p 1s so obviously, 2^p-1 divides 2^n-1. There's the famous quote from Leopold Kronecker, “God made the integers” and I always thought that when he did, he wrote them in binary.
- cmeacham98 5y ago.
- Rerarom 5y agoNo, in unary.
- colanderman 5y agoI'll be "that guy" -- this is not a regular expression [1]. A Perl regexp, sure. But backreferences are not part of the grammar of regular expressions, and moreover, using them in that particular manner (to refer to a capture of unbounded length) cannot be encoded as a DFA and therefore does not describe a regular language. (I have no clue whether unary-representation primality is actually regular or not -- it's been far too long since my automata class to remember how to (dis)prove that -- but I guess it's at least sublinear, since primality is polynomial w/r/t the logarithm of the number being tested.) [1] https://en.wikipedia.org/wiki/Regular_expression#Formal_definition https://en.wikipedia.org/wiki/Regular_expression#Formal_defi...
- dudeman13 5y agoThanks for that. My initial reaction to the title was "wait, you can describe prime numbers using formal languages?". I could feel it in my guts that this would probably have some mind blowing Math/CS implications. A shame how I'm so rusty in my Mathematics and CS nowadays :(
- aghilmort 5y agohad same immediate reaction, like whoa, huge if true, time to read the comments
- nickelpro 5y agoI'll be "the other guy" -- no one uses the term regex or regular expression in a programming context to mean a strictly regular language in the theoretical computer science sense. Nitpicking this point is ignorant of how the usage of the term has evolved within the programming community. Good. There's that obligative conversation over and done with.
- eutropia 5y agoI’ll be the guy who postscripts that “hardmode” regexes would have important mathematical and computer science implications when/if they solve certain problems (like identifying primes). So it’s not pure pedantry, and there’s an important difference between “regexes to solve programming problems” and “regexes solving math problems”.
- avinash 5y agoAha. I wrote this post 15 years ago after explaining to my wife (who is a Language major) how this "regular expression" works. It has been discussed a few times on Hacker News, Reddit, etc. over the past 15 years...
- bmn__ 5y agoCredit is due to Abigail <https://web.archive.org/web/2020/http://www.abigail.be/ https://web.archive.org/web/2020/http://www.abigail.be/>. Please give it and be a good Internet citizen by amending the post.
- phgn 5y ago@dang can we please add (2007) to the title?
- chx 5y agoAs an aside, a Hungarian mathematician wrote an entire book explaining how mathematics works to a, I guess, a language major (well, Marcell Benedek was a professor, a writer, a literary historian, a translator, a theatre director). https://en.wikipedia.org/wiki/Playing_with_Infinity https://en.wikipedia.org/wiki/Playing_with_Infinity
- deleted 5y ago[deleted]
- amp108 5y agoInteresting, I wrote a quick script to use this: #!/usr/bin/env ruby def is_prime(n) ("1" \* n.to_i)!~ /^1?$|^(11+?)\1+$/ end num = ARGV.shift $stdout.puts is_prime(num) ... then decided to test it on a button-mashed number: $ruby ~/prime.rb 767423 ... and it hung. Thought it was the length of the number, so I tried something smaller (101). Quick "true". Then I tried progressively more digits. I got to `ruby ~/prime.rb 7673121` (false) and it took less than a second. But it doesn't like something about the number 767423.
- TrianguloY 5y agoThe regexp basically tests all dividers of the number (from 2 to the number-1), if it founds one, it says false and stops, if nothing is found, it says true. 101 is prime, but it does "only" a hundred checks approx. 7673121 is divisible by 3, so as soon as it tries to match groups of 3 it succeeds and stops. 767423 is prime, so it needs to do hundreds of millions of checks, that's probably why it hungs. Basically: the runtime of the algorithm should be equivalent to the minimum divisor excluding 1 of the number.
- ogogmad 5y agoCan you decide if a number is prime using a true regular expression? No. This won't work because the time cost of primality testing is too high (cubic in the number of binary digits?), and checking if a string satisfies a regular expression takes only linear time. Since cubic is bigger than linear, this won't work. Too good to be true! Not a proof, but a rule of thumb. No need to even use the pumping lemma.
- thaumasiotes 5y ago> This won't work because the time cost of primality testing is too high This is just a conjecture, though. > No need to even use the pumping lemma. But it's really easy to prove this with the pumping lemma. This could be the first problem in a textbook section that introduces the pumping lemma. It would be difficult to come up with a language for which the pumping lemma disproof was more obvious.
- chakkepolja 5y agoThe canonical example for pumping lemma disproof is a^n b^n, which is more obvious IMO.
- thaumasiotes 5y agoHere are the disproofs: ----- (1) a^n b^n The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n. There are two cases: (1)(a) The number of 'a' characters in y does not equal the number of 'b' characters. In this case, pumping y will violate the constraint that a string in the language must have an equal number of 'a's and 'b's. (1)(b) y consists of k 'a's followed by k 'b's for some k > 0. In this case, pumping it will violate the constraint that for every string in this language, each 'a' character must precede every 'b' character. Thus, the language a^n b^n is not regular. ----- (2) a^n, where n is prime The pumping lemma tells us that for some string in this language, we can divide the string into three substrings x y z such that x y^n z remains in the language for all n. [same as above] But the string x y^|xz| z has length |xz| + |y|*|xz|, which is not prime. Thus, the language a^n (where n is prime) is not regular. ----- Which of those was easier?
- dorianmariefr 5y ago> require "prime" => true > 10.prime? => false
- deleted 5y ago[deleted]
- vbezhenar 5y agoSimpler regexp: ^(11+)\1+$ it does not handle "1" for clarity. I also don't understand why author used `+?`, because simple `+` should work just as well. At least it works in Idea for me.
- MauranKilom 5y agoYeah, should work even with greedy matching as it just does the same checks but in reverse order.
- catlifeonmars 5y agoI wonder which one will reject composite numbers faster. The non greedy version starts with the smallest (potential) factor first, while the greedy version starts with the largest candidate factor first. I suspect that since a factor must be smaller than the square root of a composite, the greedy version you proposed would waste a lot of time checking numbers which could never be factors of the composite under test. If the number is prime, I think both variants have the same performance because they will exhaustively evaluate all numbers less than or equal to the composite under test. Edit: this is not quite correct. One of the prime factors must be smaller than the square root of the composite numbers, but the other one can obviously be larger. For example: 2 * 17 = 34. I’m leaving the original statement as is, because I’m hoping someone with a better math background can chime in and explain if the way that prime factors are distributed is symmetrical or not.
- johnx123-up 5y agoFWIW... Better explanations in 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-... Abigail's other regular expression hacks https://metacpan.org/author/ABIGAIL?sort=[[3,1] https://metacpan.org/author/ABIGAIL?sort=[[3,1]]
- randv 5y agowhile compact and looks elegant... it is basically trying to group by 11 (divide by 2), if there no match (via backtracking) group by 111 (divide by 3) and so on not very efficient by any stretch esp with string matches.
- randv 5y agosteps: - it is turning the number into a string of 1s 3 => 111 4 => 1111 and so on - then trying to simulate divisibility test by trying to find perfect groups of '11' to simulate division by 2 failing which (that is the backtracking part) and trying find perfect groups of '111' to simulate division by 3 and so on... Clever but very inefficient
- bawolff 5y agoThis is interesting - i thought it would be something complex, but really its just using the fundamental meaning of prime. Literally what its doing is turn a number in to all 1s, if the number is 1 return true. Otherwise try all possible ways to put it into 2 or more equal groups, return true once we find one that works. You don't get closer to the definition of "prime" than that.
- rabbits77 5y agoI think it’s worth noting that the original author of the regex primality test is Abigail, a well known Perl hacker. https://www.masteringperl.org/2013/06/how-abigails-prime-number-checker-works/ https://www.masteringperl.org/2013/06/how-abigails-prime-num... This blog article does a nice job discussing Abigail’s work.
- pxeger1 5y agoHere is a regex to check for integer powers of four: https://codegolf.stackexchange.com/a/223129 https://codegolf.stackexchange.com/a/223129 And a regex to integer-divide numbers by the square root of 2: https://codegolf.stackexchange.com/a/198428 https://codegolf.stackexchange.com/a/198428