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 + b) * (c + d) = ac + ad + bc + bd

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

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

这对你的理解有帮助吗？