Skip to content

Instantly share code, notes, and snippets.

@batasrki

batasrki/find_prime.rb

Created July 8, 2009 15:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save batasrki/142907 to your computer and use it in GitHub Desktop.
Save batasrki/142907 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
find_prime.rb
#!/usr/bin/env ruby
require 'mathn'
require 'benchmark'
class FindPrime
attr_accessor :limit
def initialize
@limit = 10001
end
def display
counter = 0
primer = 2
while counter != @limit
counter += 1 if prime_by_trial_division?(primer)
primer += 1
end
end
def library_display
primes = Prime.new
10000.times { primes.next }
end
def performance_test
Benchmark.bm do |x|
x.report("my solution") { display }
x.report("library solution") { library_display }
end
end
def prime_by_trial_division?(num)
r = Math.sqrt(num)
r.to_i.downto(2) do |divisor|
return false if num % divisor == 0
end
return true
end
end
Raw
sum of primes benchmark -- ubuntu
*******************************************************************************************
* This is a simple benchmark proving the suckiness of Ruby 1.8's Prime class on Linux *
* Machine spec: Ubuntu 8.04.2, 2GB RAM, AMD64 3200+ single core *
* It's running ruby 1.8.6 (2007-09-24 patchlevel 111) [i486-linux] *
* *
* First benchmark is hand-rolled trial division solution *
* Second benchmark is a solution using Prime class *
* Last benchmark is hand-rolled Sieve of Eratosthenes *
* *
* I did two runs in the IRB. Please let me know if you need more than that. *
* Enjoy *
*******************************************************************************************
user system total real
up to 10 0.000000 0.000000 0.000000 ( 0.000243)
up to 100 0.000000 0.000000 0.000000 ( 0.002215)
up to 1000 0.030000 0.000000 0.030000 ( 0.039049)
up to 10000 0.580000 0.070000 0.650000 ( 0.652693)
up to 100000 14.230000 1.710000 15.940000 ( 17.480764)
user system total real
library up to 10 0.000000 0.000000 0.000000 ( 0.000121)
library up to 100 0.000000 0.000000 0.000000 ( 0.001206)
library up to 1000 0.030000 0.000000 0.030000 ( 0.036964)
library up to 10000 1.400000 0.070000 1.470000 ( 1.480327)
library up to 100000 82.930000 3.030000 85.960000 (100.499103)
user system total real
eratosthenes up to 10 0.000000 0.000000 0.000000 ( 0.000041)
eratosthenes up to 100 0.000000 0.000000 0.000000 ( 0.000283)
eratosthenes up to 1000 0.000000 0.000000 0.000000 ( 0.003178)
eratosthenes up to 10000 0.040000 0.000000 0.040000 ( 0.038190)
eratosthenes up to 100000 0.330000 0.050000 0.380000 ( 0.397940)
*************************** Second run **********************************************************
user system total real
up to 10 0.000000 0.000000 0.000000 ( 0.000457)
up to 100 0.010000 0.000000 0.010000 ( 0.014356)
up to 1000 0.070000 0.010000 0.080000 ( 0.081559)
up to 10000 1.020000 0.110000 1.130000 ( 1.154933)
up to 100000 14.760000 1.810000 16.570000 ( 18.121784)
user system total real
library up to 10 0.000000 0.000000 0.000000 ( 0.000099)
library up to 100 0.000000 0.000000 0.000000 ( 0.001310)
library up to 1000 0.040000 0.000000 0.040000 ( 0.042729)
library up to 10000 1.480000 0.060000 1.540000 ( 1.737910)
library up to 100000 86.100000 3.250000 89.350000 (100.076218)
user system total real
eratosthenes up to 10 0.000000 0.000000 0.000000 ( 0.000040)
eratosthenes up to 100 0.000000 0.000000 0.000000 ( 0.000283)
eratosthenes up to 1000 0.000000 0.000000 0.000000 ( 0.003179)
eratosthenes up to 10000 0.040000 0.000000 0.040000 ( 0.038020)
eratosthenes up to 100000 0.380000 0.020000 0.400000 ( 0.400469)
Raw
sum of primes benchmark -- windows
*******************************************************************************************
* This is a simple benchmark proving the suckiness of Ruby 1.8's Prime class on Windows *
* Machine spec: Windows XP SP3, 2GB RAM, Intel dual-core 2GHz processor *
* It's running ruby 1.8.6 (2007-09-24 patchlevel 111) [i386-mswin32] *
* *
* First benchmark is hand-rolled trial division solution *
* Second benchmark is a solution using Prime class *
* Last benchmark is hand-rolled Sieve of Eratosthenes *
* *
* I did two runs in the IRB. Please let me know if you need more than that. *
* Enjoy *
*******************************************************************************************
up to 10 0.000000 0.000000 0.000000 ( 0.000000)
up to 100 0.000000 0.000000 0.000000 ( 0.000000)
up to 1000 0.063000 0.000000 0.063000 ( 0.063000)
up to 10000 0.687000 0.000000 0.687000 ( 0.687000)
up to 100000 11.984000 0.016000 12.000000 ( 12.016000)
user system total real
library up to 10 0.000000 0.000000 0.000000 ( 0.000000)
library up to 100 0.000000 0.000000 0.000000 ( 0.000000)
library up to 1000 0.047000 0.000000 0.047000 ( 0.047000)
library up to 10000 1.594000 0.000000 1.594000 ( 1.609000)
library up to 100000 92.391000 0.016000 92.407000 ( 93.766000)
user system total real
eratosthenes up to 10 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 100 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 1000 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 10000 0.031000 0.000000 0.031000 ( 0.031000)
eratosthenes up to 100000 0.344000 0.000000 0.344000 ( 0.344000)
******************************************** Second run *********************************
user system total real
up to 10 0.000000 0.000000 0.000000 ( 0.000000)
up to 100 0.000000 0.000000 0.000000 ( 0.000000)
up to 1000 0.063000 0.000000 0.063000 ( 0.063000)
up to 10000 0.562000 0.031000 0.593000 ( 0.609000)
up to 100000 12.250000 0.015000 12.265000 ( 12.391000)
user system total real
library up to 10 0.000000 0.000000 0.000000 ( 0.000000)
library up to 100 0.000000 0.000000 0.000000 ( 0.000000)
library up to 1000 0.032000 0.000000 0.032000 ( 0.031000)
library up to 10000 1.562000 0.000000 1.562000 ( 1.594000)
library up to 100000 92.828000 0.016000 92.844000 ( 94.125000)
user system total real
eratosthenes up to 10 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 100 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 1000 0.000000 0.000000 0.000000 ( 0.000000)
eratosthenes up to 10000 0.031000 0.000000 0.031000 ( 0.031000)
eratosthenes up to 100000 0.344000 0.000000 0.344000 ( 0.344000)
=> true
Raw
sum_of_primes.rb
#!/usr/bin/env ruby
require 'd:/projects/ruby_programs/lib/find_prime.rb'
require 'benchmark'
require 'mathn'
class SumOfPrimes
attr_accessor :limit
def initialize(limit=2000000)
@limit = limit
end
def sum
fp=FindPrime.new
result = (2...@limit).select {|prime_candidate| fp.prime_by_trial_division?(prime_candidate)}.inject(0) { |start,add| start+add }
end
def sum_library
sum = Prime.new.inject(0) { |sum, n|
break sum unless n < @limit
sum+n
}
end
def sum_eratosthenes
sum = 0
primes = (2..10).to_a
primes.each do |num|
if num
print "#{num}; "
sum += num
value = num*2
print "#{value}; "
while value <= 10
primes[value - 2] = nil
value += num
print "#{value};\n"
end
end
end
sum
end
def performance
Benchmark.bm(15) do |x|
x.report("up to 10") { @limit=10; sum}
x.report("up to 100") { @limit=100; sum}
x.report("up to 1000") { @limit=1000; sum}
x.report("up to 10000") { @limit=10000; sum}
x.report("up to 100000") { @limit=100000; sum}
end
Benchmark.bm(25) do |x|
x.report("library up to 10") { @limit=10; sum_library}
x.report("library up to 100") { @limit=100; sum_library}
x.report("library up to 1000") { @limit=1000; sum_library}
x.report("library up to 10000") { @limit=10000; sum_library}
x.report("library up to 100000") { @limit=100000; sum_library}
end
Benchmark.bm(30) do |x|
x.report("eratosthenes up to 10") { @limit=10; sum_eratosthenes}
x.report("eratosthenes up to 100") { @limit=100; sum_eratosthenes}
x.report("eratosthenes up to 1000") { @limit=1000; sum_eratosthenes}
x.report("eratosthenes up to 10000") { @limit=10000; sum_eratosthenes}
x.report("eratosthenes up to 100000") { @limit=100000; sum_eratosthenes}
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment