Author tim.peters
Recipients kellerfuchs, mark.dickinson, rhettinger, serhiy.storchaka, steven.daprano, tim.peters
Date 2018-12-13.05:58:17
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1544680698.1.0.788709270274.issue35431@psf.upfronthosting.co.za>
In-reply-to
Content
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.
History
Date User Action Args
2018-12-13 05:58:18tim.peterssetrecipients: + tim.peters, rhettinger, mark.dickinson, steven.daprano, serhiy.storchaka, kellerfuchs
2018-12-13 05:58:18tim.peterssetmessageid: <1544680698.1.0.788709270274.issue35431@psf.upfronthosting.co.za>
2018-12-13 05:58:18tim.peterslinkissue35431 messages
2018-12-13 05:58:17tim.peterscreate