Is factorial defined anywhere in Ruby’s core or standard library. If

not will it be in 1.9+?

Thanks,

T.

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

require ‘benchmark’

require ‘rubygems’

require ‘inline’

inline

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

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

42.times do |i|

a, b = Math.factorial_ruby(i), Math.factorial_inline(i)

p [i, a, b]

break unless a == b

end

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

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

Sponsor our Newsletter | Privacy Policy | Terms of Service | Remote Ruby Jobs