變長＃秒[概念]

的有效倍增所以看起來我「低估」不同長度的數字是什麼意思。我甚至沒有想到操作數爲100位數的情況。在那種情況下，我提出的算法肯定是不高效的。我可能需要一個實現複雜性的實現取決於每個操作數中的數字，而不是其數值，對吧？

如下的建議，我會考慮的karatsuba算法...

寫一個算法，在兩個任意長度的數字需要（如串提供）的僞代碼，並計算產品這些數字。使用一個有效的程序來乘以大量的任意長度。分析算法的效率。

我決定採取（半）簡單的方法，並使用俄羅斯農民算法。它的工作原理是這樣的：

a * b = a/2 * 2b if a is even 
a * b = (a-1)/2 * 2b + a if a is odd

我的僞代碼：

rpa(x, y){ 
    if x is 1 
     return y 
    if x is even 
     return rpa(x/2, 2y) 
    if x is odd 
     return rpa((x-1)/2, 2y) + y 
}

我有3個問題：

這是有效的任意長度的數字？我用C實現它，嘗試了不同的長度數字。在所有情況下，運行時間幾乎是瞬間的，因此很難根據經驗來說明...
我可以應用主定理來理解複雜性嗎？
- 在遞歸一個=＃子問題= 1（最大1遞歸跨越所有狀態呼叫）
- N/B =大小每個子問題= N/1的 - > B = 1（問題不改變大小.. ？）
- f（n^d）=在遞歸調用外完成的工作= 1 - > d = 0（當a是奇數時的加法）
- a = 1，b^d = 1，a = b^d - >複雜性在n^d * log（n）= log（n）
- 這在邏輯上合理，因爲我們在每一步都將問題減半，對嗎？
我的教授通過提供任意長度的「字符串」可能意味着什麼。爲什麼這樣做？

提前

非常感謝

來源

2012-03-24 Milan Patel

他想給你的數字作爲字符串，因爲你使用的任何語言的內置數據類型都被限制在某個最大大小。如果他希望你通過23459876235987623598723645982346598234659823465982346529834乘以198347523458623586235875932485，那麼字符串就可以很好地表示這些數字。我猜你現在的算法不能處理那些輸入...... – 2012-03-24 23:21:24

你的教授意味着這些數字可能太大而不適合機器字，所以他們必須被提供爲任意長度的ASCII字符串（據推測）以10爲底。例如，「123456789876543211112222333344445」。所以你的算法恐怕是不完整的。但是你也可以在字符串上使用俄羅斯農民算法 - 你只需要做更多的工作： -/ – TonyK 2012-03-24 23:22:46

哦，我明白了。有道理 - 謝謝你清理那個。 – 2012-03-24 23:23:32

添加3）：母語整數被他們如何能大（或小）的數字代表（例如32位或64位整數）的限制。爲了表示任意長度的數字，你可以選擇字符串，因爲那樣你就不會受到這個限制。當然，問題在於你的算術單元不是真的要添加字符串;-)

來源

2012-03-24 23:22:14 tchap

我的教授通過提供任意長度的數字「as strings」可能意味着什麼。爲什麼這樣做？

這實際上改變了有關問題的一切（並使您的算法不正確）。這意味着1234被提供爲1,2,3,4，你不能直接操作整個號碼。您需要根據#additions，＃multiplus，#divisions來分析您的算法。你應該期望一個部門比一個乘法部分貴一點，並且乘法比一個加法部件昂貴得多。所以一個好的算法試圖減少分割和乘法的次數。

查看Karatsuba algorithm，（ps不要複製它，這不是你的老師想要的）是本規範最快的之一。

來源

2012-03-24 23:26:53 UmNyobe

謝謝！我會重新考慮這個問題，以及使用哪些操作，並看看Karatsuba ... – 2012-03-24 23:43:32

實際上，如果你能夠理解karatsuba在你可以根據需要再次證明它的複雜性的時候，你也可以使用它。 – UmNyobe 2012-03-24 23:48:50

Karatsuba很好的資源，完成一個遞歸樹（我如何理解一切;））：http://ozark.hendrix.edu/~burch/csbsju/cs/160/notes/31/1.html – 2012-03-25 00:07:42

變長＃秒[概念]

回答

相關問題