关于karatsuba乘法的问题

Question

我想在Python中实现Karatsuba的2分割乘法.但是,在表单中写入数字

A=c*x+d

其中x是基数(let x = b ^ m)接近sqrt(A)的幂.

如果我甚至不能使用除法和乘法,我该如何找到x？我应该计算位数并将A向左移动一半的位数吗？

谢谢.

Answer 1

几乎。您不会将 A 移动一半的位数；你移位 1。当然，只有当基数是 2 的幂时，这才有效，因为基数 10（例如）的“移位”必须通过乘法来完成。（编辑：好吧，你可以通过移位和加法来进行乘法。但是使用 2 的幂就简单多了。）

如果您使用的是 Python 3.1 或更高版本，计算位数很容易，因为 3.1 引入了该int.bit_length()方法。对于其他版本的 Python，您可以通过复制 A 并将其右移直到为 0 来计算位数。这可以通过一种二分搜索方法在 O(log N) 时间内完成（N = 位数） - 移位很多位，如果它是 0 那就太多了，等等。