Factorial in ruby

ruby-talk
1

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

Thanks,
T.

2

No and most likely not.

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

Jason

···

On 4/16/07, Trans <transfire@gmail.com> wrote:

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

Thanks,
T.

3

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

···

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

Jason

On 4/16/07, Trans <transfire@gmail.com> wrote:
>
>Is factorial defined anywhere in Ruby's core or standard library. If
>not will it be in 1.9+?
>
>Thanks,
>T.
>
>
>

4

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

T.

···

On Apr 16, 1:56 pm, "Jason Roelofs" <jameskil...@gmail.com> wrote:

No and most likely not.

5

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).

>> 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 Gray II

···

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

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

6

perhaps. perhaps not:

fortytwo: ~> cat a.rb

···

On Tue, 17 Apr 2007, Trans wrote:

On Apr 16, 1:56 pm, "Jason Roelofs" <jameskil...@gmail.com> 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.

#
# gem install inline @ 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
--
be kind whenever possible... it is always possible.
- the dalai lama

7

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.

···

On 4/16/07, Trans <transfire@gmail.com> wrote:

On Apr 16, 1:56 pm, "Jason Roelofs" <jameskil...@gmail.com> 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.

Basic maybe, common debatable, Even if its a commonly used function (maybe

8

"Trans" <transfire@gmail.com> writes:

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.

···

On Apr 16, 1:56 pm, "Jason Roelofs" <jameskil...@gmail.com> wrote:

T.

--
Christian Neukirchen <chneukirchen@gmail.com> http://chneukirchen.org

9

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

···

-----Original Message-----
From: David Simas [mailto:dsimas@imageworks.com]
Sent: Tuesday, 17 April 2007 6:58 a.m.
To: ruby-talk ML
Subject: Re: factorial in ruby

On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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

>
> Jason
>
> On 4/16/07, Trans <transfire@gmail.com> wrote:
> >
> >Is factorial defined anywhere in Ruby's core or standard library. If
> >not will it be in 1.9+?
> >
> >Thanks,
> >T.
> >
> >
> >

10

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

···

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote:

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

> On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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).

>> 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 Gray II

11

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.

···

ara.t.howard@noaa.gov wrote:

On Tue, 17 Apr 2007, Trans wrote:

On Apr 16, 1:56 pm, "Jason Roelofs" <jameskil...@gmail.com> 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/
#
  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

12

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.

···

ara.t.howard@noaa.gov 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.

--
Florian Frank

13

>> 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).

>> 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 Gray II

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

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

···

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote:

On Apr 16, 2007, at 1:58 PM, David Simas wrote:
> On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs wrote:

--
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw

14

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

···

On 4/17/07, Gary Thomas <gthomas@takaro.co.nz> wrote:

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

> -----Original Message-----
> From: David Simas [mailto:dsimas@imageworks.com]
> Sent: Tuesday, 17 April 2007 6:58 a.m.
> To: ruby-talk ML
> Subject: Re: factorial in ruby
>
> On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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
>
> >
> > Jason
> >
> > On 4/16/07, Trans <transfire@gmail.com> wrote:
> > >
> > >Is factorial defined anywhere in Ruby's core or standard library. If
> > >not will it be in 1.9+?
> > >
> > >Thanks,
> > >T.
> > >
>

--
Amos King
Ramped Media
USPS
Programmer/Analyst
St. Louis, MO
Looking for something to do? Visit ImThere.com

15

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

···

On 4/16/07, Jason Roelofs <jameskilton@gmail.com> wrote:

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote:
>
> On Apr 16, 2007, at 1:58 PM, David Simas wrote:
>
> > On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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).
>
> >> 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 Gray 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

16

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 Prete

···

On 4/16/07, Jason Roelofs <jameskilton@gmail.com> wrote:

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote:
>
> On Apr 16, 2007, at 1:58 PM, David Simas wrote:
>
> > On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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).
>
> >> 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 Gray 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

17

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

···

On Tue, 17 Apr 2007, Florian Frank wrote:

ara.t.howard@noaa.gov 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.

--
be kind whenever possible... it is always possible.
- the dalai lama

18

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

···

On Tue, 17 Apr 2007, Michael W. Ryder wrote:
--
be kind whenever possible... it is always possible.
- the dalai lama

19

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

···

-----Original Message-----
From: Amos King [mailto:amos.l.king@gmail.com]
Sent: Thursday, 19 April 2007 3:35 a.m.
To: ruby-talk ML
Subject: Re: factorial in ruby

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

On 4/17/07, Gary Thomas <gthomas@takaro.co.nz> wrote:
> 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
>
> > -----Original Message-----
> > From: David Simas [mailto:dsimas@imageworks.com]
> > Sent: Tuesday, 17 April 2007 6:58 a.m.
> > To: ruby-talk ML
> > Subject: Re: factorial in ruby
> >
> >
> > On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason Roelofs 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
> >
> > >
> > > Jason
> > >
> > > On 4/16/07, Trans <transfire@gmail.com> wrote:
> > > >
> > > >Is factorial defined anywhere in Ruby's core or standard
library. If
> > > >not will it be in 1.9+?
> > > >
> > > >Thanks,
> > > >T.
> > > >
> > > >
> > > >
> >
> >
> >
>
>
>
>

--
Amos King
Ramped Media
USPS
Programmer/Analyst
St. Louis, MO
Looking for something to do? Visit ImThere.com

20

Tyler Prete wrote:

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

Bound by available memory and computation time.

- Charlie