[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

factorial in ruby

Trans

4/16/2007 5:37:00 PM

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

Thanks,
T.
11 Answers

David Simas

4/16/2007 6:58:00 PM

0

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

James Gray

4/16/2007 7:25:00 PM

0

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

Trans

4/17/2007 12:06:00 AM

0



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.

Ara.T.Howard

4/17/2007 1:50:00 AM

0

Michael W. Ryder

4/17/2007 8:17:00 AM

0

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/r...
> #
> 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

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.

Charles Oliver Nutter

4/17/2007 9:11:00 AM

0

Tyler Prete wrote:
> The inject version should work for any value, as it is iterative.

Bound by available memory and computation time.

- Charlie

Florian Frank

4/17/2007 10:32:00 AM

0

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.

--
Florian Frank

Christian Neukirchen

4/17/2007 11:11:00 AM

0

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

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

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.

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

Robert Dober

4/17/2007 11:13:00 AM

0

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

Ara.T.Howard

4/17/2007 2:41:00 PM

0