CWYAlpha

Just another WordPress.com site

Thought this was cool: What are some efficient algorithms to compute nCr?

leave a comment »


In Algorithms: Cosmin Negruseri promoted an answer.

I was interested in this problem when doing coding contests.

  • If you need a one off for a relatively small number you can just code: factorial(n)/factorial(n-k)/factorial(k) This method is probably the fastest to code but has the slowest speed. Also it has the issue that even if the final result fits your data type the intermediary results may go out of range.
  • If you need nCr for lots of small values of n and r you can just precompute nCr = n-1Cr + n-1Cr-1 This doesn’t have the out of range issue.
  • When you need a one off and you want to avoid the out of range issue Anders’s suggestion works pretty well nCr = (n – r + 1)/r nCr-1 It’s pretty convenient that the results are always ints.
  • The fastest method I know is Vladimir’s method. One avoids division all together by decomposing nCr into prime factors. As Vladimir says you can do this pretty efficiently using Eratosthene’s sieve.

When n gets large you need to switch to Big Integers and that changes the problem a bit.

One needs to do large number multiplications efficiently. The current methods can fall into the trap that they multiply one number at a time to get the final result. This makes the complexity of the current best algorithm on the thread O(n^2).

What one should do instead is do some divide and conquer. Split the numbers in two halves, compute the result for each half and then use an efficient multiplication algorithm to compute the final result.

One could use Karatsuba‘s method (if you use Python) or some better algorithms based on the Fast Fourier Transform (if you use some external libraries). Using this you get an algorithm that has the complexity around O(n log^2(n) log log n).

Two speedup tricks :

  • Use a large base for your custom big integers. Instead of 10 one could use 1 billion and the intermediary results fit in a int64.
  • Use the int64 accumulators for multiplications of small numbers. Switch to big number multiplication when your accumulators are all filled.

See question on Quora

from Cosmin Negruseri on Quora: http://www.quora.com/Algorithms/What-are-some-efficient-algorithms-to-compute-nCr/answer/Cosmin-Negruseri

Written by cwyalpha

十二月 24, 2012 在 4:53 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: