From: Robert Dober <robert.dober@...>
Date: 2007-04-17T20:12:53+09:00
Subject: Re: factorial in ruby

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
>
>
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
-- 
You see things; and you say Why?
But I dream things that never were; and I say Why not?
-- George Bernard Shaw