Skip to content

Instantly share code, notes, and snippets.

@matchu
Created September 16, 2012 16:45
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 matchu/3733152 to your computer and use it in GitHub Desktop.
Save matchu/3733152 to your computer and use it in GitHub Desktop.
benchmark prime validators
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
@matchu
Copy link
Author

matchu commented Sep 17, 2012

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment