[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Primes in P?

Charles Zheng

3/31/2008 2:43:00 PM

There is an algorithm that tests primes with a polynomial running time:
http://fatphil.org/...

Has anyone coded it in Ruby?
--
Posted via http://www.ruby-....
12 Answers

Kyle Schmitt

3/31/2008 3:43:00 PM

0

Well, I'm gonna guess that if anyone has, they would post it on that website.
I can't get to the original paper (server's offline, file removed?),
but a cursory overview of the c++ implementations makes me think a
decent ruby hacker could pound out an implementation in an afternoon.

Why don't you code it, post it here for everyone to enjoy, and to that website?

--Kyle

On Mon, Mar 31, 2008 at 9:42 AM, Charles Zheng <snarles2@gmail.com> wrote:
> There is an algorithm that tests primes with a polynomial running time:
> http://fatphil.org/...
>
> Has anyone coded it in Ruby?
> --
> Posted via http://www.ruby-....
>
>

Todd Benson

3/31/2008 4:43:00 PM

0

On Mon, Mar 31, 2008 at 10:42 AM, Kyle Schmitt <kyleaschmitt@gmail.com> wrote:
> Well, I'm gonna guess that if anyone has, they would post it on that website.
> I can't get to the original paper (server's offline, file removed?),

For those of you interested in tackling this monster...

http://en.wikipedia.org/wiki/AKS_prim...

I'll try my hand at it eventually, but I don't think I could do it in
an afternoon.

Todd

Todd Benson

3/31/2008 5:35:00 PM

0

On Mon, Mar 31, 2008 at 11:43 AM, Todd Benson <caduceass@gmail.com> wrote:

> I'll try my hand at it eventually, but I don't think I could do it in
> an afternoon.

Scratch that. I found a way to sort of "cheat" using a stdlib. But,
I think you should try it the hard way for fun.

Todd

Michael Brooks

4/1/2008 12:55:00 AM

0

Charles Zheng wrote:
> There is an algorithm that tests primes with a polynomial running time:
> http://fatphil.org/...
>
> 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_kandalgao...

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

Charles Zheng

4/1/2008 2:23:00 AM

0

Michael Brooks wrote:
> Hello Charles:
>
> 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
...
> 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.
> Michael

That is pretty cool. It is not of polynomial running time since it tries
to factor the number brute-force, but that is a very nifty reg EXP
trick.
--
Posted via http://www.ruby-....

Xavier Noria

4/1/2008 8:17:00 AM

0

On Apr 1, 2008, at 4:23 , Charles Zheng wrote:

>> ((("1" * self) =~ /^1$|^(11+?)\1+$/) == nil)
>> end
>> end
> ...
>> 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.
>> Michael
>
> That is pretty cool. It is not of polynomial running time since it
> tries
> to factor the number brute-force, but that is a very nifty reg EXP
> trick.

The author is Perl hacker Abigail, it first appeared in
comp.lang.perl.misc:

-- fxn

Todd Benson

4/1/2008 10:20:00 AM

0

On Mon, Mar 31, 2008 at 9:23 PM, Charles Zheng <snarles2@gmail.com> wrote:
> Michael Brooks wrote:
> > Hello Charles:
>
> >
> > 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
> ...
>
> > 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.
> > Michael
>
> That is pretty cool. It is not of polynomial running time since it tries
> to factor the number brute-force, but that is a very nifty reg EXP
> trick.

Charles, take a peak at the mathn library for your greatest prime factor...

require 'mathn'
n = 12345654321
p n.prime_division.last[0]

hth a little,
Todd

Todd Benson

4/1/2008 12:07:00 PM

0

On Tue, Apr 1, 2008 at 5:19 AM, Todd Benson <caduceass@gmail.com> wrote:

>
> Charles, take a peak at the mathn library for your greatest prime factor...
>
> require 'mathn'
> n = 12345654321
> p n.prime_division.last[0]

Funny, I tried this with the same number with a 1 attached to the end
(123456543211). It took about 20 minutes, but determined it was prime
(i.e. returned [123456543211, 1]) which means 123456543211 to the
power of 1. Coincidence :)

Todd

Todd Benson

4/1/2008 2:16:00 PM

0

On Tue, Apr 1, 2008 at 5:19 AM, Todd Benson <caduceass@gmail.com> wrote:
>
> On Mon, Mar 31, 2008 at 9:23 PM, Charles Zheng <snarles2@gmail.com> wrote:
> > Michael Brooks wrote:
> > > Hello Charles:
> >
> > >
> > > 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
> > ...
> >
> > > 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.
> > > Michael
> >
> > That is pretty cool. It is not of polynomial running time since it tries
> > to factor the number brute-force, but that is a very nifty reg EXP
> > trick.
>
> Charles, take a peak at the mathn library for your greatest prime factor...
>
> require 'mathn'
> n = 12345654321
> p n.prime_division.last[0]

Oh, btw, "n" was a bad choice of variable name here if you go by the
wikipedia article. In their notation, you want to find the greatest
prime factor of (r-1).

Just pointing out what probably is obvious.

cheers,
Todd

Jimmy Kofler

4/16/2008 7:37:00 AM

0

> Posted by Todd Benson (Guest) on 01.04.2008 14:08
>
>> On Tue, Apr 1, 2008 at 5:19 AM, Todd Benson <caduceass@gmail.com> wrote:
>>
>>
>> Charles, take a peak at the mathn library for your greatest prime factor...
>>
>> require 'mathn'
>> n = 12345654321
>> p n.prime_division.last[0]
>
> Funny, I tried this with the same number with a 1 attached to the end
> (123456543211). It took about 20 minutes, but determined it was prime
> (i.e. returned [123456543211, 1]) which means 123456543211 to the
> power of 1. Coincidence :)
>
> Todd


Well, you could use the Miller-Rabin prime test for a speed up! See:

http://snippets.dzone.com/posts...

You may check the outcome with primegen, http://cr.yp.to/pri...

time -p primes 123456543211 123456543211 # done in well under a second

Cheers,
j. k.


--
Posted via http://www.ruby-....