Hacker News new | comments | show | ask | jobs | submit login

This regular expression is due to Abigail of Perl fame. Who is still very active, see 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. :-)




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)


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.


Yeah, I realized that after the edit link expired. Let's just disambiguate the expression in whatever way makes me look best :)


It's right associative, normally :)


Thank you for answering my anticipated question. I was thinking, "There is some beauty here, but this seems very slow relative to other options."


Some how the beauty of this reminds me of Lambda calculus and Church numerals.


Aha! My memory doesn't fail me... I recall her discussing it on #perl 18 or 19 years ago.




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: