Feature #10354
Optimize Integer#prime?
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
Files
Related issues
Associated revisions
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Remove useless loop and block capture. See [#10354]
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@52200 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]
History
Updated by marcandre (Marc-Andre Lafortune) about 5 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
Updated by Anonymous about 5 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
Updated by marcandre (Marc-Andre Lafortune) about 5 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
Updated by marcandre (Marc-Andre Lafortune) almost 5 years ago
- Is duplicate of Feature #5378: Prime.each is slow added
Updated by marcandre (Marc-Andre Lafortune) about 4 years ago
- Status changed from Open to Closed
Applied in changeset r52200.
- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]