Ruby

Added another version using the step method, in fact3.
It's faster than using downto and neck-in-neck with using reduce as n gets bigger.

def fact(n) return 1 if n == 0 f = 1 n.downto(1) do |i| f *= i end return f end def fact1(n) return 1 if n | 1 == 1 # if n 0 or 1 f = 2 n.downto(3) do |i| f *= i end return f end def fact2(n) return 1 if n | 1 == 1 # if n 0 or 1 (2..n).reduce(:*) end def fact3(n) return 1 if n | 1 == 1 # if n 0 or 1 f = 2 3.step(n) {|i| f *= i } f end require 'benchmark/ips' Benchmark.ips do |x| n = 100 puts "factorials tests for n = #{n}" x.report("original factorial") { fact n } x.report("modified factorial") { fact1 n } x.report("enhanced factorial") { fact2 n } x.report("withstep factorial") { fact3 n } x.compare! end 

Here are benchmark results for various values of n.

2.4.0 :074 > load 'factversiontest.rb' factorials tests for n = 50 Warming up -------------------------------------- original factorial 12.555k i/100ms modified factorial 13.201k i/100ms enhanced factorial 16.157k i/100ms withstep factorial 15.874k i/100ms Calculating ------------------------------------- original factorial 130.394k (± 3.0%) i/s - 652.860k in 5.011491s modified factorial 139.530k (± 3.4%) i/s - 699.653k in 5.020706s enhanced factorial 168.796k (± 2.9%) i/s - 856.321k in 5.077542s withstep factorial 168.096k (± 3.8%) i/s - 841.322k in 5.012920s Comparison: enhanced factorial: 168795.7 i/s withstep factorial: 168095.7 i/s - same-ish: difference falls within error modified factorial: 139530.0 i/s - 1.21x slower original factorial: 130394.5 i/s - 1.29x slower => true 2.4.0 :075 > load 'factversiontest.rb' factorials tests for n = 70 Warming up -------------------------------------- original factorial 6.986k i/100ms modified factorial 7.346k i/100ms enhanced factorial 8.775k i/100ms withstep factorial 8.729k i/100ms Calculating ------------------------------------- original factorial 74.263k (± 4.1%) i/s - 377.244k in 5.088997s modified factorial 77.018k (± 4.2%) i/s - 389.338k in 5.065362s enhanced factorial 91.759k (± 3.1%) i/s - 465.075k in 5.073560s withstep factorial 90.324k (± 3.5%) i/s - 453.908k in 5.031665s Comparison: enhanced factorial: 91759.4 i/s withstep factorial: 90323.5 i/s - same-ish: difference falls within error modified factorial: 77017.6 i/s - 1.19x slower original factorial: 74262.9 i/s - 1.24x slower => true 2.4.0 :076 > load 'factversiontest.rb' factorials tests for n = 80 Warming up -------------------------------------- original factorial 5.887k i/100ms modified factorial 6.193k i/100ms enhanced factorial 7.197k i/100ms withstep factorial 7.178k i/100ms Calculating ------------------------------------- original factorial 61.279k (± 3.4%) i/s - 306.124k in 5.001437s modified factorial 59.091k (±17.6%) i/s - 284.878k in 5.066603s enhanced factorial 73.394k (± 5.7%) i/s - 367.047k in 5.021211s withstep factorial 73.323k (± 3.1%) i/s - 373.256k in 5.095652s Comparison: enhanced factorial: 73393.6 i/s withstep factorial: 73323.3 i/s - same-ish: difference falls within error original factorial: 61279.1 i/s - 1.20x slower modified factorial: 59091.0 i/s - same-ish: difference falls within error => true 2.4.0 :077 > load 'factversiontest.rb' factorials tests for n = 90 Warming up -------------------------------------- original factorial 5.058k i/100ms modified factorial 5.269k i/100ms enhanced factorial 6.110k i/100ms withstep factorial 5.910k i/100ms Calculating ------------------------------------- original factorial 52.231k (± 3.1%) i/s - 263.016k in 5.040608s modified factorial 52.933k (± 5.0%) i/s - 268.719k in 5.090458s enhanced factorial 62.426k (± 3.1%) i/s - 317.720k in 5.094697s withstep factorial 61.210k (± 4.1%) i/s - 307.320k in 5.030274s Comparison: enhanced factorial: 62426.3 i/s withstep factorial: 61210.0 i/s - same-ish: difference falls within error modified factorial: 52933.4 i/s - 1.18x slower original factorial: 52230.8 i/s - 1.20x slower => true 2.4.0 :078 > load 'factversiontest.rb' factorials tests for n = 100 Warming up -------------------------------------- original factorial 4.450k i/100ms modified factorial 4.580k i/100ms enhanced factorial 5.259k i/100ms withstep factorial 5.195k i/100ms Calculating ------------------------------------- original factorial 45.211k (± 5.0%) i/s - 226.950k in 5.034319s modified factorial 46.402k (± 3.7%) i/s - 233.580k in 5.040945s enhanced factorial 53.148k (± 4.2%) i/s - 268.209k in 5.055701s withstep factorial 52.588k (± 3.2%) i/s - 264.945k in 5.043348s Comparison: enhanced factorial: 53148.1 i/s withstep factorial: 52588.5 i/s - same-ish: difference falls within error modified factorial: 46401.9 i/s - 1.15x slower original factorial: 45210.5 i/s - 1.18x slower => true 2.4.0 :079 > load 'factversiontest.rb' factorials tests for n = 150 Warming up -------------------------------------- original factorial 2.699k i/100ms modified factorial 2.759k i/100ms enhanced factorial 3.071k i/100ms withstep factorial 2.960k i/100ms Calculating ------------------------------------- original factorial 27.169k (± 4.6%) i/s - 137.649k in 5.078680s modified factorial 27.344k (± 4.7%) i/s - 137.950k in 5.056891s enhanced factorial 30.398k (± 3.9%) i/s - 153.550k in 5.059403s withstep factorial 29.730k (± 3.5%) i/s - 150.960k in 5.084036s Comparison: enhanced factorial: 30398.2 i/s withstep factorial: 29730.3 i/s - same-ish: difference falls within error modified factorial: 27343.9 i/s - 1.11x slower original factorial: 27168.7 i/s - 1.12x slower => true 2.4.0 :080 > 

