# Factorial in ruby

**URL:** <https://www.ruby-forum.com/t/factorial-in-ruby/92161>\
**Category:** Ruby\
**Created:** [April 16, 2007, 7:38pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161 "2007-04-16T19:38:17Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 7:38pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/1 "2007-04-16T19:38:17Z")

</div>

Is factorial defined anywhere in Ruby’s core or standard library. If  
not will it be in 1.9+?

Thanks,  
T.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 7:57pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/2 "2007-04-16T19:57:18Z")

</div>

No and most likely not.

def fact(n)  
if n == 0  
1  
else  
n \* fact(n-1)  
end  
end

Jason

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 8:59pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/3 "2007-04-16T20:59:26Z")

</div>

On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason R. wrote:

> No and most likely not.
> 
> def fact(n)  
> if n == 0  
> 1  
> else  
> n \* fact(n-1)  
> end  
> end

For large enough n, this will overflow the stack. Since Ruby doesn’t  
optimize tail-recursive functions (and the above isn’t tail recursive,  
anyway), you’d better write this function as a loop (left as an  
exercise).

DGS

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 9:26pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/4 "2007-04-16T21:26:32Z")

</div>

On Apr 16, 2007, at 1:58 PM, David Simas wrote:

> For large enough n, this will overflow the stack. Since Ruby doesn’t  
> optimize tail-recursive functions (and the above isn’t tail recursive,  
> anyway), you’d better write this function as a loop (left as an  
> exercise).

> > class Integer  
> > def fact  
> > (2…self).inject(1) { |f, n| f \* n }  
> > end  
> > end  
> > =\> nil
> 
> > 0.fact  
> > =\> 1
> 
> > 1.fact  
> > =\> 1
> 
> > 10.fact  
> > =\> 3628800
> 
> > 10\_000.fact  
> > =\> 28462596809170545189064132121198688901480514017…

James Edward G. II

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 10:21pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/5 "2007-04-16T22:21:36Z")

</div>

One important lesson learnt (at least by me) is that the default  
accumulator  
assignment happens _before_ the Enumerable iteration. This allows the  
0.fact and 1.fact to work. In fact the block is _not_ even checked if  
the  
iteration does not happen, just like other Enumerable methods.

So the following is possible -

irb(main):002:0\> (1…0).inject(1)  
=\> 1

This is cool but is it a corner case? This could lead to hard to find  
bugs  
in cases when the array or range was never meant to be accumulated  
(because  
it was empty or out of range) but there will be a return value  
regardless.

- Nasir

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 10:37pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/6 "2007-04-16T22:37:36Z")

</div>

The inject version should work for any value, as it is iterative. The  
recursive version probably breaks somewhere in the thousands (on my  
machine  
just under 2000), but could be machine dependent.

–Tyler P.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 16, 2007, 9:36pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/7 "2007-04-16T21:36:32Z")

</div>

On 4/16/07, James Edward G. II [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > > n \* fact(n-1)  
> > > (2…self).inject(1) { |f, n| f \* n }  
> > > =\> 28462596809170545189064132121198688901480514017…
> 
> James Edward G. II

I knew there was a way to use #inject here, I just didn’t know how. I  
need  
to use that function more. When does this version break Ruby?

Jason

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 2:07am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/8 "2007-04-17T02:07:00Z")

</div>

On Apr 16, 1:56 pm, “Jason R.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> No and most likely not.

Why not? Seems to me factorial is a pretty basic/common math function.  
It would be nice if written in C for speed.

T.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 4:33am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/9 "2007-04-17T04:33:10Z")

</div>

On 4/16/07, Trans [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> Basic maybe, common debatable, Even if its a commonly used function (maybe  
> your program does a lot of permutations and combinations) I somehow  
> suspect  
> factorial doesn’t actually get called so often that it needs to be in  
> stdlib  
> or core. Its also not one of those math functions where you have to  
> “know  
> the trick” (not that its a terribly complicated trick) to implement it  
> like  
> Math::exp. I can’t think of a good use case. although maybe its just me.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 3:51am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/10 "2007-04-17T03:51:07Z")

</div>

On Tue, 17 Apr 2007, Trans wrote:

> On Apr 16, 1:56 pm, “Jason R.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > No and most likely not.
> 
> Why not? Seems to me factorial is a pretty basic/common math function.  
> It would be nice if written in C for speed.

perhaps. perhaps not:

fortytwo: ~\> cat a.rb

# 

# gem install inline @ [http://rubyforge.org/projects/rubyinline/](http://rubyforge.org/projects/rubyinline/)

# 

require ‘benchmark’  
require ‘rubygems’  
require ‘inline’

