From: Michael Brooks <michael.brooks@...>
Date: 2008-04-01T10:00:06+09:00
Subject: Re: Primes in P?

Charles Zheng wrote:
> There is an algorithm that tests primes with a polynomial running time:
> http://fatphil.org/maths/AKS/
> 
> Has anyone coded it in Ruby?

Hello Charles:

My head hurt trying to understand the wikipedia description for 
polynomial time so I stopped read it.  That aside, a cool algorithm was 
pointed out by Tim Pease in March of 2007.  It uses regular expressions 
to achieve, to a point, non-exponential solving times for prime numbers.

Here is an example of that algorithm demonstrated via a method which 
extends the Fixnum class.

class Fixnum
   def is_prime?
     ((("1" * self) =~ /^1$|^(11+?)\1+$/) == nil)
   end
end

irb(main):009:0> 2.is_prime?
=> true
irb(main):010:0> 113.is_prime?
=> true
irb(main):008:0> 123457.is_prime?
=> true

The turnaround time on solving is almost instantaneous for this 
algorithm until the numbers start gets really big (i.e. like the 123457 
above).  I don't know if this matches the criteria for "polynomial 
running time" but thought you might find this interesting if you didn't 
know about it.

Tim made reference to this web site for credit:

http://montreal.pm.org/tech/neil_kandalgaonkar.shtml

I used the above example to demonstrated Ruby's ability to modify base 
classes and support advanced regular expressions to a Python programming 
friend.  He was both impressed and a little confused by the example :) 
Prior to using this Ruby trick the equivalent Python program was about 
2.25 times faster when solving into the low 100s on Windows.  After 
using this trick the Ruby program was 1.1 times faster than Python which 
couldn't do the same trick according to my friend.  FYI, both Ruby and 
Python were still 32 times slow than CodeGear's Delphi even though 
Delphi didn't use the regular expression trick.

Michael