For MRI Ruby (but not JRuby) while loops are consistently faster than all
the other loop constructs (times, each, step, etc). If the goal is fastest
possible speed for MRI Ruby 3x3 it seems internals should use while loops
wherever possible.

Here, fact4 using a while loop is fastest for any value of n.

def fact(n) return 1 if n == 0 f = 1 n.downto(1) do |i| f *= i end return f end def fact1(n) return 1 if n | 1 == 1 # if n 0 or 1 f = 2 n.downto(3) do |i| f *= i end return f end def fact2(n) return 1 if n | 1 == 1 # if n 0 or 1 (2..n).reduce(:*) end def fact3(n) return 1 if n | 1 == 1 # if n 0 or 1 f = 2 3.step(n){|i| f *= i } f end def fact4(n) return 1 if n | 1 == 1 # if n 0 or 1 f, i = 2, 3 (f *= i; i += 1) while i <= n f end require 'benchmark/ips' Benchmark.ips do |x| n = 100 puts "factorials tests for n = #{n}" x.report("original factorial") { fact n } x.report("modified factorial") { fact1 n } x.report("enhanced factorial") { fact2 n } x.report("withstep factorial") { fact3 n } x.report("usewhile factorial") { fact4 n } x.compare! end 

Example timings.

2.4.0 :010 > load 'factversiontest.rb' factorials tests for n = 10 Warming up -------------------------------------- original factorial 152.621k i/100ms modified factorial 169.295k i/100ms enhanced factorial 124.274k i/100ms withstep factorial 134.304k i/100ms usewhile factorial 208.290k i/100ms Calculating ------------------------------------- original factorial 2.074M (± 2.5%) i/s - 10.378M in 5.006297s modified factorial 2.328M (± 2.6%) i/s - 11.681M in 5.020649s enhanced factorial 1.623M (± 2.7%) i/s - 8.202M in 5.058125s withstep factorial 1.736M (± 2.7%) i/s - 8.730M in 5.032241s usewhile factorial 3.259M (± 2.8%) i/s - 16.455M in 5.052772s Comparison: usewhile factorial: 3259334.0 i/s modified factorial: 2328303.5 i/s - 1.40x slower original factorial: 2074354.4 i/s - 1.57x slower withstep factorial: 1736091.0 i/s - 1.88x slower enhanced factorial: 1622837.9 i/s - 2.01x slower => true 2.4.0 :011 > load 'factversiontest.rb' factorials tests for n = 25 Warming up -------------------------------------- original factorial 50.369k i/100ms modified factorial 53.391k i/100ms enhanced factorial 56.290k i/100ms withstep factorial 60.209k i/100ms usewhile factorial 83.857k i/100ms Calculating ------------------------------------- original factorial 553.152k (± 2.6%) i/s - 2.770M in 5.011731s modified factorial 598.668k (± 2.7%) i/s - 3.043M in 5.087403s enhanced factorial 635.598k (± 2.7%) i/s - 3.209M in 5.051865s withstep factorial 673.752k (± 2.6%) i/s - 3.372M in 5.007842s usewhile factorial 996.703k (± 2.6%) i/s - 5.031M in 5.051626s Comparison: usewhile factorial: 996703.4 i/s withstep factorial: 673752.0 i/s - 1.48x slower enhanced factorial: 635598.1 i/s - 1.57x slower modified factorial: 598668.2 i/s - 1.66x slower original factorial: 553152.2 i/s - 1.80x slower => true 2.4.0 :012 > load 'factversiontest.rb' factorials tests for n = 50 Warming up -------------------------------------- original factorial 13.772k i/100ms modified factorial 14.688k i/100ms enhanced factorial 17.696k i/100ms withstep factorial 17.501k i/100ms usewhile factorial 21.318k i/100ms Calculating ------------------------------------- original factorial 142.356k (± 3.0%) i/s - 716.144k in 5.035290s modified factorial 152.404k (± 3.0%) i/s - 763.776k in 5.016154s enhanced factorial 183.865k (± 2.8%) i/s - 920.192k in 5.008924s withstep factorial 182.771k (± 2.7%) i/s - 927.553k in 5.078797s usewhile factorial 222.403k (± 3.0%) i/s - 1.130M in 5.085087s Comparison: usewhile factorial: 222402.7 i/s enhanced factorial: 183865.0 i/s - 1.21x slower withstep factorial: 182770.6 i/s - 1.22x slower modified factorial: 152404.0 i/s - 1.46x slower original factorial: 142355.6 i/s - 1.56x slower => true 2.4.0 :013 > load 'factversiontest.rb' factorials tests for n = 100 Warming up -------------------------------------- original factorial 4.933k i/100ms modified factorial 4.976k i/100ms enhanced factorial 5.752k i/100ms withstep factorial 5.607k i/100ms usewhile factorial 6.060k i/100ms Calculating ------------------------------------- original factorial 49.084k (± 2.9%) i/s - 246.650k in 5.029407s modified factorial 49.886k (± 3.4%) i/s - 253.776k in 5.093179s enhanced factorial 54.025k (± 8.1%) i/s - 270.344k in 5.044646s withstep factorial 53.487k (± 4.3%) i/s - 269.136k in 5.041225s usewhile factorial 58.795k (± 9.2%) i/s - 296.940k in 5.096755s Comparison: usewhile factorial: 58794.8 i/s enhanced factorial: 54024.6 i/s - same-ish: difference falls within error withstep factorial: 53486.8 i/s - same-ish: difference falls within error modified factorial: 49885.7 i/s - 1.18x slower original factorial: 49084.0 i/s - 1.20x slower => true 2.4.0 :014 >