# 

# setup two factorial methods, one in ruby and in using inline. the

inline

# version is compiled on the fly using ruby2c and cc

# 

module Math  
class \<\< self  
def factorial\_ruby n  
f = 1  
n.downto(2){|x| f \*= x }  
f  
end

```
   inline do |builder|
     builder.c <<-'c'
       int
       factorial_inline (int max)
       {
         int i = max, result = 1;
         while (i >= 2)
           {
             result *= i--;
           }
         return result;
       }
     c
   end
 end

```

end

# 

# check how fast they each are. we run many times to show the

differences.

# 

n = 4242  
Benchmark.bm do |x|  
x.report ‘factorial\_ruby’ do  
n.times{ Math.factorial\_ruby 42 }  
end

```
 x.report 'factorial_inline' do
   n.times{ Math.factorial_inline 42 }
 end

```

end

# 

# now show accuracy. how many bits is a signed int again?

# 

42.times do |i|  
a, b = Math.factorial\_ruby(i), Math.factorial\_inline(i)  
p [i, a, b]  
break unless a == b  
end

# 

# check this out. automatic bigint boxing.

# 

p Math.factorial\_ruby(42)  
p Math.factorial\_ruby(42).class

fortytwo: ~\> ruby a.rb  
user system total real  
factorial\_ruby 0.550000 0.010000 0.560000 ( 0.767810)  
factorial\_inline 0.010000 0.000000 0.010000 ( 0.003574)  
[0, 1, 1]  
[1, 1, 1]  
[2, 2, 2]  
[3, 6, 6]  
[4, 24, 24]  
[5, 120, 120]  
[6, 720, 720]  
[7, 5040, 5040]  
[8, 40320, 40320]  
[9, 362880, 362880]  
[10, 3628800, 3628800]  
[11, 39916800, 39916800]  
[12, 479001600, 479001600]  
[13, 6227020800, -215430144]  
1405006117752879898543142606244511569936384000000000  
Bignum

not the integer wrap from the c version - this is a case where c gets  
you crap  
answers real quick. you need more that just c, but also an arbitrary  
precision  
arithmitic library to do factorial fast.

kind regards.

-a

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 10:20am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/11 "2007-04-17T10:20:40Z")

</div>

removed\_email\_address@domain.invalid wrote:

> perhaps. perhaps not:
> 
> # setup two factorial methods, one in ruby and in using inline. the inline
> 
> ```
> inline do |builder|
> }
> n.times{ Math.factorial_ruby 42 }
> a, b = Math.factorial_ruby(i), Math.factorial_inline(i)
> 
> ```
> 
> [5, 120, 120]
> 
> -a  
> Is it possible to use long integers with rubyinline and would it make a  
> difference with the results?  
> Also where would I find more documentation on rubyinline? I tried to  
> use your example program and got the gem installed but it then  
> complained about an environment variable. I don’t know if it is looking  
> for a specific C compiler or what, I have Borland C installed and in the  
> path.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 11:11am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/12 "2007-04-17T11:11:46Z")

</div>

Tyler P. wrote:

> The inject version should work for any value, as it is iterative.

Bound by available memory and computation time.

- Charlie

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 12:33pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/13 "2007-04-17T12:33:53Z")

</div>

removed\_email\_address@domain.invalid wrote:

> not the integer wrap from the c version - this is a case where c gets  
> you crap  
> answers real quick. you need more that just c, but also an arbitrary  
> precision  
> arithmitic library to do factorial fast.

Caching can avoid unnecessary multiplications (while using Bignums), if  
one wants to compute a lot of factorials:

module Factorial  
module\_function

@@cache = [1]

def fact(n)  
raise ArgumentError, “n has to be \>= 0” if n \< 0  
@@cache.size.upto(n) { |i| @@cache[i] = i \* @@cache[i - 1] }  
@@cache[n]  
end  
end

if $0 == **FILE**  
require ‘test/unit’  
class TestFactorial \< Test::Unit::TestCase  
include Factorial  
def test\_fact  
assert\_raises(ArgumentError) { fact(-1) }  
assert\_equal 1, fact(0)  
assert\_equal 1, fact(1)  
assert\_equal 2, fact(2)  
assert\_equal 6, fact(3)  
assert\_equal 24, fact(4)  
assert\_equal 120, fact(5)  
assert\_equal 3628800, fact(10)  
end  
end  
end

This should get faster, the more factorials you want to compute.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 1:11pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/14 "2007-04-17T13:11:56Z")

</div>

