沒有浮點的MCU如何找到sqrt（2）？

Question

我被問了最後一次採訪這個問題，並期待它再次。採訪是爲嵌入式系統的固件工程師進行的。可用於這些應用的微處理器和微控制器通常功能不是很強大，而且更簡單的微處理器和微控制器不具備執行浮點計算的能力（內部不存在乘法器或分頻器）。

那麼對於這個問題，可能的答案是什麼，以及什麼（如果有的話）定點算術與此有關？

是否有可能使用牛頓 - 拉夫遜方法來做這個計算呢？怎麼樣？

Answer 1

像這樣的面試問題一樣，聰明的回答是問反問題。旨在澄清和消除這個問題的聰明問題表明，您可以思考而不是簡單地吐出所接受的智慧或教條，並且還會縮小問題的範圍，以便您的答案更適合於應用。在這種情況下，有可能是沒有浮點和軟件實現不使用浮點的MCU之間的區別。如果是後者，那麼肯定是固定點是相關的，但在許多應用中，根可能就足夠了 - 您可能會問這個問題，但isqrt（2）== 1在這種情況下似乎不夠充分。對於前者，這種情況並不排除使用浮點。

通常使用浮點時，在嵌入式系統中的問題是缺乏一個浮點單元（FPU），導致在軟件中實現是慢得多，少確定性浮點運算的。缺乏FPU甚至硬件整數乘法或除法並不排除使用浮點，它只是意味着這種操作速度較慢並且需要更大的代碼空間。

在大多數系統上，即使沒有硬件浮點支持，標準庫數學函數仍將由軟件浮點支持，並且可以正常使用 - 即使在8位系統上也可以使用 - 但不要期望得到Mega-FLOPS的性能。在某些情況下，性能問題以及可能的庫實現的非確定性特性妨礙了它的使用，在這種情況下，有許多算法返回更快或更確定的性能。

如果要生根的值很大，並且整數結果足夠精確，那麼純粹的整數解決方案將是最快的，但是對於一般情況，有許多解決方案，其中牛頓 - 拉夫遜是一個解決方案，但不太可能是最優的 - 它是泡沫排序的平方根算法;因爲它很容易教和理解，而不是因爲它的表現。

使用固定點是可能的，但不是本徵的數據類型，代碼可以成爲編寫和調試較少容易。我使用library written by Anthony Williams;它用C++編寫並定義了一個fixed類; C++的函數和運算符重載能力意味着只需將float或double替換爲fixed即可移植大多數浮點代碼。在ARM處理器上，fixed類的執行速度比軟件浮點快五倍。然而正如我基於製品The Neglected Art of Fixed Point Arithmetic描述here一實現安東尼的SQRT算法可以改善上 - 該文章中的代碼是在C語言所以可以更適用通常（其中C++是不可用或不實際的 - 雖然這是一個不同的論點！）。

Jack Crenshaw在他的書Math Toolkit for Real-Time Programming中用了一整章來介紹sqrt（）函數，他首先用一個簡單的Newton-Raphson實現並逐漸細化它。他還提出了一個整數解決方案，儘管有趣的是沒有定點。傑克在書中所包含的一些內容已經出現在他的期刊文章中;例如他的治療integer square-root。

無論哪種方式，我可以像下面這樣回答這個問題：

我將評估標準庫軟件浮點性能，精度和效果上的代碼大小和只有當我發現它是不夠的應用需求我會考慮使用已建立的算法和可能的定點算法的優化解決方案。

注意我使用術語「建立算法」的;它有效地避免了我可能不知道或回想任何特定算法的名稱這一事實，而我真正說的是我不知道什麼算法是合適的，但我不愚蠢地重新發明輪子，因爲我不太可能想出一些比現有技術更好的東西，並且通過仔細的研究和評估，如果可行的話，我會取得預期的結果。如果一位受訪者提出這個答案，並且事先詢問了一些聰明的問題，我會發現這不僅僅是可以接受的。當然，面試官可能不如你聰明，並且可能有一個特別的回答，他認爲他是「正確的」;你可能不想在這樣一個教條式的反應組織中工作。面試是一個雙向的過程 - 你正在採訪組織，看看你是否想給你的服務帶來好處。

Answer 2

ENIAC僅使用加法和減法取平方根。 它基於前n個奇數整數之和爲n平方的公式。

要計算m的平方根，找到最小的整數n，例如前n個奇數整數的和超過m。這可以通過從m中減去連續的奇數整數直到獲得否定結果來完成。如果n是最小的整數，那麼m - (1 + 3 + 5 + ... + 2n-1) < 0然後是(n - 1)^2 <= m < n^2。讓一個等於第n奇數2n - 1，解決了雙不等式(n-1) <= sqrt(m) < n爲

a - 1 <= 2*sqrt(m) < a + 1 

或

(a - 1)/2 <= sqrt(m) < (a + 1)/2 

來源： http://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm

然而，這並不真正爲米工作= 2，只適用於大數目。

Answer 3

是的，你可以用Newton-Raphson來計算平方根。通常它是這樣做的：

讓x是數字。我們首先接近1/sqrt（x），然後乘以x得到x/sqrt（x），即sqrt（x）。

給定x，創建1/sqrt（x）的粗略估計值。通常，這是通過一個小查找表完成的，但是任何合理的估計就足夠了（包括1）。調用初始估計值e 。

重複此步驟多次所希望的：從當前估值e _我，創建一個新的估值e _{i + 1的} = 1/2·è_我·（3-X·電子_我 ）。通常，可以通過數值分析，初始估計值1/sqrt（x）的質量以及應用程序所需的準確度來預先確定所需步驟的數量。

最後，返回最後的e _i·x用於估計sqrt（x）。

該序列收斂非常快，通常用於計算平方根。您可以從Wikipedia page on Newton’s method開始瞭解如何導出平方根倒數的這個序列。另外請注意，它不使用除法，這通常是一個緩慢的操作。

您將使用固定點進行這些計算，因爲您需要比整數提供更高的精度，但浮點不可用。

從本質上講，面試官正在調查，看你是否有對嵌入式處理器的數值算法經驗。