From: jzakiya@... Date: 2016-08-13T20:57:36+00:00 Subject: [ruby-core:76862] [Ruby trunk Feature#12673] Performance improvement to Prime.prime? in prime.rb Issue #12673 has been updated by 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 ``` ---------------------------------------- Feature #12673: Performance improvement to Prime.prime? in prime.rb https://bugs.ruby-lang.org/issues/12673#change-60087 * Author: Jabari Zakiya * Status: Open * Priority: Normal * Assignee: ---------------------------------------- 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 -- https://bugs.ruby-lang.org/ Unsubscribe: