這是 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)我不明白“拆分關(guān)于中間的數(shù)字序列”的步驟，尤其是在查看了Karatsuba 算法的 python 實(shí)現(xiàn)之后你能解釋一下，我們應(yīng)該如何分割數(shù)字序列？
2 回答
開(kāi)心每一天1111
TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超13個(gè)贊
在每次迭代中，您按文本長(zhǎng)度（以 10 為底）分隔中間的數(shù)字。例如，六位數(shù)字123456變?yōu)?code>123和456。
對(duì)于不同長(zhǎng)度的數(shù)字，請(qǐng)注意該實(shí)現(xiàn)適用于兩者中的最大值。鑒于12345678和100，這個(gè)有效的用零填充較短的數(shù)字，到00000100。將每個(gè)數(shù)字拆分為兩個(gè) 4 位數(shù)字并繼續(xù)。
請(qǐng)注意，作為一種算法，這表示簡(jiǎn)單的二項(xiàng)式展開(kāi)：
(a + b) * (c + d) = ac + ad + bc + bd
在 8 位數(shù)字的情況下，我們的數(shù)字是
(1234*10^4 + 5678) * (0000*10^4 + 0100)
這對(duì)你的理解有幫助嗎？
添加回答
舉報(bào)
0/150
提交
取消