Karatsuba 的算法：分割关于中间的数字序列

Question

这是 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 实现之后

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

Answer 1

在每次迭代中，您按文本长度（以 10 为底）分隔中间的数字。例如，六位数字123456变为123和456。对于不同长度的数字，请注意该实现适用于两者中的最大值。鉴于12345678和100，这个有效的用零填充较短的数字，到00000100。将每个数字拆分为两个 4 位数字并继续。请注意，作为一种算法，这表示简单的二项式展开：(a&nbsp;+&nbsp;b)&nbsp;*&nbsp;(c&nbsp;+&nbsp;d)&nbsp;=&nbsp;ac&nbsp;+&nbsp;ad&nbsp;+&nbsp;bc&nbsp;+&nbsp;bd在 8 位数字的情况下，我们的数字是(1234*10^4&nbsp;+&nbsp;5678)&nbsp;*&nbsp;(0000*10^4&nbsp;+&nbsp;0100)这对你的理解有帮助吗？