factorial in ruby

[Trans]

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

Thanks,
T.

 

[David Simas]

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

 

[James Edward Gray II]

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

=> 28462596809170545189064132121198688901480514017...

James Edward Gray II

 

[Trans]

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]

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

 

[Michael W. Ryder]

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

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]

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

Bound by available memory and computation time.

- Charlie

 

[Florian Frank]

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

 

[Robert Dober]

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

 

[ara.t.howard]

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

 

[ara.t.howard]

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

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

 

[Amos King]

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

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:[email protected]]
Sent: Tuesday, 17 April 2007 6:58 a.m.
To: ruby-talk ML
Subject: Re: factorial in ruby

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


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