Hello,

What is the most efficient way in Ruby to calculate the factorial of any

given sum? Is there any way to make it as fast as in C?

Complexity doesn’t matter as long as it works correctly.

Hello,

What is the most efficient way in Ruby to calculate the factorial of any

given sum? Is there any way to make it as fast as in C?

Complexity doesn’t matter as long as it works correctly.

y = 1 # this will be the value of your factorial at the end, initialize

to 1

j = 5 #You will get the factorial for j+1. Eg if you wanted 5! you

would have j = 4

j.times { |x| y += y*(x+1) } #gives you the factorial for j + 1

puts y

iterative method

p (2…5).inject(factorial = 1) {|factorial,j| factorial *= j }

recursive method

class Integer

def my_fact

return 1 if self < 2

self * (self - 1).my_fact

end

end

p 5.my_fact

On Fri, 2012-02-17 at 18:35 +0900, Junayeed Ahnaf N. wrote:

Hello,

What is the most efficient way in Ruby to calculate the factorial of any

given sum? Is there any way to make it as fast as in C?Complexity doesn’t matter as long as it works correctly.

see the first example here

http://www.zenspider.com/ZSS/Products/RubyInline/

2012/2/17 Junayeed Ahnaf N. [email protected]:

given sum? Is there any way to make it as fast as in C?Complexity doesn’t matter as long as it works correctly.

How about Math.gamma(n+1).to_i for fact(n) assuming n <= 22 ?

If the restriction, n <= 22 is not acceptable,

table lookup is another option.

I think C is not so useful here because fact(21) overflows 64bit signed

int.

http://en.wikipedia.org/wiki/Factorial#Computation

You can not get as fast as C, unless you write a C extension.

For practical purposes and non-gigantic numbers, I would just

precompute all values we care about and store them in an array.

– Matma R.

2012/2/17 Junayeed Ahnaf N. [email protected]:

This method isn’t as fast as using Math.gamma, but I believe any

reasonable

factorial can be calculated.

A factorial of 10,000 benchmarked at 0.121007 seconds using this

approach,

where 100,000 took 14.354879 seconds.

(1…n).inject(:*)

On Fri, Feb 17, 2012 at 1:35 AM, Junayeed Ahnaf N. <

[email protected]> wrote:

Hello,

given sum? Is there any way to make it as fast as in C?Complexity doesn’t matter as long as it works correctly.

Just precalculate all the factorials and put them in Mongodb.

On Fri, Feb 17, 2012 at 12:12 PM, Tony A.

[email protected]wrote:

On Fri, Feb 17, 2012 at 1:35 AM, Junayeed Ahnaf N. <

[email protected]> wrote:Just precalculate all the factorials and put them in Mongodb.

–

Tony A.

this gives pretty good performance:

@stat = []

def fact n

n == 0 ? 1 : @stat[n] ||= n * fact(n-1)

end

though for big numbers ( > 10k) you have to go up by multiples of 5k in

order to not have a stack overflow… in that case you can use the

inject

method given above… and if you then have a *huge* table, you can

stick

it into something like mongodb… increase complexity only when needed.

hex

–

- my blog is cooler than yours: http://serialhex.github.com
- The wise man said: “Never argue with an idiot. They bring you down to

their level and beat you with experience.” - As a programmer, it is your job to put yourself out of business. What

you do today can be automated tomorrow. ~Doug McIlroy

No snowflake in an avalanche ever feels responsible.

CFO: What happens if we train people and they leave?

CTO: What if we dont and they stay?

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