固定小数点の計算。 基本原則（パート1）

はじめにまたはなぜこのトピック

Habrahabrを読んで、「澄んだ水で表示する」浮動小数点計算という2つのトピックに出会いました。
IEEE754規格からの絞り込みと浮動小数点計算の主な問題の1つは十分な詳細と品質で提供され、 もう1つはPCでの計算がすべてがうまくいくわけではないという短いトピックノートです。 同時に、結果の数学的精度が重要な場合、整数計算を使用する、「コンマを修正する」、または少なくともプラットフォーム（コンパイラ+プロセッサ）によって生成された結果を確認するときに推奨事項が与えられます。
アドバイスが実用的であるという事実にもかかわらず、以前に浮動小数点があった整数計算を使用する方法を理解することは、特に数学的な準備なしでは容易ではありませんでした。 この意味で、「ハブロフスク市民」の一人が実験的手法を使用して不動点に対処しようとする試みは非常に興味深いものです。
このトピックは簡単な紹介であり、固定小数点計算のアイデアを提供します。 この記事の数学は誰をも怖がらせるべきではありません-すべてが非常に原始的です。 すぐに許してください。私の友人の間では、確立された表現は正確に「 英語からの固定小数点」であり、「コンマ」ではありません。したがって、私はこの用語に固執します。

仮数と指数についてもう一度

計算数学では、小数値は整数のペア（n、e）として表されます。仮数と指数（ロシア語では「指数」はより真実ですが、簡潔さと習慣のために、将来は「指数」という言葉を使用します）。 ペアはn * 2 ^-eの形式の小数を表します。
指数は、数値の小数部分を区切る小数点の前の桁数と見なすことができます。
指数がレジスタに書き込まれ、コンパイル時に不明な変数である場合、 （n、e）は浮動小数点数と呼ばれます。 指数が事前にわかっている場合、 （n、e）は固定小数点数と呼ばれます。 固定小数点数は、仮数のみを保存することにより、通常の整数変数（レジスタ）に書き込むことができます。 通常、指数は文字qで示されます。 したがって、変数の解説で「 q15マルチプライヤー 」の精神で何かに出会った場合、この変数を固定小数点数と15に等しい指数と見なす必要があります。しかし、さまざまなソースコードや記事にある表記の問題に戻ります。

計算

そのため、固定小数点で作業する場合、指数はどこにも記録されず、「念頭に置いて」保持されることがわかりました。
計算方法 計算算術は、独自の公式、公理、定理を持つ科学全体です。 この記事の目的は、この科学を紹介することではありません。 以下に示すアプローチは、主にエンジニアリングと応用の問題を解決するプログラマーを対象としています。 そのような場合、許容値の範囲と計算の必要な精度は既知であり、制限されています。
この記事のもう1つの制限は、三角法やその他の複雑な操作のアルゴリズムがここに記載されていないことです。 1つの記事で完全なレビューを行うことは非現実的です（ほとんど必要ありません）。 この記事では、このようなアルゴリズムを理解する（および独自のアルゴリズムを開発する）ために必要な基礎を提供します-基本的な操作（加算/減算、乗算、除算）を実行するためのルールと固定小数点で計算する一般的な方法です。

加算と減算

紙の上に「列に」2つの小数を入れなければならないと思い込んでいるなら、加算は簡単です。 この操作を実行すると、小数部分を区切るコンマが上下に配置されるように、数値が列に書き込まれます。 二項算術では、そのような演算は指数の簡約と呼ばれます。
「ペーパー」から数学表記に進むと、次のようになります。
2つの数値a = n1 * 2 ^-q1とb = n2 * 2 ^{-q2があるとし}ます。
次に：
a + b = n1 * 2 ^-q1 + n2 * 2 ^-q2 =（n1 + n2 * 2 ^（q1-q2） ）* 2 ^-q1 。
第2項の係数2 ^（q1-q2）は、本質的に数値を1つの指数に減らす算術シフトを意味します。
計算結果も希望の指数値になるようにシフトできることに注意してください。
Cコードスニペット：

