From: ara.t.howard@...
Date: 2007-04-17T10:50:19+09:00
Subject: Re: factorial in ruby

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
-- 
be kind whenever possible... it is always possible.
- the dalai lama