Feature #12673: Performance improvement to Prime.prime? in prime.rb

• Status: Closed
• Assignee: -
• Target version: -

[jzakiya (Jabari Zakiya)]

The following code change provides a significant speed increase for Prime.prime? in prime.rb.

class Prime
  ...
  ...

  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2

    generator.each do |num|             sqrt_n = Math.sqrt(value).to_i
      q,r = value.divmod num            while (gp = generator.next) <= sqrt_n
      return true if q < num               return false if value % gp == 0
      return false if r == 0            end
    end                                 true
  end                                 end
  ...
  ...
end

Pros:

1. Performs fewer mathematical computations and comparisons
2. Thus is significantly faster than current technique
3. Has same number of lines-of-code
4. Is applicable to any generator
5. Uses similar technique as in Integer::prime? in prime.rb

Cons:
None

[jzakiya (Jabari Zakiya)]

After doing more testing of alternative techniques, for CRuby and JRuby,
here are some timing results on CRuby 2.3.1 on 64-bit Linux OS on
System76 I7 3.5GHz laptop with 16GB ram.

Version 1) the current code for prime? in class Prime in prime.rb, is the slowest
in CRuby and JRuby.

Version 2) is faster than 1) in [C|J]Ruby, but slower than 3) for CRuby

Version 3) is fastest in CRuby, but slowest in JRuby (because it
does while loops the worst of all the looping constructs).

Version 4) the current prime? in class Integer, is the fastest in both [C|J]Ruby.

So the question becomes to me, what is the purpose of having two methods in the
same file that perform the same function, but have signficant performance differences?

Why not use the much faster Integer version in class Prime, if you really need/want one there?

class Prime
  def prime? (value)
     value.prime?
  end
end

I am trying to understand the necessity of this redundancy of functionality.
I don't see why anyone would use the much slower Prime.prime?(n) construct over doing n.prime?

Could someone please explain the rationale for this.

irb(main):002:0> def tm; s=Time.now; yield; Time.now-s end
=> :tm

1) Original, and slowest, implementation of Prime.prime? in prime.rb, for CRuby and JRuby

class Prime
  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2

    generator.each do |num|
      q,r = value.divmod num
      return true if q < num
      return false if r == 0
    end
end
 
irb(main):004:0> n =   100_000_000_000_000_003; tm{ Prime.prime? n }
=> 19.976400647
irb(main):005:0> n =   200_000_000_000_000_003; tm{ Prime.prime? n }
=> 28.067153331
irb(main):006:0> n = 1_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 63.159005711
irb(main):007:0> n = 5_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 235.396632104


2) A faster implementation of Prime.prime? in prime.rb, for both CRuby and JRuby.

class Prime
  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2
    
    sqrt_n = Math.sqrt(value).to_i
    generator.each do |num|
      return true  if num > sqrt_n
      return false if value % num == 0
    end
end

irb(main):008:0> n =   100_000_000_000_000_003; tm{ Prime.prime? n }
=> 14.169731005
irb(main):009:0> n =   200_000_000_000_000_003; tm{ Prime.prime? n }
=> 20.264718577
irb(main):010:0> n = 1_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 45.985622043
irb(main):011:0> n = 5_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 193.274088194


3) Fastest implementation of Prime.prime? in prime.rb, for CRuby, but slowest for JRuby,
   because JRuby does while loops really slow compared to other looping structures
   
class Prime
  def prime?(value, generator = Prime::Generator23.new)
    raise ArgumentError, "Expected a prime generator, got #{generator}" unless generator.respond_to? :each
    raise ArgumentError, "Expected an integer, got #{value}" unless value.respond_to?(:integer?) && value.integer?
    return false if value < 2

    sqrt_n = Math.sqrt(value).to_i
    while (pc = generator.next) <= sqrt_n
      return false if value % pc == 0
    end 
    true
end

irb(main):003:0> n =   100_000_000_000_000_003; tm{ Prime.prime? n }
=> 9.354626367
irb(main):004:0> n =   200_000_000_000_000_003; tm{ Prime.prime? n }
=> 12.827152622
irb(main):005:0> n = 1_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 28.223534973
irb(main):006:0> n = 5_000_000_000_000_000_003; tm{ Prime.prime? n }
=> 148.168372529


4) Current implementation of Integer::prime? in prime.rb; fastest for both [C|J]Ruby.

 class Integer
   def prime?
     return self >= 2 if self <= 3
     return false if self % 2 == 0 or self % 3 == 0
     (5..(self**0.5).floor).step(6).each do |i|
       if self % i == 0 || self % (i + 2) == 0
         return false
       end
     end
   end
 end

irb(main):011:0> n =   100_000_000_000_000_003; tm{ n.prime? }
=> 4.029015084
irb(main):012:0> n =   200_000_000_000_000_003; tm{ n.prime? }
=> 5.686641653
irb(main):013:0> n = 1_000_000_000_000_000_003; tm{ n.prime? }
=> 12.738684879
irb(main):014:0> n = 5_000_000_000_000_000_003; tm{ n.prime? }
=> 123.476314978

[hsbt (Hiroshi SHIBATA)]

• Status changed from Open to Closed

prime.rb is extracted to https://github.com/ruby/prime as the bundled gems.