From: "Jabari Z." <lists@...>
Date: 2013-07-30T23:58:20+09:00
Subject: Re: Faster primality testing and factorization methods in Ruby

Kiswono Prayogo wrote in post #1117124:
> ah yeah, on 32-bit it's really-really slow.. (trying on my more powerful
> PC
> instead of my old laptop for now)
>
> soo.. the conclusion would be: Miller-Rabin is the fastest
>
> http://pastie.org/8189939
>
> ruby: 343s
> jruby: 284s

First, thanks to all who have run my code on their systems.

It would be really helpful if you would site your system specs for
comparison purposes. Please provide this minimal system spec info:

Ruby version: ruby-2.0.0-p247, jruby-1.7.4, etc
CPU spec: Intel I5, 4 core, 2.4 GHz, etc.
OS: Linux Mint 14 64-bit, etc

It would be nice to see the performance across a range of hardware
(Intel, AMD, Power PC, etc) and OSs (Linux, OS X, Windows, etc)

Also Miller-Rabin is a probabilistic primality test, which I provided
for comparison. This means it can/will give incorrect answers to some
odd composites (especially odds > 10^16). See more at Miller-Rabin liks:

https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

All my algorithms are deterministic (answers are 100% true or false).

They also lend themselves to parallel implementations.

My primality test algorithms came out of work I originally began on
creating and understanding prime generators and using them to create
prime sieves (finding all primes up to some number N). See my Sieve of
Zakiya, which is faster/more efficient than the Sieve of Eratosthenes,
et al.

http://www.scribd.com/doc/73384039/Ultimate-Prime-Sieve-Sieve-Of-Zakiya
http://www.scribd.com/doc/73385696/The-Sieve-of-Zakiya

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