public
Last active

  • Download Gist
factorial.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
class Integer
##
# Automatically choses fastest accurate algorithm.
def factorial
case
when 0 <= self && self <= 21
self.factorial_via_gamma
when 21 < self
self.factorial_via_reduce
else
raise RangeError, 'the factorial operation is only defined for n >= 0'
end
end
 
##
# Math#gamma calculates using Float. Its docs explain implications of this.
# Accurate from 0! to 21! try:
# (1..30).each_with_index{|n, i| p [i, n.factorial_via_gamma == n.factorial_via_reduce] }
def factorial_via_gamma
Math.gamma(self + 1).round
end
 
##
# Slower than Math#gamma, but accurate in all domains.
def factorial_via_reduce
(1..self).reduce(:*) || 1
end
end
 
require 'benchmark'
 
a = 1
b = 21
r = 1000000
 
Benchmark.bm do |x|
x.report do
r.times do
(a..b).each {|i| i.factorial_via_reduce }
end
end
x.report do
r.times do
(a..b).each {|i| i.factorial_via_gamma }
end
end
x.report do
r.times do
(a..b).each {|i| i.factorial }
end
end
end
 
# My Results
# ==========
#
# user system total real
# 38.410000 0.050000 38.460000 ( 38.873156)
# 23.060000 0.040000 23.100000 ( 23.190497)
# 25.700000 0.040000 25.740000 ( 25.816415)
#
# You should probably run the benchmark yourself to get relevant data.

Of course, since factorial is a pure function, a much better way to optimize considering Math#gamma is only faster without losing accuracy for integers in (1..21) is to memoize the output.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.