News for hackers. Stuff that matters.

A comment on A regular expression to check for prime numbers. Parent comment

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)
[ Parent | on HN ]
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.
[ Parent | on HN ]
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 :)
[ Parent | on HN ]
Re:A regular expression to check for prime numbers by quadratini on Friday February 13, 2015 @11:06AM (#9045001)
It's right associative, normally :)
[ Parent | on HN ]