Project

General

Profile

Feature #10354

Optimize Integer#prime?

Added by marcandre (Marc-Andre Lafortune) about 3 years ago. Updated about 2 years ago.

Status:
Closed
Priority:
Normal
Target version:
-
[ruby-core:65580]

Description

Nick Slocum shows in https://github.com/ruby/ruby/pull/736 that Integer#prime? can be optimized quite a bit.

First, that's because there are some basic things to avoid in the current lib, like needlessly capturing blocks and there's a useless loop do too.

I'm attaching a patch that fixes many of these things.

Even after these fixes applied, Nick's version is still faster and I don't see why we would not use it for Fixnum#prime?

For Bignum#prime?, since division costs more, we can go slightly faster with the following implementation:

class Integer
  # Returns true if +self+ is a prime number, else returns false.
  def prime?
    return true if self == 2
    return false if self % 2 == 0 || self % 3 == 0 || self < 2
    skip_division = true
    (5..(self**0.5).floor).step(2) do |i|
      return false if skip_division && self % i == 0
      skip_division = !skip_division
    end
    true
  end
end
prime_opt.patch (1.55 KB) prime_opt.patch marcandre (Marc-Andre Lafortune), 10/10/2014 03:22 AM

Related issues

Is duplicate of Ruby trunk - Feature #5378: Prime.each is slowAssigned2011-09-29

Associated revisions

Revision 48767
Added by marcandre (Marc-Andre Lafortune) about 3 years ago

  • lib/prime.rb: Remove useless loop and block capture. See [#10354]

Revision 48767
Added by marcandre (Marc-Andre Lafortune) about 3 years ago

  • lib/prime.rb: Remove useless loop and block capture. See [#10354]

Revision 48767
Added by marcandre (Marc-Andre Lafortune) about 3 years ago

  • lib/prime.rb: Remove useless loop and block capture. See [#10354]

Revision 48767
Added by marcandre (Marc-Andre Lafortune) about 3 years ago

  • lib/prime.rb: Remove useless loop and block capture. See [#10354]

Revision 52200
Added by marcandre (Marc-Andre Lafortune) about 2 years ago

  • lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

Revision 52200
Added by marcandre (Marc-Andre Lafortune) about 2 years ago

  • lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

Revision 52200
Added by marcandre (Marc-Andre Lafortune) about 2 years ago

  • lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

History

#1 [ruby-core:65586] Updated by marcandre (Marc-Andre Lafortune) about 3 years ago

Oups, it would help if I gave the right implementation for Bignum#prime? See below

Here are some benchmarks:

Benchmark over 1..1_000_000
Current prime lib: 15.54
Fixed prime lib: 7.13
Nick's: 2.49

Benchmark for ((1 << 65) + 5).prime?:
Current prime lib: 11.83
Fixed prime lib: 6.82
Nick's: 5.32
Mine: 4.91

class Integer
  # Returns true if +self+ is a prime number, else returns false.
  def prime?
    return true if self == 2
    return false if (self % 2 == 0) || (self % 3 == 0) || (self < 2)
    skip_division = 3
    (5..(self**0.5).floor).step(2) { |i|
      if (skip_division -= 1) == 0
        skip_division = 3
        next
      end
      return false if self % i == 0
    }
    true
  end
end

#2 [ruby-core:65633] Updated by nick_slocum (Nick Slocum) about 3 years ago

I rewrote #prime? again using a better algorithm. It's about 2x faster. This version is for Integer, but could be reworked for BigNum.

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
    true
  end
end

Benchmarked with ruby-2.1.3
my first version: 4.27
this latest version: 2.76

#3 [ruby-core:65975] Updated by marcandre (Marc-Andre Lafortune) about 3 years ago

Dear Yugui,

Do you have an objection that I commit my fixes (which are really bug fixes) while you decide if you want to go in the direction of Nick's optimization?

Thanks

#4 Updated by marcandre (Marc-Andre Lafortune) almost 3 years ago

#5 Updated by marcandre (Marc-Andre Lafortune) about 2 years ago

  • Status changed from Open to Closed

Applied in changeset r52200.


  • lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

Also available in: Atom PDF