Project

General

Profile

Actions

Feature #12673

open

Performance improvement to Prime.prime? in prime.rb

Added by jzakiya (Jabari Zakiya) about 5 years ago. Updated about 5 years ago.

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

Actions

Also available in: Atom PDF