3 ms·
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 hone
by cperciva 19y ago
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.
- eru 19y agoRegular expressions are equivalent to finite automata. (At least in their purer forms like the one defined in http://en.wikipedia.org/wiki/Regular_expression#Formal_language_theory http://en.wikipedia.org/wiki/Regular_expression#Formal_langu...) That's not very powerful. Edit: The expression in the articles seems to use some 'practical' extensions.
- cperciva 19y ago> 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.
- eru 19y agoI wonder if those 'irregular expressions' are already lambda isomorph (or say Turing complete if you like).
- almost 19y agoThanks captain obvious!