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><strong> Edited for correctness/brevity </strong></p>

<hr/>

<p>I have another approach that would take the load away from division and put it on multiplication. I would suggest taking advantage of the definition of combinations. Since combinations and permutations are counting techniques, losing precision through arithmetic operations is not good craftsmanship.</p>

<p>In the combination, you wanna cancel out the common factors in the numerator and the denominator as best as you can so that you can. So I'd say ditch your permutation function altogether, and your combination function would be something like...</p>

<pre><code>    def permute(n, k):
        // P(n,k) = n!/(n-k)!  mathematically
        largest_dividable_number = max(k, n-k)
        output_value = 1
        starting_value = n
        for i in range(1,largest_dividable_number - 1):
            output_value = output_value * starting_value
            starting_value = starting_value - 1
        return output_value

    def choose(n, k):
        p = permute(n,k)
        return p//math.factorial(k)
</code></pre>

python python-3.x