我想实现 Karatsuba's 2-split multiplication在 Python 中。但是，在表格中写数字
A=c*x+d
其中 x 是接近 sqrt(A) 的底的幂 (令 x=b^m)。
如果我什至不能使用除法和乘法，我应该如何找到 x？我应该计算位数并将 A 向左移动位数的一半吗？
谢谢。
最佳答案
差不多。您不会将 A 移动一半的位数；你移动 1。当然，这只有在基数是 2 的幂时才有效，因为基数 10 的“移动”(例如)必须通过乘法来完成。 (编辑:嗯，好的，您可以通过移位和加法进行乘法运算。但是使用 2 的幂就简单多了。)
如果您使用的是 Python 3.1 或更高版本，计算位数很容易，因为 3.1 引入了 int.bit_length() 方法。对于其他版本的 Python，您可以通过复制 A 并将其右移直到它为 0 来计算位数。这可以使用一种二进制搜索方法在 O(log N) 时间(N = # of digits)中完成 - 移位许多位，如果它是 0 则太多，等等。
关于python - 关于karatsuba乘法的问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7461496/