Karatsuba乘法器

我乘兩個n位正整數與n位Karatsuba乘數。但大多數時候，這些子問題仍然需要處理兩位數字。那麼我應該再次使用n位Karatsuba算法遞歸地處理子問題嗎？這種方法有什麼冗餘？它會以任何方式損害計算時間（O（n^1.5））嗎？Karatsuba乘法器

來源

2013-01-11 zeroByte

東西不健全就在這裏;在Karatsuba乘法運算期間，你不應該回到n位數字。你可以發佈你的代碼或僞代碼，以便我們可以查看它嗎？ – templatetypedef

甲Karasuba減少降低了一個N×N的產品分成三個N/2×N/2產品。這就是'O（N^1.585）'來自的地方。有一個門檻，你應該切換回'O（N^2）'乘法。 – Mysticial

請發佈鱈魚，並告訴我們你的嘗試。 –

是的，你必須使用相同的方法。仍然爲足夠小的數字使用其他方法，因爲添加數字的開銷可能太大。

但這不是真的，你需要再乘以n位數字，你需要乘以n/2位數字。這是該方法的重點。

來源

2013-01-11 17:17:31

讓我們乘49 X 56（兩個2位數字）一個= 4×5 d = 9×6 E =（4 + 9）×（5 + 6） - A - d => E = 13 x 11 - a - d 我們可以看到，我們需要再次乘以13和11，它們又是兩個2位數字。那麼我應該再次在他們身上應用2位Karatsuba乘數嗎？ – zeroByte

@Ivaylo Strandjev 請回答zeroByte的評論.. – Hari

我不認爲小數字是很好的例子。每次迭代的數字數量是n/2的數量，但它可能有一個常數（本例中爲1）。這就是爲什麼我對少數人說不同的方法效果更好。作爲添加兩個n/2個數字可能會導致交叉污染，位數可以被1增加，這是在這種情況下發生了什麼。 –

Karatsuba乘法器

回答

相關問題