I wrote:
As another data point, Python has also re-invented the GMP wheel, likely for the same licensing reasons. They have been using a simple implementation of Karatsuba multiplication for years. I have never heard of anyone complaining about it
Greg Fitzgerald wrote:
Looks like they swapped out their integer implementation for Python3
Interesting! This will be new in Python 3.2 - the first changes in many years. It's not exactly swapped out, but there are many changes. At first glance, it looks like better 64-bit support, a new division algorithm via floating-point, a new exponentiation algorithm using a 5-bits-at-a-time trick in some cases, optimized Read and Show instances (pardon the expression), a few other things. A lot of the new stuff seems to be from HAC. As before, everything is fully explained in expository comments inside the code, with references; a worthwhile read. Multiplication is still the same basic idea though - naive up to about 2000 bits, followed by just Karatsuba and nothing more. Thanks, Yitz