Ruby factorial function

Question

I'm going crazy: Where is the Ruby function for factorial? No, I don't need tutorial implementations, I just want the function from the library. It's not in Math!

I'm starting to doubt, is it a standard library function?

Solution 1

There is no factorial function in the standard library.

Solution 2

Like this is better

(1..n).inject(:*) || 1

Solution 3

It's not in the standard library but you can extend the Integer class.

class Integer
  def factorial_recursive
    self <= 1 ? 1 : self * (self - 1).factorial
  end
  def factorial_iterative
    f = 1; for i in 1..self; f *= i; end; f
  end
  alias :factorial :factorial_iterative
end

N.B. Iterative factorial is a better choice for obvious performance reasons.

Solution 4

Shamelessly cribbed from http://rosettacode.org/wiki/Factorial#Ruby, my personal favorite is

class Integer
  def fact
    (1..self).reduce(:*) || 1
  end
end

>> 400.fact
=> 64034522846623895262347970319503005850702583026002959458684445942802397169186831436278478647463264676294350575035856810848298162883517435228961988646802997937341654150838162426461942352307046244325015114448670890662773914918117331955996440709549671345290477020322434911210797593280795101545372667251627877890009349763765710326350331533965349868386831339352024373788157786791506311858702618270169819740062983025308591298346162272304558339520759611505302236086810433297255194852674432232438669948422404232599805551610635942376961399231917134063858996537970147827206606320217379472010321356624613809077942304597360699567595836096158715129913822286578579549361617654480453222007825818400848436415591229454275384803558374518022675900061399560145595206127211192918105032491008000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

This implementation also happens to be the fastest among the variants listed in Rosetta Code.

update #1

Added || 1 to handle the zero case.

update #2

With thanks and appreciation to Mark Thomas, here's a version that is a bit more efficient, elegant and obscure:

class Integer
  def fact
    (2..self).reduce(1,:*)
  end
end

Solution 5

In math, factorial of n is just the gamma function of n+1
(see: http://en.wikipedia.org/wiki/Gamma_function)

Ruby has Math.gamma() so just use Math.gamma(n+1) and cast it back to an integer if desired.

View more solutions

Comments

[sepp2k]

He explicitly said, he doesn't want an implementation.

[Pierre-Antoine LaFayette]

He may not; but people searching SO for "Ruby factorial" might.

[Michael Kohl]

From the docs: "Note that gamma(n) is same as fact(n-1) for integer n > 0. However gamma(n) returns float and can be an approximation". If one takes that into account, it works, but the reduce solution seems a lot more straight forward.

[chip]

what the heck does that mean?! yeah it's fast but its very unuserfriendly though

[Tarmo]

it's also incorrect for 0! - should be something like: if self <= 1; 1; else; (1..self).reduce(:*); end

[David J.]

Thanks for this! My gut says to use towards the standard library over a custom-written reduce whenever possible. Profiling might suggest otherwise.

[Douglas G. Allen]

rosettacode.org/wiki/Factorial#Ruby is just wrong. There isn't a case for 0

[SDJMcHattie]

@allen - Don't blame the language if you can't understand it. It simply means, take the range 1 to self, then remove the first element (1) from it (i.e. that's what reduce means in functional programming). Then remove the first element of what's left (2) and multiply (:*) those together. Now remove the first element from what's left (3) and multiply that with the running total. Keep going until there's nothing left (i.e. you've handled the entire range). If reduce fails (because the array is empty in the case of 0!) then just return 1 anyway.

[Ayarch]

Correction: After n = 22 it ceases to give an exact answer and produces approximations.

[fny]

Note: It's O(1) and precise for 0..22: MRI Ruby actually performs a lookup for those values (see static const double fact_table[] in the source). Beyond that, its an approximation. 23!, for instance, requires a 56-bit mantissa which is impossible to represent precisely using he IEEE 754 double which has a 53-bit mantissas.

[Andrew Marshall]

Or specify the initial value directly: (1..n).reduce(1, :*).

[Aleksei Matiushkin]

What’s wrong with class Integer ; def ! ; (1..self).inject(:*) ; end ; end?

[jasonleonhard]

@mudasobwa I like it, I have refactored for simplicity.

[MatzFan]

I'd respectfully suggest that overriding an instance method incorporated into all Ruby objects to return a truthy value, rather than a falsy one may not make you many friends.

[Dorian]

Ruby has the Math.gamma method, e.g. stackoverflow.com/a/37352690/407213

[Mark Thomas]

You can also handle the zero case by specifying the initial value in reduce: (1..self).reduce(1,:*).

[Mark Thomas]

Actually you can use (2..self).reduce(1,:*), if micro-efficiency is your thing :)

[Lex Lindsey]

Is the recursive version actually slower? It might depend on whether Ruby does tail-recursive optimization.

[Alexander Gorg]

What a crazy logic! We have (n-1)! function and don't have plain n! !!!

[nonopolarity]

It might be really dangerous to make the negate operator to become something else when a happens to be Integer in the case of !a... doing so may cause a bug to exist which is very hard to tell. If a happens to be a big number such as 357264543 then the processor is going into a big loop and people may wonder why the program all of a sudden becomes slow

[jasonleonhard]

This answer was more just a cool thing to share rather than a practical example to use.

[Neil Slater]

Worth noting that the fastest one Math.gamma(n+1) is also only approximate for n > 22, so may not be suitable for all use cases.

[Jaime Bellmyer]

I don't believe the recursive version is actually recursive. It calls factorial, which is aliased to factorial_iterative. It never recurses into itself. So it's indirectly iterative.

[Pablo]

I like it but it's useful up to 50,000; anything higher is not a match for.

[RixTheTyrunt]

Outputs 0 when tried with 5

[RixTheTyrunt]

Oh nevermind it worked with a fix

[Raksha Saini]

@RixTheTyrunt It worked with a fix. when we try any number in factorail_number(n). like factorial_number(5). Return 120

[RixTheTyrunt]

I replaced all 1 and <= but it returned 0 when tried with any number

[Raksha Saini]

@RixTheTyrunt Do you use:- puts factorial_number(5)? and getting 0.?