Handling big numbers in Python 3 for calculating combinations
<p>So I have a Python 3 script that calculates combinations in the following way</p>

<pre><code>def permutate(n, k):

    if k == 0:
        return 1
    elif n &lt; n - k + 1:
        return n
    else:
        return n * permutate(n - 1, k - 1)


def choose(n, k):

    if k &gt; n / 2:
    k = n - k

    return int(permutate(n, k) / permutate(k, k))
</code></pre>

<p>So my problem is when handling big numbers,</p>

<pre><code>choose(5, 3)
</code></pre>

<p>yields 10 which is correct.</p>

<pre><code>choose(1000, 1)
choose(52, 4)
choose(1000, 5)
choose(1000, 999)
</code></pre>

<p>These all yield the correct result, however when I try to pass</p>

<pre><code>choose(1000, 800)
</code></pre>

<p>I get the wrong result, the head of part of my resulting integer is correct but when I reach the tail part of the integer it is not correct, which leads me to believe that the problem lies in Python trying to handle the division of the two very large numbers in the choose function.</p>

<pre><code>return int(permutate(n, k) / permutate(k, k))
</code></pre>

<p>I'm sorry if I broke any rules or if the code formatting is way off, officially my first post :)</p>

<p>Here is another solution, which uses the <a href="https://docs.python.org/3.5/library/fractions.html" rel="nofollow">fractions</a> module to (by reducing to lowest terms) do the division as it goes along. It also uses the fact that e.g. <code>choose(100,70) = choose(100,30)</code> so as to not do unneeded multiplication:</p>

<pre><code>from fractions import Fraction

def choose(n,k):
    if k &gt; n//2: k = n - k
    p = Fraction(1)
    for i in range(1,k+1):
        p *= Fraction(n - i + 1, i)
    return int(p)
</code></pre>

<p>for example,</p>

<pre><code>&gt;&gt;&gt; choose(10000,100)
65208469245472575695415972927215718683781335425416743372210247172869206520770178988927510291340552990847853030615947098118282371982392705479271195296127415562705948429404753632271959046657595132854990606768967505457396473467998111950929802400
</code></pre>

<p>(which can be verified with a computer algebra system).</p>

<p>It is reasonably fast, taking about a second to find all 54341 digits of <code>choose(10**9, 10000)</code>.</p>

python python-3.x