4 ms·
This regular expression is due to Abigail of Perl fame. Who is still very active, see http://search.cpan.org/~abigail/ http://search.cpan.org/~abigail/ for mor
by btilly 12y ago
This regular expression is due to Abigail of Perl fame. Who is still very active, see http://search.cpan.org/~abigail/ http://search.cpan.org/~abigail/ for more.
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. :-)
- mathattack 12y agoThank you for answering my anticipated question. I was thinking, "There is some beauty here, but this seems very slow relative to other options."
- derekp7 12y agoSome how the beauty of this reminds me of Lambda calculus and Church numerals.
- j2kun 12y agoIt'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)
- nhaehnle 12y agoYou 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.
- quadratini 12y agoIt's right associative, normally :)
- deleted 12y ago[deleted]
- j2kun 12y agoYeah, I realized that after the edit link expired. Let's just disambiguate the expression in whatever way makes me look best :)
- davidw 12y agoAha! My memory doesn't fail me... I recall her discussing it on #perl 18 or 19 years ago.