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

on 2007-04-16 19:38

on 2007-04-16 19:57

No and most likely not. def fact(n) if n == 0 1 else n * fact(n-1) end end Jason

on 2007-04-16 20:59

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

on 2007-04-16 21:26

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 => nil >> 0.fact => 1 >> 1.fact => 1 >> 10.fact => 3628800 >> 10_000.fact => 28462596809170545189064132121198688901480514017... James Edward Gray II

on 2007-04-16 21:36

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote: > >> n * fact(n-1) > >> (2..self).inject(1) { |f, n| f * n } > => 28462596809170545189064132121198688901480514017... > > James Edward Gray 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 2007-04-16 22:21

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

on 2007-04-16 22:37

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 Prete

on 2007-04-17 02:07

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

on 2007-04-17 03:51

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

on 2007-04-17 04:33

On 4/16/07, Trans <transfire@gmail.com> 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 2007-04-17 10:20

ara.t.howard@noaa.gov 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.

on 2007-04-17 11:11

```
Tyler Prete wrote:
> The inject version should work for any value, as it is iterative.
Bound by available memory and computation time.
- Charlie
```

on 2007-04-17 12:33

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.

on 2007-04-17 13:11

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

on 2007-04-17 13:13

On 4/16/07, James Edward Gray II <james@grayproductions.net> wrote: > >> end > >> end > > 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

on 2007-04-17 16:44

On Tue, 17 Apr 2007, Florian Frank wrote: > module Factorial > > 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

on 2007-04-17 16:45

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 2007-04-18 06:38

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

on 2007-04-18 17:36

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

on 2007-04-20 21:12

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

on 2007-04-21 03:43

Gary Thomas wrote: > 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 > A rule of thumb I was taught in the days when compute power was expensive was that any factorial over 10! should be done using Stirling's approximation. I think that's a reasonable strategy even today. -- M. Edward (Ed) Borasky, FBG, AB, PTA, PGS, MS, MNLP, NST, ACMC(P) http://borasky-research.net/ If God had meant for carrots to be eaten cooked, He would have given rabbits fire.