6 ms·

For some this will be obvious, but for others it may still be interesting: If this was a "true" regular expression, in the sense that it describes a regular la

by anyfoo 12y ago

For some this will be obvious, but for others it may still be interesting: If this was a "true" regular expression, in the sense that it describes a regular language (http://en.wikipedia.org/wiki/Regular_language http://en.wikipedia.org/wiki/Regular_language), then checking whether the number is prime or not, by checking if the expression matches, would run in linear time. This would be worth a few nobel prizes at least. Unfortunately, it is an "extended" regular expression, i.e. not regular at all in the strictest sense, and (as the article says) requires backtracking.

btilly 12y ago
Not true! First of all there is no Nobel in math/CS. But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting. And a better primality test would not rock the world of cryptography. At the moment http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_... is demonstrably good enough as a prime test that nobody really is hurting for better ones. The thing that you want is a better factoring algorithm. And the General Number Sieve is already subexponential, and so better than any regular expression could be.
- web007 12y ago
  M-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a better test, so we have Lucas-Lehmer and APRT-CL and AKS. Better primality testing would be interesting to the crypto community, but it could rock the math world - like "Primes is in P" introducing AKS as the first deterministic polynomial time primality test. As you said, though, better factoring would be game-changing for both cryptography AND mathematics.
  - raiph 12y ago
    I've heard that, on modern cpus, with the first 100 or so primes cached, for all but the most performance sensitive applications, MR can be run with sufficient accuracy that there's a greater likelihood that a stray neutron will flip a bit in the cpu at the time of computing MR than that MR will produce an incorrect result. Or something like that. Is it true than MR can be tuned to be as useful as a non-probabilistic test?
    - btilly 12y ago
      This is absolutely true. Every time you run it, a non-prime has probability of at most 1/4 of passing. Run it 5 times, and you'll catch 99.9% of non-primes. What about neutron flips? Judging from http://lambda-diode.com/opinion/investigations/transmutations/.../ecc-memory-3 http://lambda-diode.com/opinion/investigations/transmutation... you can probably expect one every 4-5 years. If you run MR 20 times, your odds of wrongly declaring a non-prime prime are on the same order of magnitude as the number of microseconds in a 5 year period. So yes, neutron flips and MR errors are on par with each other. If you're concerned, just run MR a few more times. :-)
- cperciva 12y ago
  First of all there is no Nobel in math/CS. He didn't say it would win a Nobel prize, just that it would be worth a few Nobel prizes. A major breakthrough in algorithmic theory could easily result in someone winning a Fields medal, and I'd say that's easily worth more than a Nobel prize.
- anyfoo 12y ago
  First of all there is no Nobel in math/CS. I know. An algorithm this efficient would still be worth that much. :) But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting. No, the regular expression described here works on numbers in unary representation. Linear to the size of the unary representation is linear to the number itself.
  - sold 12y ago
    Unary representation is useless when speaking about complexity in number theory. If you take a number N given in unary, convert it to binary and do trial division up to the square root, it will take O(N log N) time for conversion to binary and O(sqrt(N) * log(N)^2) for trial division (depending on your computational model, it could be O(N) and O(sqrt(N)) - I am counting bit complexity). In total, it's O(N log N). The runtime is dominated by reading the input! The complexity of trial division and the brilliant AKS algorithm is the same from this viewpoint. Even if you had an algorithm that did not have to convert to binary and could tell in time linear to unary represenation whether a number is prime, it would be interesting trivia but nothing worthy a Nobel prize. In practice numbers are given in binary (or some other base>1 number system). To use your algorithm, you would have to convert to unary, which already means trial division would be faster.
    - anyfoo 12y ago
      Ah, I see, thanks for the explanation.
marvin 12y ago
In other words, this is not a regular expression as defined mathematically, i.e. equivalent to a specific finite-state machine?
- beagle3 12y ago
  Not a regular language as mathematically defined. Unfortunately, quite a few very-well-defined terms have been made much-less-defined by use in practice. "regular expression" has come to mean "anything that can be specified by a Perl 'RE' expression, which can backtrack and may take exponential time", rather than the original precise definition (that I will not give here) equivalent to "anything that can be accepted by a memoryless finite state automaton" Similarly, "real time" has come to mean "on-line" or "computation happening more or less at the same time input is generated", as opposed to the original meaning of "guaranteed response to input within a pre-specified time frame" (which has been relegated to being "hard real time", with the amortized version often called "soft real time"). One could think software construction, being somewhat of an engineering discipline, would be more precise with terms - but one would be wrong; software construction as practiced today is something between an art and a craft, and is mostly not related to engineering.
  - cogburnd02 12y ago
    > the original precise definition (that I will not give here) I'll give it: the regular expression syntax acceptable to (n)awk. (and Perl, etc.)
  - deleted 12y ago
    [deleted]
Chinjut 12y ago
It's also worth noting that what this expression matches are not primes given in decimal notation; rather, the language it accepts is "111...111" with any prime number of 1s. And we know straight-up that no "true" regular expression matches this language, by the pumping lemma (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...).
wyager 12y ago
There does not exist a "true" regular expression (i.e. a FSM) to check if a number is prime. Proving this is a common assignment in automata theory classes.