int32_t a = 0x1000L; // q15: a = 0.125 int32_t b = 0x20000L; // q20: b = 0.125 int32_t c = 0; // q25 c = (a << 5) + b; // q20: (a * 2 ^ (20 - 15) + b); c = 0x40000L (0.25  q20) c <<= 5; // q25: c = 0x800000L (0.25  q25) 

この例から、実際のコンピューティングでは、加算などの単純な操作であっても、思考の余地があることが理解できます。 質問を覚えておく価値は常にあります。

• 精度を犠牲にするかどうか？ 結局、右にシフトすることで用語をより小さな指数にし、下の桁を落とすことができます。
• 変数値は制限されていますか？ たとえば、この場合の右へのシフトは、精度の低下にはつながりません。
• 容量を拡張することは可能ですか？

これは完全なリストではありませんが、すべてが一見すると思えるほど単純ではないことをすでに示しています。 ほとんどの実用的なアプリケーションでは、各サブジェクト領域について、許容値の範囲が既知であるか取得できるため、固定小数点で作業する場合は、ある程度の経験または研究が必要です。 多くの場合、コードは浮動小数点で事前に作成され、その後、値の範囲が検査され、小さな値は無視されます。

乗算

固定小数点乗算は、トリッキーなアライメントや単一の指数への削減なしに実行できます。 それにもかかわらず、乗算はかなり危険な操作であり、ほとんどの場合、精度が失われ、取り扱いには特別な注意が必要です。
乗算の数学的な説明から始めましょう。
2つの数値a = n1 * 2 ^-q1とb = n2 * 2 ^{-q2があるとし}ます。
次に：
a * b = n1 * 2 ^-q1 * n2 * 2 ^-q2 = n1 * n2 * 2- ^{（q2 + q1）} 。
式から、乗算されたときの数値の指数が加算されることが^わかります： 2- ^{（q2 + q1）} 。 この記事では、データのビット深度は考慮されていません。現時点では、オーバーフローと精度の低下を伴わない安全な乗算のために、結果のビット深度は因子の合計ビット深度以上でなければならないことを覚えておけば十分です。
指数の加算により、さらに計算を実行するために乗算結果を調整する必要があります。 指数が減少すると、結果の最下位ビットは破棄されます。 つまり、精度が失われます。 精度の損失を減らすことができます（必要な場合もあります）が、損失に対処する方法は常にオーバーヘッドに関連付けられます。
Cコードスニペット：

 int32_t a = 0x8000L; // q16: a = 0.5 int32_t b = 0x100000L; // q21: b = 0.5 int32_t c = 0xC0000L; // q20: c = 0.75 int64_t d; //      ,    . d = (int64_t)a * (int64_t)b; // q37 = q16 * q21; d = 0x800000000L (0.25 in q37) d >>= 17; // q37 / 2 ^ 17 = q20 c += (int32_t)d; // q20: c = 0x100000 (1 in q20) 

乗算結果の最下位15ビットは、数字を用語の形式にするために破棄されたことに注意してください。 もちろん、変数cのビット深度を増やすことはできましたが、すでに述べたように、実際には値の範囲は通常制限され、乗算の下位桁はしばしば無視されます。 さらに、初期因子にゼロ以外の高次ビットが存在する可能性は考慮されていません。
ただし、この記事ではオーバーフロー処理については説明しません。

部門

