瀏覽單個文章
沒問題
Major Member
 

加入日期: Dec 2015
文章: 210
引用:
作者Adsmt
這種特殊的算法是很多的,過去沒有計算機的時代,為了快速求解,發明了很多奇妙的算法。

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

因為你這算法看起來計算複雜度應該還是 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 就是魔術數字,計算反平方根卻出現一個固定的魔術數字,神奇吧?這是最佳化牛...


你好,這個東西我是知道的…
不過,這有助於快速計算除法嗎?
我還是很感謝你的介紹。

FFT配合牛頓切線法,可以達到 O(NlogNlogN)這我也是知道的。

現在我們回到問題的原點,你這篇提到的FFT變換,主要是使用軟體達成的,這只是一種計算方法,而不是一種計算步驟。
一般不會被實現成真實的計算電路。

我是沒有卡馬克厲害,我也不覺得我是『聰明』的工程師。
修正…
舊 2024-07-26, 06:34 PM #48
回應時引用此文章
沒問題離線中