“Trans” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> On Apr 16, 1:56 pm, “Jason R.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:
> 
> > No and most likely not.
> 
> Why not? Seems to me factorial is a pretty basic/common math function.  
> It would be nice if written in C for speed.

Good point for other reasons: note that there are vastly more efficient  
implementations for factorials n! with big (say, \>1000) n.

I’m not sure if these are needed often, tho.

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 1:13pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/15 "2007-04-17T13:13:56Z")

</div>

On 4/16/07, James Edward G. II [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> > > end  
> > > end
> 
> James Edward G. II

James I think it is better to change f \* n to n \* f, at least at my  
Linux box 😉

520/20 \> cat fact.rb && ./fact.rb  
#!/usr/local/bin/ruby

# vim: sts=2 sw=2 expandtab nu tw=0:

require ‘benchmark’  
class Integer  
def fact  
(2…self).inject(1) { |f, n| f \* n }  
end  
def fact1  
(2…self).inject(1) { |f, n| n \* f }  
end  
end

Benchmark.bmbm do  
| bench |  
bench.report( “fact” ) { 10\_000.fact }  
bench.report( “fact1” ) { 10\_000.fact1 }  
end # Benchmark.bmbm do  
Rehearsal -----------------------------------------  
fact 0.680000 0.020000 0.700000 ( 0.741495)  
fact1 0.530000 0.010000 0.540000 ( 0.615510)  
-------------------------------- total: 1.240000sec

```
        user system total real

```

fact 0.680000 0.010000 0.690000 ( 0.755592)  
fact1 0.530000 0.010000 0.540000 ( 0.589984)

Cheers  
Robert

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 4:45pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/16 "2007-04-17T16:45:35Z")

</div>

On Tue, 17 Apr 2007, Michael W. Ryder wrote:

> Is it possible to use long integers with rubyinline and would it make a  
> difference with the results?

it should be.

> Also where would I find more documentation on  
> rubyinline?

it’s on rubyforge. the source comes with some examples.

> I tried to use your example program and got the gem installed but it then  
> complained about an environment variable. I don’t know if it is looking for  
> a specific C compiler or what, I have Borland C installed and in the path.

afaik rubyinline will work under

- \*nix
- osx
- msys compiled ruby
- cygwin compiled ruby

it would take some incantations to make it work with the one-click  
installer,  
which is crippled in this (having knowledge about the build environment)  
resepect

-a

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 17, 2007, 4:44pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/17 "2007-04-17T16:44:34Z")

</div>

On Tue, 17 Apr 2007, Florian F. wrote:

> module Factorial
> 
> ```
> assert_equal 24, fact(4)
> assert_equal 120, fact(5)
> assert_equal 3628800, fact(10)
> 
> ```
> 
> end  
> end  
> end
> 
> This should get faster, the more factorials you want to compute.

and even more reason to delay writing it in c. my main point was simply  
that  
almost no function is straight forward to write in c if one is looking  
for  
robust code. also, because ruby is fast enough for small values but c  
is  
wrong for even medium values it begs the question of whether writing a  
seemingly simply function like factorial in c really would be worth the  
work.

maybe someone can hack a rubyinline version using bignums so we can  
compare  
that?

kind regards.

-a

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 18, 2007, 6:38am UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/18 "2007-04-18T06:38:00Z")

</div>

For large enough n it will also overflow the number. Probably the most  
efficient way would be to use a loop up to some (not very large) number,  
to  
use Stirling’s approximation or its extension up to some larger number,  
and  
throw an overfow exception for anything larger than that.

Cheers

Gary Thomas

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 20, 2007, 9:12pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/19 "2007-04-20T21:12:49Z")

</div>

Except for calculating binomial coefficients for probability  
calculations or  
closely related things. I can’t think of any reason to calculate large  
factorials. In the case of binomial coefficients it is better to cancel  
out  
some of the factors and avoid calculating the huge factorials. If the  
numbers are large, the use of approximations is almost certainly a  
better  
approach

Cheers

Gary Thomas

---

<div class="post-metadata">

**Author:** ![Trans](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/t/dfb087/32.png) [@Trans](https://www.ruby-forum.com/u/Trans)\
**Post date:** [April 18, 2007, 5:36pm UTC](https://www.ruby-forum.com/t/factorial-in-ruby/92161/20 "2007-04-18T17:36:26Z")

</div>

make it non-recursive use

class Integer  
def fact  
return 1 if self == 0  
(1…self).inject { |i,j| i\*j }  
end  
end

Then you can just call  
120.fact and that will return the factorial of 120 with no overflow.  
You may want to add in a check for negatives

[Next page](https://www.ruby-forum.com/t/factorial-in-ruby/92161.md?page=2)
