Is factorial defined anywhere in Ruby’s core or standard library. If
not will it be in 1.9+?
Thanks,
T.
No and most likely not.
def fact(n)
if n == 0
1
else
n * fact(n-1)
end
end
Jason
On Tue, Apr 17, 2007 at 02:56:16AM +0900, Jason R. 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
On Apr 16, 2007, at 1:58 PM, David Simas wrote:
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
=> nil0.fact
=> 11.fact
=> 110.fact
=> 362880010_000.fact
=> 28462596809170545189064132121198688901480514017…
James Edward G. II
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
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 P.
On 4/16/07, James Edward G. II [email protected] wrote:
n * fact(n-1)
(2…self).inject(1) { |f, n| f * n }
=> 28462596809170545189064132121198688901480514017…James Edward G. 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
On Apr 16, 1:56 pm, “Jason R.” [email protected] 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.
On 4/16/07, Trans [email protected] wrote:
Basic maybe, common debatable, Even if its a commonly used function (maybe
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 Tue, 17 Apr 2007, Trans wrote:
On Apr 16, 1:56 pm, “Jason R.” [email protected] 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
[email protected] wrote:
perhaps. perhaps not:
setup two factorial methods, one in ruby and in using inline. the inline
inline do |builder| } n.times{ Math.factorial_ruby 42 } a, b = Math.factorial_ruby(i), Math.factorial_inline(i)[5, 120, 120]
-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.
Tyler P. wrote:
The inject version should work for any value, as it is iterative.
Bound by available memory and computation time.
- Charlie
[email protected] 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.
“Trans” [email protected] writes:
On Apr 16, 1:56 pm, “Jason R.” [email protected] 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.
On 4/16/07, James Edward G. II [email protected] wrote:
end
endJames Edward G. 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
On Tue, 17 Apr 2007, Michael W. Ryder wrote:
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, Florian F. wrote:
module Factorial
assert_equal 24, fact(4) assert_equal 120, fact(5) assert_equal 3628800, fact(10)end
end
endThis 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
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
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
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