Feature #12673
closedPerformance improvement to Prime.prime? in prime.rb
Description
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:
- Performs fewer mathematical computations and comparisons
- Thus is significantly faster than current technique
- Has same number of lines-of-code
- Is applicable to any generator
- Uses similar technique as in Integer::prime? in prime.rb
Cons:
None
Updated by jzakiya (Jabari Zakiya) about 8 years ago
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
Updated by hsbt (Hiroshi SHIBATA) almost 3 years ago
- Status changed from Open to Closed
prime.rb is extracted to https://github.com/ruby/prime as the bundled gems.