除算の数式から始めましょう：
2つの数値a = n1 * 2 ^-q1とb = n2 * 2 ^{-q2があるとし}ます。
次に：
a / b = n1 * 2 ^-q1 /（n2 * 2 ^-q2 ）= n1 / n2 * 2- ^（q1-q2） 。
係数2- ^（q1-q2）は、除算の実行時に指数が自動的に減少することを意味します。 アクションが実行されない場合、有効数字の一部は自動的に破棄されます。
修正方法は明らかです-除算の結果、有効なビットの希望数を得るために、除算器のビット深度を事前に増やす必要があります。
a / b = n1 * 2 ^-q1 * 2 ^q3 /（n2 * 2 ^-q2 ）= n1 / n2 * 2- ^{（q1-q2 + q3）} 。
したがって、プライベート指数はq3放電によって増加します。
Cコードスニペット：

 int32_t a = 0x4000L; // q15: a = 0.5 int32_t b = 0x80000L; // q20: b = 0.5 int32_t c = 0; // q25 int64_t d; //      . d = (int64_t)a << 30; // q45: d = 0x200000000000; (0.5 in q45) c = (int32_t)(d / (int64_t)b); // q25: c = 0x2000000; (1 in q25) 

明らかに、数値が32ビットを超えると、問題を簡単に解決できなくなります。 ただし、単純な工学計算では、通常32ビットの数値で十分です。
除算の精度の損失を大幅に減らす簡単な方法が1つあります-配当の予備的な正規化です。 正規化は、実際には仮数の左への最大シフトであり、有効ビットは破棄されません。 特別なアルゴリズム（またはハードウェアプロセッサの命令）がある配当の先行ゼロをカウントすることで、数値をどれだけシフトできるかを判断できます。
除算後、商を同じビット数だけ右にシフトして、指数を復元する必要があります。
上記のコードは次のようになります。

 int32_t a = 0x4000L; // q15: a = 0.5 int32_t b = 0x80000L; // q20: b = 0.5 int32_t c = 0; // q25 int norm_shift = norm(a); //   . norm_shift = 16 c = ((a << norm_shift) / b); // q(-5): c = 0x800 (1*2^norm in q(-5)) c <<= (30 - norm); // q25: c = 0x2000000; (1 in q25) 

ご覧のとおり、この場合の精度の低下は、配当のキャパシティが増加しない限り発生しませんでした。
ただし、これは常に発生するわけではなく、特定のビット深度（たとえば、32ビット）内にとどまる場合は、除算をアルゴリズム的に実装する必要があります。 レビュー記事では、このようなジャングルに飛び込む価値はほとんどありません。分割プロセスとそれに伴う困難を理解するには、上記の説明で十分です。

文献およびさまざまなソースコードで受け入れられている表記

記事の最後のセクションでは、固定小数点アルゴリズムの説明で使用されている一般に受け入れられている表記法にもう一度戻りたいと思います。
これは、他の人の情報源を読むときに注意しなければならないかなり重要なポイントです。
最も一般的なのは、固定小数点数を指定するための2つのオプションです。

1. Q M - Mは小数点以下の桁数です。 記事で使用
2. Q N.M - Nは小数点の前の桁数で、符号ビットを除き、 M-後です。

最初の表記法のマイナスは明らかです。変数を操作するときは、変数宣言を参照し（ビット深度を覚えて）、指数を希望の指数に合わせる方法を理解するために心の中でいくつかの計算を行う必要があります。 さらに、乗算の例で丸め（int32_t）dを思い出すと、この表記のコメントでは、重要なビットのシフトまたは破棄がエラーにつながるかどうかを理解することが困難であることに注意できます。
2番目の表記法でコメントを使用すると、計算の正確さを簡単に記録できるため、変数の宣言方法を思い出す必要がなくなります。
例を挙げましょう。

 a = 0x1000; // Q15 b = 0x8000; // Q15 int32_t c = a + b; // ???     ,      . a = 0x2000; // Q0.15 b = 0x8000; // Q16.15 c = a + b; // Q0.15 + Q16.15 = Q16.15: 16 + 15 = 31  + 1   

