Misc #13209: fact.rb in ruby/sample variations

• Status: Open
• Assignee: -

[jzakiya (Jabari Zakiya)]

I was looking at some of the Sample files that come with Ruby and
saw the example for doing factorials. It's an old example that I
thought I could make simpler/faster. Below are the results.

Maybe upgrading to show the difference between coding idioms can
be instructive to newer Ruby programmers.

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

require 'benchmark/ips'

Benchmark.ips do |x|
  x.report("original factorial") { fact  100 }
  x.report("modified factorial") { fact1 100 }
  x.report("enhanced factorial") { fact2 100 }
  x.compare!
end

Timings using ruby-2.4.0 on Linux 64-bit, on I7 cpu system.

2.4.0 :001 > load 'factversiontest.rb'
Warming up --------------------------------------
  original factorial     4.501k i/100ms
  modified factorial     4.594k i/100ms
  enhanced factorial     5.271k i/100ms
Calculating -------------------------------------
  original factorial     44.962k (± 4.2%) i/s -    225.050k in   5.015176s
  modified factorial     46.288k (± 3.2%) i/s -    234.294k in   5.066948s
  enhanced factorial     53.425k (± 3.1%) i/s -    268.821k in   5.036635s

Comparison:
  enhanced factorial:    53424.9 i/s
  modified factorial:    46288.0 i/s - 1.15x  slower
  original factorial:    44961.5 i/s - 1.19x  slower

 => true 
2.4.0 :002 > 

[jzakiya (Jabari Zakiya)]

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 > 

[jzakiya (Jabari Zakiya)]

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 >