Tim Peters <t...@python.org> added the comment:
My two cents: - Spell it comb(n, k). - TypeError if args aren't ints. - ValueError if not 0 <= k <= n. Not concerned about speed. It's possible to do this with no divisions involving integers bigger than `n` and `k`(*), using O(k) space, but for "practical" arguments I bet that's slower than the dumbest possible loop. (*) Sketch: make lists of the k numerators and k-1 denominators (skip 1). For each prime P <= k, a modulus operation can determine the index of the first multiple of P in each list. For that, and for each P'th later list element, divide out the multiples of P, adding 1 to a running count for numerators, subtracting 1 for denominators, and reducing each list element by the Ps divided out. Then if the final P count isn't 0 (it will always be >= 0), append pow(P, count) to a list of factors. pow() is efficient. After that, all the denominators will be reduced to 1, so can be ignored thereafter. It just remains to multiply all the reduced numerators and prime-power factors. Catenate them all in a single list, heapify it (min heap), and so long as at least 2 factors remain pop the two smallest and push their product. This attempts to balance bit lengths of incoming factors, allowing close-to-best-case-for-it Karatsuba multiplication to kick in. But that's nuts ;-) To get even nutsier, special-case P=2 to use shifts instead, skip adding pow(2, count) to the list of factors, and just shift left by the count at the end. That said, even the "dumbest possible loop" may benefit in C by shifting out all trailing zeroes, multiplying/dividing only odd integers, and shifting left at the end. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue35431> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
