前回のインタビューでこの質問をされましたが、また期待しています。インタビューは、組み込みシステムをプログラムするファームウェアエンジニアを対象としています。これらのアプリケーションで使用できるマイクロプロセッサとマイクロコントローラは、通常はそれほど強力ではなく、単純なものには浮動小数点計算を実行する機能がありません（内部に乗算器または除算器はありません）。
では、この質問に対する考えられる答えは何であり、固定小数点演算はこれと（もしあれば）何の関係があるのでしょうか？
ニュートンラプソン法を使用してこの計算を行うことは可能ですか？どのように？
このような面接の質問と同様に、賢明な対応は反対の質問をすることです。質問を明確にし、曖昧さを解消することを目的とした賢明な質問は、受け取った知恵や教義を単に吐き出すのではなく、考えることができることを示しています。また、質問の範囲を狭めて、答えがより適切になりやすいようにします。この場合、浮動小数点のないMCUと浮動小数点を使用しないソフトウェア実装にはおそらく違いがあります。後者の場合、確かに固定小数点が適切ですが、多くのアプリケーションでは整数二乗ですルートで十分かもしれません-あなたはそれについて尋ねるかもしれませんが、この場合、isqrt（2）==1は適切ではないようです。前者の場合、この状況は浮動小数点の使用を排除するものではありません。
通常、浮動小数点を使用する場合の組み込みシステムの問題は、浮動小数点ユニット（FPU）がないため、ソフトウェアに実装されている浮動小数点演算がはるかに遅くなり、決定論的ではなくなることです。FPUの欠如、またはハードウェア整数の乗算または除算でさえ、浮動小数点の使用を排除するものではありません。これは、そのような操作がはるかに遅く、より大きなコードスペースを必要とすることを意味します。
ほとんどのシステムでは、ハードウェア浮動小数点のサポートがなくても、標準ライブラリの数学関数はソフトウェア浮動小数点でサポートされ、8ビットシステムでも通常どおり使用できますが、 Mega-FLOPSのパフォーマンスは期待できません。パフォーマンスが低下し、ライブラリ実装の非決定論的性質によってその使用が妨げられる場合があります。その場合、より高速またはより決定論的なパフォーマンスを返すアルゴリズムが多数あります。
根付く値が大きく、整数の結果が十分に正確である場合、純粋な整数の解が最速になりますが、一般的なケースでは、ニュートンラプソンが1つであるが、最適ではない可能性が高い解がいくつかあります-それはむしろバブルソートの平方根アルゴリズムです。パフォーマンスのためではなく、教えて理解しやすいために使用されます。
固定小数点を使用することは可能ですが、固有のデータ型ではないため、コードの記述とデバッグが容易でなくなる可能性があります。私はAnthonyWilliamsによって書かれたライブラリを使用しています。これはC++で記述されており、fixedクラスを定義します。floatC ++の関数と演算子のオーバーロード機能は、ほとんどの浮動小数点コードを、またはdoubleで置き換えるだけで移植できることを意味しfixedます。ARMプロセッサでは、fixedクラスはソフトウェア浮動小数点の約5倍の速度で実行されます。ただし、Anthonyのsqrtアルゴリズムは、記事The Neglected Art of Fixed Point Arithmeticに基づく実装でここで説明したように、改善することができます。-その記事のコードはCであるため、より一般的に適用できる可能性があります（C ++が利用できないか、実用的でない場合-それは別の議論ですが！）。
Jack Crenshawは、彼の著書 『 Math Toolkit for Real-Time Programming』のsqrt（）関数に全章を捧げています。ここでは、ナイーブなニュートンラプソン実装から始めて、徐々に改良していきます。彼はまた、興味深いことに不動点ではありませんが、整数解を提示します。ジャックが本に含めているもののいくつかは、彼のジャーナル記事にすでに掲載されています。たとえば、彼の整数平方根の扱い。
いずれにせよ、私は次のように質問に答えるかもしれません：
標準ライブラリソフトウェアの浮動小数点パフォーマンス、精度、およびコードサイズへの影響を評価し、アプリケーション要件に対して不十分であることがわかった場合にのみ、確立されたアルゴリズムと場合によっては固定小数点演算を使用した最適化されたソリューションを検討します。
「確立されたアルゴリズム」という用語の使用に注意してください。特定のアルゴリズムの名前を知らない、または思い出せない可能性があるという事実を有効に排除します。実際に言っているのは、どのアルゴリズムが適切かわからないということですが、私はありそうもないので、車輪の再発明をするほど愚かではありません。まだ入手できないものよりも優れたものを考え出すために、そして慎重な調査と評価を通して、可能であれば、私は望ましい結果を達成するでしょう。面接対象者がその答えを思いつき、事前に賢明な質問をした場合、それは許容範囲を超えていると思います。もちろん、インタビュアーはあなたほど頭が良くないかもしれません、そして彼が「正しい」と信じているという特定の答えを心に留めているかもしれません「1つ。そのような独断的な反応を示す組織で働きたくない場合があります。面接は双方向のプロセスです。組織に面接して、サービスのメリットを提供するかどうかを確認します。
はい、ニュートンラプソン法を使用して平方根を計算できます。通常、次のように実行されます。
xを数とします。最初に1/sqrt（x）を概算し、次にそれをxで乗算して、sqrt（x）であるx / sqrt（x）を生成します。
xが与えられた場合、1 / sqrt（x）の大まかな見積もりを作成します。多くの場合、これは小さなルックアップテーブルを使用して行われますが、妥当な見積もりで十分です（1を含む）。初期推定値をe0と呼びます。
この手順を必要な回数繰り返します。現在の推定値eiから、新しい推定値e i + 1 = 1/2・e i・（3-x・e i 2）を作成します。通常、必要なステップ数は、数値解析、1 / sqrt（x）の初期推定の品質、およびアプリケーションに必要な精度から事前に決定できます。
最後に、 sqrt（x）の推定値として最後のe i・xを返します。
このシーケンスは非常に速く収束し、平方根を計算するために一般的に使用されます。ニュートン法に関するウィキペディアのページから始めて、平方根の逆数のこのシーケンスがどのように導出されるかを理解できます。また、除算を使用しないことにも注意してください。除算は、多くの場合、遅い操作です。
これらの計算には固定小数点を使用します。整数が提供するよりも高い精度が必要ですが、浮動小数点は使用できないためです。
基本的に、インタビュアーは、組み込みプロセッサで数値アルゴリズムを使用した経験があるかどうかを調査していました。
ENIACは、加算と減算のみを使用して平方根を取りました。これは、最初のn個の奇数の整数の合計がnの2乗であるという式に基づいています。
mの平方根を計算するには、最初のn個の奇数の整数の合計がmを超えるような最小の整数nを見つけます。これは、負の結果が得られるまで、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
ただし、これはm = 2の場合は実際には機能せず、多数の場合にのみ機能します。