时间戳

首页 > 解决方案 > Karatsuba 算法：在中间分割数字序列

python - Karatsuba 算法：在中间分割数字序列

问题描述

以下是 karatsuba 算法的伪代码：

procedure karatsuba(num1, num2)
    if (num1 < 10) or (num2 < 10)
        return num1*num2

    /* calculates the size of the numbers */
    m = max(size_base10(num1), size_base10(num2))
    m2 = m/2

    /* split the digit sequences about the middle */
    high1, low1 = split_at(num1, m2)
    high2, low2 = split_at(num2, m2)

    /* 3 calls made to numbers approximately half the size */
    z0 = karatsuba(low1, low2)
    z1 = karatsuba((low1+high1), (low2+high2))
    z2 = karatsuba(high1, high2)

    return (z2*10^(2*m2)) + ((z1-z2-z0)*10^(m2)) + (z0)

我不明白“在中间分割数字序列”这一步，尤其是在查看了 Karatsuba 算法的 python 实现之后

你能解释一下，我们应该如何分割数字序列？

标签： pythonalgorithm

解决方案

在每次迭代中，您将中间的数字按文本长度（以 10 为底）进行拆分。例如，六位数字123456变为123and 456。

对于不同长度的数字，请注意该实现适用于两者中的最大值。给定12345678和100，这个有效的用零填充较短的数字，到00000100。分成两个 4 位数字并继续。

请注意，作为一种算法，这表示简单的二项式展开：

(a + b) * (c + d) = ac + ad + bc + bd

在 8 位的情况下，我们的数字是

(1234*10^4 + 5678) * (0000*10^4 + 0100)

这对你的理解有帮助吗？

推荐阅读