Optimizing prime-number detection by short-circuiting when a zero remainder is found

prime_detector.rb

require 'benchmark'
require 'prime'

class Integer
  def simple_prime?
    (2..Math.sqrt(self).floor).all? { |i| (self % i).nonzero? }
  end

  def clever_prime?
    return true  if self == 2
    return false if self.even?
    3.step(Math.sqrt(self).floor, 2).all? { |i| (self % i).nonzero? }
  end

  def short_circuit_prime?
    return true  if self == 2
    return false if self.even?
    !3.step((self ** 0.5).floor, 2).find { |i| (self % i).zero? }
  end
end

range = 2..1_000_000

Benchmark.bmbm do |bench|
  bench.report('simple:') { range.each &:simple_prime? }
  bench.report('clever:') { range.each &:clever_prime? }
  bench.report('short circuit:') { range.each &:short_circuit_prime? }
  bench.report('stdlib:') { range.each &:prime?        }
end

Results: Short-circuit method is almost 29% faster than clever method

Rehearsal --------------------------------------------------
simple:         68.760000   0.160000  68.920000 ( 72.631534)
clever:         35.560000   0.130000  35.690000 ( 39.200709)
short circuit:  26.340000   0.050000  26.390000 ( 27.931216)
stdlib:         89.790000   0.310000  90.100000 ( 97.839364)
--------------------------------------- total: 221.100000sec

                     user     system      total        real
simple:         68.740000   0.140000  68.880000 ( 72.799588)
clever:         35.680000   0.110000  35.790000 ( 38.660648)
short circuit:  26.890000   0.050000  26.940000 ( 28.111847)
stdlib:         90.980000   0.230000  91.210000 ( 97.697757)

Thanks! Interesting – it’s not the #all? to #find change (#all? is short-circuiting, as #any? and #none?), it’s the #nonzero? being slower than #zero? – check this one:

class Integer
  def clever_prime?
    return true  if self == 2
    return false if self.even?
    3.step(Math.sqrt(self).floor, 2).none? { |i| (self % i).zero? }
  end
end

(Which might make sense, as #zero? returns true or false, whereas #nonzero? returns nil or the value itself so it can be chained in #<=> implementations.)

Related: http://talks.chastell.net/src-2011/#131 :)

That is interesting. I didn't think about #all? short circuiting when it hits a falsy value. I was thinking of it along the lines of Array#select vs Array#detect.

I did find a pretty slight improvement going from #any? to #find, though. It was just a few percent, probably due to not having to convert truthy/falsy values into actual true and false.

Also, another thing that surprised me was that switching from Math.sqrt(self) to self ** 0.5 gave a pretty big boost. Switching your code above to use it knocked about a second off on my machine under Rubinius (far less pronounced on MRI 2.0, though).