這個發現平方根算法的名稱是什麼？

的算法如下：這個發現平方根算法的名稱是什麼？

res <- 0 
for i from 15 downto 0 do: 
    change the ith bit of result to 1 
    if res^2 > x then: 
     change the ith bit of res back to 0 
return res

我完全理解它是如何工作的，但我不知道這是什麼方法被調用。我一直在尋找wiki的平方根計算方法，但無濟於事。這是數字的方法嗎？

來源

2017-09-29 whoshotya

在其他領域（尤其是模數轉換）中，該過程稱爲「逐次逼近」。儘管如此，牛頓的方法也被稱爲「逐次逼近」。你可以把這種方法稱爲「二進制逐次逼近」來區分它。它不用於平方根，因爲牛頓的方法收斂速度更快。 –

這個很清楚，維基百科稱之爲[按位數算法]（https://en.wikipedia.org/wiki/Integer_square_root#Digit-by-digit_algorithm），使用位運算來實現基-2。順便說一下，在現代x86硬件上，最快的整數sqrt是使用FP雙精度硬件。在Haswell中，轉換爲/來自'double'的每個方法都是4個週期的延遲，再加上'sqrtsd'的16個週期延遲。（而且它只有3個指令/ 5個微指令，所以如果還有別的事情需要，無序執行可以很容易地隱藏這個等待時間。） –

它看起來像是一個時代的古老遺蹟，CPU甚至沒有乘法指令。可以很容易地避免使用res^2（通過使用res和res 2的兩個不同值，用0x8000和0x40000000初始化：一個res - 右移1位，另一個res - 每個循環2位），之後這可以很容易地實現在6502和類似的CPU – Tommylee2k

正如彼得·柯德斯在評論中提到的，這是digit-by-digit algorithm（這裏二進制位）。

這是一種二分查找。如果平方結果接近於x但不超過它，則設置第i位，因此添加兩個近似值所需的功率結果會越來越好。

來源

2017-09-29 04:15:34 MBo

我不確定這實際上是否回答了這個問題，雖然..「...種類的二進制搜索」不是一個真正的名字。 –

@David：但是「逐位數算法」確實會回答它，IMO。 –

我同意。這不是原來的答案。 –

這個發現平方根算法的名稱是什麼？

回答

相關問題