Re:A regular expression to check for prime numbers
by j2kun on Thursday February 12, 2015 @06:21PM
(#9042019)
It's even worse, because the speed of factoring algorithms is measured against the number of digits of the binary expansion, and this is a unary expansion. So it's really O(2^n^2)
Re:A regular expression to check for prime numbers
by nhaehnle on Friday February 13, 2015 @08:20AM
(#9044139)
You really have to put parentheses when building "towers" of exponentials. The bound is (2^n)^2, which simplifies to 2^(2n). This is of course still horrible, but much less so than the 2^(n^2) for which what you wrote may be mistaken.
Re:A regular expression to check for prime numbers
by j2kun on Friday February 13, 2015 @11:26AM
(#9045116)
Yeah, I realized that after the edit link expired. Let's just disambiguate the expression in whatever way makes me look best :)
Re:A regular expression to check for prime numbers
by quadratini on Friday February 13, 2015 @11:06AM
(#9045001)
It's right associative, normally :)
Re:A regular expression to check for prime numbers
by mathattack on Thursday February 12, 2015 @05:47PM
(#9041874)
Thank you for answering my anticipated question. I was thinking, "There is some beauty here, but this seems very slow relative to other options."
However while cute, it is very slow. It tries every possible factorization as a pattern match. When it succeeds, on a string of length n that means that n times it tries to match a string of length n against a specific pattern. This is O(n^2). Try it on primes like 35509, 195341, 526049 and 1030793 and you can observe the slowdown. (Some regular expression engines may employ tricks that speed this up over the naive analysis, but none will be super speedy about it.)
Usual arithmetic is much more efficient. :-)