2番目の表記のコメントの方が明らかに便利です。
ここでは、コメントの有用性については説明しません（コメントはどこからでも）、私は間違いを犯さず、指数の減少と混同しないように、計算時に常に変数のタイプをペイントすると言います。
原則としてコメントがない場合、コードの読み取りと理解はもちろん複雑ですが、混乱した場合は、Q表記でそのような復号化をいつでも追加して、「このシフトを左に4シフトし、次に右に10シフト」することを理解できます。
最近公開されたVoIP GIPSエンジン（ webrtc ）のGoogleのソースでは、コメントの中で最も頻繁にQを書くことに注意してください。つまり、数字のすべてのビットが小数部に割り当てられます。 これは私を個人的に混乱させます、なぜなら コードがどのように機能するかを明確にするために、定義を調べなければなりません。
私自身は、上記とは異なり、固定小数点を操作するためのMATLABツールボックス表記に近い別の表記を使用します。 数学を変数の容量に結び付け、操作の結果（容量と指数）を評価する必要がある場合に、生活を簡素化します。
私のコメントでは、固定小数点数をQN.Mとしてマークします 。ここで、 Nは数値のビット容量、 Mは小数点以下の桁数です。
このようなスキームが自分にとって便利だと思った理由を説明しましょう。

1. 数値のビット深度がわかれば、結果のビット深度をいつでも予測できます。 それを表すのに十分な変数タイプを選択します。
2. 個人的には、 Q（-N）.Mという形式のレコードを読むのは不便であることがわかります。これは、右へのシフトと小数部の桁数不足を実行した後、2番目の表記に表示されます。 たとえば、指数が18（ n * 2 ^-18 ）である16ビット数のレコードは、私にとってはq16.18、2番目の表記についてはq（-3）.18に見えます。 すでに述べたように、最初の表記のレコードは、いずれの場合も計算の精度を理解するために定義に戻ることを強制しますが、この場合、定義なしでは明確ではありません。先頭の重要なビットはすでに破棄されているかどうかです。
3. 独自の表記法を使用して計算を行った後、どの変数でビット深度が結果に適合するか、指数をどのように調整するかを簡単に確認できます。 たとえば、 q32.15 * q16.4 = q48.19です。 結果を完全に表示するには、48ビットが必要であることがすぐにわかります。 2番目の表記では、エントリはq16.15 * q11.4 = q27.19のようになり、最初の係数から27 + 19 = 47 + 1符号+ 2番目の係数から1符号= 48ビットを計算する必要があります。 些細なことですが、素晴らしい。 特に多くのソースコードがある場合。

固定小数点を使用する長所と短所について

基本的な操作であっても、このような詳細な説明は、特に結果を追跡せずに浮動小数点の習慣が既に開発されている場合、計算で固定小数点を使用することからエンジニアとプログラマーを怖がらせることができます。 それでも、固定小数点の使用には利点があり、そのいくつかは明らかではありません。
必要かどうかを最終的に判断するには、次の固定小数点計算の要約を使用できます。
長所：

• 考える必要性。
• 結果の予測可能性。 コーディングへの正しいアプローチにより、計算の結果は、その時点まで正確なプラットフォーム（プロセッサー+コンパイラー）で同じになります。 この現象には、「bitexactivity」という特別な用語があります（英語のbit- exactnessから）。 正しくエンコードされたアルゴリズムは常にビットロックされているため、ターゲット以外のプラットフォームで調査できます。 これは、ターゲットプラットフォームでのデバッグが困難または不可能であり、入力データのみを取得できる場合に特に役立ちます。
• コードの動作を完全に制御します。 固定小数点は、使用されるプラットフォームでの浮動小数点の実装の機能に関連する「驚き」の出現を排除します。
• 無視できる値の自動「フィルタリング」。 浮動小数点では、計算エラーが累積する可能性があり、固定ポイントではこれは起こりません（小さな値を破棄するため）、またはエラーを累積するプロセスはアルゴリズムで制御できます。
• 変数値のアルゴリズム制御範囲。 浮動小数点を使用すると計算の自由度が高まりますが、結果は許容限度を超える可能性があり、個別に制御する必要が生じます。 固定点では、この問題はアルゴリズムの開発およびデバッグの段階で自動的に解決されます。
• 移植性アルゴリズム。 これに加えて、最初のものとかなりよく相関していますが、多くの非x86プロセッサでは、浮動小数点計算よりも整数計算の方がはるかによくサポートされていることに注意してください。 そのため、固定点で一度アルゴリズムを開発すると、さまざまな「弱い」プラットフォームへの移植がはるかに簡単になります。 通常、ターゲットプラットフォームで利用できるのは整数計算だけである場合があります。
• アルゴリズムの開発の精度を下げることにより、計算の複雑さを制御する機能。
• これは時々面白いです。

