«

* Ken Kunz <> [2005-06-22 07:20:36 +0900]:

> user system total real
> original: 171.767000 0.020000 171.787000 (174.627000)
> Florian's: 2.804000 0.010000 2.814000 ( 2.814000)
> Ken's: 1.041000 0.000000 1.041000 ( 1.042000)

That's better than I expected. I'm not sure why Florian thought
it would be slower.

--
Jim Freeze

Jim Freeze wrote:

>That's better than I expected. I'm not sure why Florian thought
>it would be slower.
>
>
If you compute a sieve to find out, if a very high number is prime...

--
Florian Frank

How about using a better algorithm than Eratosthenes sieve invented
thousands of years ago. In late 2003 a new method was published that
computes the first n primes using binary quadratic forms. This will
give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).

For theoretical description see:
http://www.ams.org/mcom/2004-73-246/...03-01501-1.pdf

And for a sample implementation in C
http://cr.yp.to/primegen.html

cheers,
zsombor
--
http://deezsombor.blogspot.com

irb(main):001:0> require "openssl"
=> true
irb(main):002:0> include OpenSSL
=> Object
irb(main):003:0> a=BN.new("103")
=> 103
irb(main):004:0> a.prime?(10)
=> true
irb(main):005:0> a.prime?(nil)
=> true
irb(main):006:0>


It implements the Miller-Rabin-Test.

See http://www.hmug.org/man/3/BN_is_prime.php




Dee Zsombor schrieb:
> How about using a better algorithm than Eratosthenes sieve invented
> thousands of years ago. In late 2003 a new method was published that
> computes the first n primes using binary quadratic forms. This will
> give an O(n/log(log n)) algorithm, instead of O(n*sqrt(n)).
>
> For theoretical description see:
> http://www.ams.org/mcom/2004-73-246/...03-01501-1.pdf
>
> And for a sample implementation in C
> http://cr.yp.to/primegen.html
>
> cheers,
> zsombor
> --
> http://deezsombor.blogspot.com
>
>
>

Florian Frank wrote:
> And look, I just made the Ruby version, faster, smaller and more object
> oriented:
> ...
> Now do the same in the other two languages...

Okay, here's the Perl version:

#!/usr/bin/perl -w
use Math::Big 'primes';
my $max = 50000;
my $start = time();
my $total = primes($max);
my $time = time() - $start;
print "There are $total primes below $max.\n";
print "Time taken was $time\n";

On my system I get 27 vs. 192 for the original Perl version (which is
not written very perlishly). Sure, this is cheating. CPAN is like
institutionalized cheating, and I love it. In fact, one of the
reasons I started lurking in the Ruby group is that I think Ruby (with
Gems) is closer to developing a CPAN-like system than Python, and thus
I have decided to learn Ruby instead of Python.

- Mark.

On Jun 21, 2005, at 12:55 PM, Michael Tan wrote:

> Just new to Ruby since last week, running my same functional
> program on the windows XP(Pentium M1.5G), the Ruby version is 10
> times slower than the Java version. The program is to find the
> prime numbers like 2, 3,5, 7, 11, 13... Are there setup issues? or
> it is normal?
> 1. Ruby result: 101 seconds
> 2. Java result:9.8 seconds
> 3. Perl result:62 seconds

With some very minor modifications to the original code (I did upto
instead of for and wrapped is_prime in a class), none of which were
algorithmic improvements (ugh):

Modified is_prime code:

class Primer
def is_prime(number)
2.upto(number-1) do |i|
return false if number % i == 0
end
return true
end
end

NORMAL:

% rm -rf ~/.ruby_inline/; ruby primes.rb 50000
There are 5133 primes between 2 and 50000
Time taken 237.315160036087 seconds

(whoa. my laptop is a slowpoke! oh yeah, I'm on battery!)

ONE EXTRA CMD-LINE TOKEN:

% rm -rf ~/.ruby_inline/; ruby -rzenoptimize primes.rb 50000
*** Optimizer threshold tripped!! Optimizing Primer.is_prime
There are 5133 primes between 2 and 50000
Time taken 2.81669783592224 seconds

That said... what did we learn from this thread?

Yes... benchmarks are dumb (see also, 3 lines down)
That there is no accounting for taste (ugliest code/
algorithm ever).
A good algorithm goes a long way.
2/3rds of the ppl are going to mis-analyze anyhow.

... Nothing really.



--
ryand- - Seattle.rb - http://www.zenspider.com/
seattle.rb
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

of course... I spaced out and didn't fix my subject line.

--
ryand- - Seattle.rb - http://www.zenspider.com/
seattle.rb
http://blog.zenspider.com/ - http://rubyforge.org/projects/ruby2c

As far as I understood from Miller-Rabin-Test is for determining if a
number is prime with a _given_ _probability_. It is a very efficient
algortithm for that.
The Atkins sieve (binary quadratic forms) is about generating all
primes less than given number. And that is an entirely different
problem, even if you woud do MR in a loop you would not get the same
results as Atkin sieve.

As far as I understood from Miller-Rabin-Test is for determining if a
number is prime with a _given_ _probability_. It is a very efficient
algortithm for that.
The Atkins sieve (binary quadratic forms) is about generating all
primes less than given number. And that is an entirely different
problem, even if you woud do MR in a loop you would not get the same
results as Atkin sieve.

--
http://deezsombor.blogspot.com

On Wed, Jun 22, 2005 at 10:50:36PM +0900, Mark Thomas wrote:
> Okay, here's the Perl version:
>
> #!/usr/bin/perl -w
> use Math::Big 'primes';
> my $max = 50000;
> my $start = time();
> my $total = primes($max);
> my $time = time() - $start;
> print "There are $total primes below $max.\n";
> print "Time taken was $time\n";
>
> On my system I get 27 vs. 192 for the original Perl version (which is
> not written very perlishly). Sure, this is cheating. CPAN is like
> institutionalized cheating, and I love it. In fact, one of the
> reasons I started lurking in the Ruby group is that I think Ruby (with
> Gems) is closer to developing a CPAN-like system than Python, and thus
> I have decided to learn Ruby instead of Python.

It's perhaps worth mentioning that although Ruby is about 1/3rd of the size
of Perl, it has a far more complete standard library.

A base Ruby install includes, amongst other things: SSL, base64 encoding/
decoding, MD5/SHA1 hashing, XML/YAML parsing, HTTP client and server, and
remote method calls (DRb, SOAP, XMLRPC).

I think recent version of Perl have accumulated MIME::Base64, but the others
are still extensions you have to download and install.