ruby-core

Issue #13209 has been updated by 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 > 


```

----------------------------------------
Misc #13209: fact.rb in ruby/sample variations
https://bugs.ruby-lang.org/issues/13209#change-62968

* Author: Jabari Zakiya
* Status: Open
* Priority: Normal
* Assignee: 
----------------------------------------
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 > 

```



-- 
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request@ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>