短所：

• 考える必要性。
• 浮動小数点と比較した変数値の範囲の縮小（最も単純な場合）。
• 変数の値の範囲をアルゴリズムで制御する必要性。 開発時間の大部分は、正しいスケーリングと範囲の選択に費やされています。
• 計算の各段階で容量を監視する必要性。
• 基本関数（三角関数、対数など）の独自のフレームワークを記述するか、既存のフレームワークを変更する必要があります。
• アルゴリズムを開発する際にアプリケーション領域に飛び込む必要性。
• コードの記述と保守の文化を改善する必要性-固定点で独自の開発を使用せずにはできません。 浮動小数点では、ほとんどの場合、ためらうことなく、既製の関数を使用して数学を「真正面から」書き換えることができます。

結論として

結果のオーバーフローや丸め中のゼロドリフトなどの固定小数点を使用した計算の問題や、それらの処理方法には触れませんでした。 テキストは、詳細を補うために、すでに膨大で、おそらく退屈であることが判明しています。
次に、特殊な文献の読み取りと独自のソースの作成（および、おそらく記事の第2部の理解）を容易にするために、固定小数点演算を記録する際に一般に受け入れられている表記法に非常に多くの注意を払いました。 はい、Q表記法で計算されたコメントは、ソースの深刻なデバッグと分析から私を救った。
トピックが必要な場合は、次のパートで記事を補足します。次のパートでは、上記の点を説明し、一般的な場合、アルゴリズムを浮動小数点から固定小数点に移行する方法を説明します。
NB数学者、心配しないでください、私はあなたが対処されている問題をよく知っていると思います。

参照資料

• ARMの固定小数点演算
• 固定小数点と浮動小数点DSPの比較（SPRY061）
• 固定小数点演算：はじめに-Digital Signal Labs
• グーグル

更新：

• 結局、私が使用した表記法は、MATLABからわかりました。 私は自分の時間のどこでそれを掘ったかをまだ覚えていませんでした。 nerudoに感謝します。 オブジェクトを作成するために、指定されたパッケージの固定小数点ツールボックスは、「ビット数」+「分数あたりのビット数」ペアのみを使用し、明示的な表示：符号付きまたは符号なしの数を使用します。
• 例が8ビット、16ビット、32ビット、および64ビットの単語にあふれているという事実にもかかわらず、私は説明をx86およびその他の汎用プロセッサのみに添付しようとしませんでした。 シンプルで、第一に、Cで例を挙げるのが簡単で、第二に、FPGA、ASICなどの専門家（VERILOGなどを読む）からは程遠いため、任意のビット深度を選択して明確に伝えることができます。 。 おそらく、この問題に精通している人は、例でトピックを記事に追加することができます。
• 表記法の説明では、符号なしの数値をどうするかについては言及していません。 一般に、私がそれらを見た主な情報源は、兆候についても何も言っていません。 基本的に、すべての数値が重要であることが暗示されました。 著者が署名された数字の記録を見た方法をすぐに言うことはできません。 / matlab表記では、符号のない番号をマークするためにQの後に文字「u」を追加したことに注意してください。