Instantly share code, notes, and snippets.

# matchu/gist:3733152 Created Sep 16, 2012

What would you like to do?
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
Owner

### 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 ``````