by anyfoo 12y ago

btilly 12y ago

Not true! First of all there is no Nobel in math/CS. But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting. And a better primality test would not rock the world of cryptography. At the moment http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_... is demonstrably good enough as a prime test that nobody really is hurting for better ones. The thing that you want is a better factoring algorithm. And the General Number Sieve is already subexponential, and so better than any regular expression could be.

web007 12y ago
M-R is a probabilistic primality test, with a deterministic variant for some ranges and a general-deterministic variant dependent on GRH. Lots of people want a better test, so we have Lucas-Lehmer and APRT-CL and AKS. Better primality testing would be interesting to the crypto community, but it could rock the math world - like "Primes is in P" introducing AKS as the first deterministic polynomial time primality test. As you said, though, better factoring would be game-changing for both cryptography AND mathematics.
- raiph 12y ago
  I've heard that, on modern cpus, with the first 100 or so primes cached, for all but the most performance sensitive applications, MR can be run with sufficient accuracy that there's a greater likelihood that a stray neutron will flip a bit in the cpu at the time of computing MR than that MR will produce an incorrect result. Or something like that. Is it true than MR can be tuned to be as useful as a non-probabilistic test?
  - btilly 12y ago
    This is absolutely true. Every time you run it, a non-prime has probability of at most 1/4 of passing. Run it 5 times, and you'll catch 99.9% of non-primes. What about neutron flips? Judging from http://lambda-diode.com/opinion/investigations/transmutations/.../ecc-memory-3 http://lambda-diode.com/opinion/investigations/transmutation... you can probably expect one every 4-5 years. If you run MR 20 times, your odds of wrongly declaring a non-prime prime are on the same order of magnitude as the number of microseconds in a 5 year period. So yes, neutron flips and MR errors are on par with each other. If you're concerned, just run MR a few more times. :-)
cperciva 12y ago
First of all there is no Nobel in math/CS. He didn't say it would win a Nobel prize, just that it would be worth a few Nobel prizes. A major breakthrough in algorithmic theory could easily result in someone winning a Fields medal, and I'd say that's easily worth more than a Nobel prize.
anyfoo 12y ago
First of all there is no Nobel in math/CS. I know. An algorithm this efficient would still be worth that much. :) But more importantly, when we talk about the running time of algorithms, we talk about the time in relation to how many bits it takes to describe the number. So linear in the size of the number is exponential in the number of bits, and that is not very interesting. No, the regular expression described here works on numbers in unary representation. Linear to the size of the unary representation is linear to the number itself.
- sold 12y ago
  Unary representation is useless when speaking about complexity in number theory. If you take a number N given in unary, convert it to binary and do trial division up to the square root, it will take O(N log N) time for conversion to binary and O(sqrt(N) * log(N)^2) for trial division (depending on your computational model, it could be O(N) and O(sqrt(N)) - I am counting bit complexity). In total, it's O(N log N). The runtime is dominated by reading the input! The complexity of trial division and the brilliant AKS algorithm is the same from this viewpoint. Even if you had an algorithm that did not have to convert to binary and could tell in time linear to unary represenation whether a number is prime, it would be interesting trivia but nothing worthy a Nobel prize. In practice numbers are given in binary (or some other base>1 number system). To use your algorithm, you would have to convert to unary, which already means trial division would be faster.
  - anyfoo 12y ago
    Ah, I see, thanks for the explanation.

marvin 12y ago

In other words, this is not a regular expression as defined mathematically, i.e. equivalent to a specific finite-state machine?

beagle3 12y ago
Not a regular language as mathematically defined. Unfortunately, quite a few very-well-defined terms have been made much-less-defined by use in practice. "regular expression" has come to mean "anything that can be specified by a Perl 'RE' expression, which can backtrack and may take exponential time", rather than the original precise definition (that I will not give here) equivalent to "anything that can be accepted by a memoryless finite state automaton" Similarly, "real time" has come to mean "on-line" or "computation happening more or less at the same time input is generated", as opposed to the original meaning of "guaranteed response to input within a pre-specified time frame" (which has been relegated to being "hard real time", with the amortized version often called "soft real time"). One could think software construction, being somewhat of an engineering discipline, would be more precise with terms - but one would be wrong; software construction as practiced today is something between an art and a craft, and is mostly not related to engineering.
- cogburnd02 12y ago
  > the original precise definition (that I will not give here) I'll give it: the regular expression syntax acceptable to (n)awk. (and Perl, etc.)
- deleted 12y ago
  [deleted]

Chinjut 12y ago

It's also worth noting that what this expression matches are not primes given in decimal notation; rather, the language it accepts is "111...111" with any prime number of 1s. And we know straight-up that no "true" regular expression matches this language, by the pumping lemma (http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_langu...).

wyager 12y ago

There does not exist a "true" regular expression (i.e. a FSM) to check if a number is prime. Proving this is a common assignment in automata theory classes.