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
2012/2/17 Junayeed Ahnaf N. [email protected]:
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.
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.
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,
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.
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?