[ruby-core:106273] [Ruby master Feature#12673] Performance improvement to Prime.prime? in prime.rb

Issue #12673 has been updated by hsbt (Hiroshi SHIBATA).

Status changed from Open to Closed

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



----------------------------------------
Feature #12673: Performance improvement to Prime.prime? in prime.rb
https://bugs.ruby-lang.org/issues/12673#change-94895

* Author: jzakiya (Jabari Zakiya)
* Status: Closed
* Priority: Normal
----------------------------------------
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: <mailto:[e-mail]?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>