Wow. This guy just rewrote my exegesis of a Perl one-liner from about seven years ago. He links to the original, but his much more verbose explanation adds little.
Every now and then somebody rediscovers this, and in latter years it's made the social news sites regularly. And it's not even hosted on my own site! That's HTML somebody else made from a mailing list post, long before I ever blogged. I guess I peaked early.
Oh, and DUH: the point is not that one should use regular expressions for computation. It's to underscore that regexes are automata. And, it's kind of fun to unravel some of the obfuscation.
Remember: The fact that you CAN us a regular expression doesn't mean that you SHOULD. I'm sure this isn't the slowest possible way to detect primes, but I honestly can't think of a slower way right now. [EDIT: Ok, I can now see how to detect primes in superexponential time by simulating a Turing machine.]
In general, the more powerful a tool is, the slower it is. Good coding requires understanding how much power you need and using the right tool -- not waving a sledgehammer around because you've discovered that it can solve all of your problems.
> Regular expressions are equivalent to finite automata... That's not very powerful.
True. I was using the (incorrect) terminology of the article, wherein "regular expression" really means "irregular expression". Regular expressions are fine and can be matched quickly; throw in backreferences and you have a tool which is both very powerful (and can detect primes) and can be exceedingly slow.
http://montreal.pm.org/tech/neil_kandalgaonkar.shtml
Every now and then somebody rediscovers this, and in latter years it's made the social news sites regularly. And it's not even hosted on my own site! That's HTML somebody else made from a mailing list post, long before I ever blogged. I guess I peaked early.
Oh, and DUH: the point is not that one should use regular expressions for computation. It's to underscore that regexes are automata. And, it's kind of fun to unravel some of the obfuscation.