关于Karatsuba乘法的问题

Question

我想在Python中实现Karatsuba的二分乘法。不过，我需要把数字写成这样的形式：

A=c*x+d

这里的x是一个接近A平方根的基数的幂（也就是x=b^m）。

如果我连除法和乘法都不能用，那我该怎么找到x呢？我是不是应该先算一下数字的位数，然后把A向左移动半个数字的位数？

谢谢。

Answer 1

你的问题在你提到的文章中已经有答案了：“Karatsuba的基本步骤适用于任何进制B和任何m，但当m等于n/2（向上取整）时，递归算法效率最高。”这里的n是数字的位数，而0 <= 数字的值 < B。

这里有一些背景信息，可能会对你有帮助：

你可以（而且必须！）使用一些基本的操作，比如number_of_digits // 2和divmod(digit_x * digit_x, B)……在学校的算术中，如果B是10，你需要知道，比如说，divmod(9 * 8, 10)会得到(7, 2)。

在计算机上实现大数运算时，通常会选择B为最大的2的幂，这样可以方便地进行基本的乘法操作。例如，在32位机器上的CPython实现中，B被选为2 ** 15（即32768），因为这样product = digit_x * digit_y; hi = product >> 15; lo = product & 0x7FFF;就可以在没有溢出和符号位问题的情况下正常工作。

我不太明白你想用B == 2在Python中实现什么，因为Python的整数已经在C语言中使用Karatsuba算法来乘以足够大的数字，这样做并不会提高速度。

作为一个学习练习，你可以尝试把一个数字表示成一个数字列表，进制B作为输入参数。

Answer 2

你已经接受了一个答案，而我刚开始写这个，但我想补充一下：

汤姆说的对：在Python 3.x中，你可以直接用int.bit_length()来获取n的值。

而在Python 2.x中，你可以通过二分查找的方法在O(log2(A))的时间内得到n，下面是具体的做法。

这里有一段（2.x版本的）代码，可以计算出这两个值。假设x的以2为底的指数是n，也就是说x = 2**n。

首先，我们通过位移的方法进行二分查找来得到n。（其实我们只需要n的一半，所以最后一次迭代是多余的）。

当我们知道n后，得到x、c、d就变得简单了（仍然没有使用除法）。

def karatsuba_form(A,n=32):
    """Binary-search for Karatsuba form using binary shifts"""
    # First search for n ~ log2(A)
    step = n >> 1
    while step>0:
        c = A >> n
        print 'n=%2d step=%2d -> c=%d' % (n,step,c)
        if c:
            n += step
        else:
            n -= step
        # More concisely, could say: n = (n+step) if c else (n-step)
        step >>= 1
    # Then take x = 2^(n/2) ˜ sqrt(A)
    ndiv2 = n/2
    # Find Karatsuba form
    c = (A >> ndiv2)
    x = (1 << ndiv2)
    d = A - (c << ndiv2)
    return (x,c,d)

Answer 3

差不多。你并不是把A的位数减半，而是只移动1位。当然，这种方法只有在底数是2的幂时才有效，因为在10进制下“移动”就得用乘法来实现。（补充一下：其实你可以用移动和加法来乘法，但用2的幂来做会简单得多。）

如果你使用的是Python 3.1或更高版本，计算位数就很简单，因为3.1引入了int.bit_length()这个方法。对于其他版本的Python，你可以通过复制A，然后不断右移直到它变成0来计算位数。这种方法可以用一种类似二分查找的方式在O(log N)的时间内完成（N是位数的数量）——先移动很多位，如果结果是0，那就说明移动得太多了，等等。