我需要盡可能有效地乘以幾個大的長整數。
我正在嘗試實作 Harvey & van der Hoeven 2019 整數乘法演算法，但我堅持理解其背后的定義和數學，尤其是 Agarwal–Cooley 演算法。
任何理解這個演算法的幫助，比如一個實際的例子或一些偽代碼，將不勝感激。
uj5u.com熱心網友回復：
請記住，大 O 表示法是這樣定義的，即存在一些 x≥x?，對于所有這樣的 x，一些函式 |f(x)|≤εg(x)。
Harvey & van der Hoeven (2019) 演算法的問題在于所涉及的 x? 非常大。因此，對于大多數輸入，他們的演算法提供了一種低效率地乘以整數的方法。但是，對于非常大的數字，該演算法確實給出了O(n log n)演算法。
但這些數字有多大？作者之一大衛哈維說：
新演算法在當前形式下并不實用，因為我們論文中給出的證明僅適用于可笑的大數。即使每個數字都寫在氫原子上，在可觀測的宇宙中也幾乎沒有足夠的空間來寫下它們。
另一方面，我們希望通過進一步改進，該演算法可能對僅具有數十億或數萬億位數的數字變得實用。如果是這樣，它很可能成為計算數學家武器庫中不可或缺的工具。
因此，如果你認真對待你的既定目標——快速乘以大數字——這個演算法不是你應該做的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409386.html
標籤：
上一篇：找到一組三元組的最大GCD