public
Created

benchmark prime validators

  • Download Gist
gistfile1.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
require 'benchmark/ips'
require 'prime'
 
def isPrimeRegexp n
"1" * n =~ /^1?$|^(11+?)\1+$/
end
 
def isPrime(number)
if number == 0 or number == 1
return false
end
 
i = 2
limit = number / i
while i < limit
if number % i == 0
return false
end
i += 1
limit = number / i
end
return true
end
 
def compute_sieve(n)
sieve = Array.new(n-1, true)
# cross off numbers in the sieve who fail
(2..Math.sqrt(n)).each do |i|
if sieve[i-2]
(i*i..n).step(i) do |j|
sieve[j-2] = false
end
end
end
sieve
end
 
def single_sieve(n)
compute_sieve(n)[n-2]
end
 
@sieve_upper = 0
@sieve = nil
 
def cached_sieve(n)
if n > @sieve_upper
@sieve = compute_sieve(n)
@sieve_upper = n
end
@sieve[n-2]
end
 
g = Random.new
 
Benchmark.ips do |r|
r.report('isPrimeRegexp') do
isPrimeRegexp(g.rand(2..1000))
end
 
r.report('isPrime') do
isPrime(g.rand(2..1000))
end
r.report('single_sieve') do
single_sieve(g.rand(2..1000))
end
r.report('cached_sieve') do
cached_sieve(g.rand(2..1000))
end
r.report('stdlib') do
g.rand(2..1000).prime?
end
end
Calculating -------------------------------------
       isPrimeRegexp      1539 i/100ms
             isPrime     68380 i/100ms
        single_sieve      1155 i/100ms
        cached_sieve     93674 i/100ms
              stdlib     17267 i/100ms
-------------------------------------------------
       isPrimeRegexp    16515.5 (±7.4%) i/s -      83106 in   5.059397s
             isPrime  1269990.1 (±2.6%) i/s -    6359340 in   5.011132s
        single_sieve    11649.7 (±2.8%) i/s -      58905 in   5.060345s
        cached_sieve  2658561.1 (±3.0%) i/s -   13301708 in   5.008759s
              stdlib   208393.5 (±3.7%) i/s -    1053287 in   5.061332s

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.