以下是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)
我不理解“在中间分割数字序列”这一步骤,尤其是在查看了的python实现之后 Karatsuba's algorithm
你能给我解释一下,我们到底该怎么分位吗?你知道吗
我已经写了一个非常简单的代码为Karatsuba算法,你可以尝试这个以及。。。你知道吗
可能这段代码很长,但很简单。你知道吗
在每次迭代中,将中间的数字按文本长度(以10为基数)打断。例如,六位数
123456
变成123
和456
。你知道吗对于不同长度的数字,请注意,该实现使用两个中的最大值。在给定
12345678
和100
的情况下,这个有效的方法将较短的数字用零填充到00000100
。分成两个4位数的数字,然后继续。你知道吗请注意,作为一种算法,这表示简单的二项式展开:
在8位数的情况下,我们的数字是
这有助于你的理解吗?你知道吗
相关问题 更多 >
编程相关推荐