Project

General

Profile

Feature #14383 ยป bm.rb

mame (Yusuke Endoh), 01/25/2018 04:13 PM

 
1
require 'prime'
2
require 'faster_prime'
3

    
4
require 'openssl'
5
require 'benchmark'
6

    
7
class Integer
8
  def prime_division_2(generator = Prime::Generator23.new)
9
    return [] if (self.abs | 1) == 1
10
    pv = self < 0 ? [-1] : []
11
    value = self.abs
12
    prime = generator.next
13
    until value.to_bn.prime? or value == 1
14
      while prime
15
        (pv << prime; value /= prime; break) if value % prime == 0
16
        prime = generator.next
17
      end
18
    end
19
    pv << value if value > 1
20
    pv.group_by {|prm| prm }.map{|prm, exp| [prm, exp.size] }
21
  end
22
end
23

    
24
def factor(num)
25
  return [] if num | 1 == 1
26
  factors = num < 0 ? [-1] : []
27
  factors += `factor #{num.abs}`.split(' ')[1..-1].map(&:to_i)
28
  factors.group_by {|prm| prm }.map {|prm, exp| [prm, exp.size] }
29
end
30

    
31
puts <<~EOF
32
prime_division_current - current in prime.rb
33
prime_division_jzakiya - proposed version in #14383 by jzakiya
34
prime_division_mame    - https://github.com/mame/faster_prime
35
EOF
36

    
37

    
38
puts
39
puts "1_000_000 times of 10"
40
puts
41
Benchmark.bm(22) do |x|
42
  x.report('prime_division_current') { 1_000_000.times { Prime.prime_division(10) } }
43
  x.report('prime_division_jzakiya') { 1_000_000.times { 10.prime_division_2 } }
44
  x.report('prime_division_mame   ') { 1_000_000.times { FasterPrime.prime_division(10) } }
45
end
46

    
47
puts
48
puts "1_000 times of 2**256"
49
puts
50
Benchmark.bm(22) do |x|
51
  num = 2**256
52
  x.report('prime_division_current') { 1_000.times { Prime.prime_division(num) } }
53
  x.report('prime_division_jzakiya') { 1_000.times { num.prime_division_2 } }
54
  x.report('prime_division_mame   ') { 1_000.times { FasterPrime.prime_division(num) } }
55
end
56

    
57
puts
58
puts "10 times of 500_000_000_000_000_000_008_244_213"
59
puts
60
Benchmark.bm(22) do |x|
61
  num = 500_000_000_000_000_000_008_244_213
62
  x.report('prime_division_mame   ') { 10.times { FasterPrime.prime_division(num) } }
63
  x.report('prime_division_jzakiya') { 10.times { num.prime_division_2 } }
64
  x.report('prime_division_current') { 10.times { Prime.prime_division(num) } }
65
end