|
require 'prime'
|
|
require 'faster_prime'
|
|
|
|
require 'openssl'
|
|
require 'benchmark'
|
|
|
|
class Integer
|
|
def prime_division_2(generator = Prime::Generator23.new)
|
|
return [] if (self.abs | 1) == 1
|
|
pv = self < 0 ? [-1] : []
|
|
value = self.abs
|
|
prime = generator.next
|
|
until value.to_bn.prime? or value == 1
|
|
while prime
|
|
(pv << prime; value /= prime; break) if value % prime == 0
|
|
prime = generator.next
|
|
end
|
|
end
|
|
pv << value if value > 1
|
|
pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] }
|
|
end
|
|
end
|
|
|
|
def factor(num)
|
|
return [] if num | 1 == 1
|
|
factors = num < 0 ? [-1] : []
|
|
factors += `factor #{num.abs}`.split(' ')[1..-1].map(&:to_i)
|
|
factors.group_by {|prm| prm }.map {|prm, exp| [prm, exp.size] }
|
|
end
|
|
|
|
puts <<~EOF
|
|
prime_division_current - current in prime.rb
|
|
prime_division_jzakiya - proposed version in #14383 by jzakiya
|
|
prime_division_mame - https://github.com/mame/faster_prime
|
|
EOF
|
|
|
|
|
|
puts
|
|
puts "1_000_000 times of 10"
|
|
puts
|
|
Benchmark.bm(22) do |x|
|
|
x.report('prime_division_current') { 1_000_000.times { Prime.prime_division(10) } }
|
|
x.report('prime_division_jzakiya') { 1_000_000.times { 10.prime_division_2 } }
|
|
x.report('prime_division_mame ') { 1_000_000.times { FasterPrime.prime_division(10) } }
|
|
end
|
|
|
|
puts
|
|
puts "1_000 times of 2**256"
|
|
puts
|
|
Benchmark.bm(22) do |x|
|
|
num = 2**256
|
|
x.report('prime_division_current') { 1_000.times { Prime.prime_division(num) } }
|
|
x.report('prime_division_jzakiya') { 1_000.times { num.prime_division_2 } }
|
|
x.report('prime_division_mame ') { 1_000.times { FasterPrime.prime_division(num) } }
|
|
end
|
|
|
|
puts
|
|
puts "10 times of 500_000_000_000_000_000_008_244_213"
|
|
puts
|
|
Benchmark.bm(22) do |x|
|
|
num = 500_000_000_000_000_000_008_244_213
|
|
x.report('prime_division_mame ') { 10.times { FasterPrime.prime_division(num) } }
|
|
x.report('prime_division_jzakiya') { 10.times { num.prime_division_2 } }
|
|
x.report('prime_division_current') { 10.times { Prime.prime_division(num) } }
|
|
end
|