From: jzakiya@...
Date: 2016-08-13T15:06:57+00:00
Subject: [ruby-core:76860] [Ruby trunk Feature#12673] Performance improvement to Prime.prime? in prime.rb

Issue #12673 has been reported by Jabari Zakiya.

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

* 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: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>