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

Status:
Open
Priority:
Normal
Assignee:
-
Target version:
-
[ruby-core:76860]

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:
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

### History

#### Updated by jzakiya (Jabari Zakiya)over 3 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
```

Also available in: Atom PDF