benchmark prime validators

gistfile1.rb

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