Last active
December 11, 2015 17:59
-
-
Save wenzowski/4638729 to your computer and use it in GitHub Desktop.
integer factorial for http://stackoverflow.com/questions/2434503/ruby-factorial-function
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.