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>Problem is: all your divisions use floating point whereas they are clearly targeted as integer.</p>

<p>Python 3 acts differently from Python 2.</p>

<pre><code>3/2 =&gt; 1.5
3//2 =&gt; 1
</code></pre>

<p>Replace <code>/</code> by <code>//</code> (no need to cast in integer like you did)</p>

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

<p>also here (less important)</p>

<pre><code>if k &gt; n // 2
</code></pre>

python python-3.x