benrg <benrud...@gmail.com> added the comment:
My example used ints, but I was being deliberately vague when I said "bignums". Balanced-tree reduction certainly isn't optimal for ints, and may not be optimal for anything, but it's pretty good for a lot of things. It's the comparison-based sorting of reduction algorithms. * When the inputs are of similar sizes, it tends to produce intermediate operands of similar sizes, which helps with Karatsuba multiplication (as you said). * When the inputs are of different sizes, it limits the "damage" any one of them can do, since they only participate in log2(n) operations each. * It doesn't look at the values, so it works with third-party types that are unknown to the stdlib. There's always a fallback case, and balanced reduction is good for that. If there's a faster path for ints that looks at their bit lengths, great. ---------- _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue46868> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
