[issue37295] Possible optimizations for math.comb()

[Raymond Hettinger]

Raymond Hettinger <raymond.hettinger at gmail.com> added the comment:

Also, it would help Serhiy's divide and conquer algorithm if the fast cases included the sides of Pascal's triangle rather than just the top:

   if n < TableSize and k < limits[n]:
       return comb_small(n, k)
   return comb_slow(n, k)

Build the table like this:

    TableSize = 101
    limits = bytearray(TableSize)
    for n in range(0, TableSize):
        for k in range(0, n+1):
            if comb(n, k) != comb_small(n, k):
                break
        else:
            k += 1
        limits[n] = k

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue37295>
_______________________________________