5

分治法之整数乘法

 2 years ago
source link: https://lasttillend.github.io/algorithm,/divide/and/conquer/2020/05/26/dc_for_multiplication.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

分治法之整数乘法

May 26, 2020 • 唐涵

最近在看 Algorithms 的分治法（Divide and Conquer）部分，发现书中举的几个例子很有意思，今天想分享的就是第一个例子：用分治法优化整数乘法。这个例子虽然简单，但是非常巧妙。

假设xx和yy是两个nn-bit的整数，为了方便，假设nn是2的幂次。于是每个数都可以等分成左右各n/2n/2bit:

dc_multiplication_1.png

所以xx和yy就可以重新写成：

x=2n/2xL+xRy=2n/2yL+yR.x=2n/2xL+xRy=2n/2yL+yR.

它们的乘积也可以用xLxL、xRxR、yLyL和yRyR表示：

x⋅y=2nxLyL+2n/2(xLyR+xRyL)+xRyR.x⋅y=2nxLyL+2n/2(xLyR+xRyL)+xRyR.

这样写的好处是可以将nn-bit整数的乘法转换成4组n/2n/2-bit整数的乘法，逐个击破，最后将这四组结果合并。

下面我们来看看“分”和“治”分别花了多少时间。“分”的部分将每个数拆成左右各一半，这可以通过左移(left shift) n/2n/2个bit达成，所以耗费O(n)O(n)的力气；“治”的部分也可以由左移操作完成，耗费O(n)O(n)的力气。所以，递归式为

T(n)=4T(n/2)+O(n).T(n)=4T(n/2)+O(n).

等等，解这个递归式会得到T(n)=O(n2)T(n)=O(n2)，这和1位1位相乘再相加好像没有区别吧？是的，如果分割成四个子问题的话就和最”naive”的乘法没有区别了，但是这四个子问题之间是有关系的，中间一项xLyR+xRyLxLyR+xRyL可以写成

xLyR+xRyL=(xL+xR)(yL+yR)−xLyL−xRyR.xLyR+xRyL=(xL+xR)(yL+yR)−xLyL−xRyR.

也就是说，我们只要算xRyRxRyR、xLyLxLyL和(xL+xR)(yL+yR)(xL+xR)(yL+yR)这三组乘法就足够了，这就是精妙之处！

优化后的递归式为

T(n)=3T(n/2)+O(n),T(n)=3T(n/2)+O(n),

利用Master定理可以知道T(n)=O(nlog23)T(n)=O(nlog2⁡3)，大约为O(n1.59)O(n1.59)。

代码

# two 8-bit numbers
x = 0b10011011  # 155
y = 0b10111010  # 186

def multiply(x, y, n):
    """
    Multiply two n-bit positive integers.
    
    Args:
        x: int
        y: int
        n: int, assumed to be power of 2
    Returns:
        prod: int
    """
    if n == 1:
        return x * y
    
    x_l, x_r = divmod(x, 2 ** (n / 2))
    y_l, y_r = divmod(y, 2 ** (n / 2))
    
    p1 = multiply(x_l, y_l, n / 2)
    p2 = multiply(x_r, y_r, n / 2)
    p3 = multiply(x_l + x_r, y_l + y_r, n / 2)
    
    prod = p1 * 2 ** n + (p3 - p1 - p2) * 2 ** (n / 2) + p2
    return prod


multiply(x, y, 8)

输出结果：

28830.0

可以更快吗？

还有没有比这更快的整数乘法算法？答案是有的，需要用到书中之后介绍的快速傅立叶变换(FFT)，这也是接下来要填坑的主题。

参考资料

Dasgupta, S., Papadimitriou, C., & Vazirani, U. (2011). Algorithms. Boston: McGraw-Hill Higher Education.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK