瀏覽單個文章
Adsmt
Golden Member
 
Adsmt的大頭照
 

加入日期: Feb 2004
您的住址: 從來處來
文章: 2,762
這種特殊的算法是很多的,過去沒有計算機的時代,為了快速求解,發明了很多奇妙的算法。

你這算法並沒有比較快,但對於手算極大數來說確實能減少出錯率。但對現在來說,已經沒有任何意義。

因為你這算法看起來計算複雜度應該還是 O(N^2), 因為本質與長除法相同, 但現在用FFT配合牛頓切線法,可以達到 O(NlogNlogN), 如果用程式來算極大數,你這算法會被甩到連車尾燈都看不到。

還有電腦程式工程師比你想像中聰明多了,早就發明了快到你想都想不到的方法——魔術數字法。

反平方根快速演算法
https://zh.wikipedia.org/zh-hant/%E...%AE%97%E6%B3%95

程式碼中有一段

i = 0x5f3759df - ( i >> 1 );     // what the fuck?

其中的 0x5f3759df 就是魔術數字,計算反平方根卻出現一個固定的魔術數字,神奇吧?這是最佳化牛頓切線法來的。

(後面那段註解則可看出,當初使用這段程式的工程師的驚奇程度
舊 2024-07-26, 11:47 AM #46
回應時引用此文章
Adsmt現在在線上