Clever Geek Handbook

乗算オーバーフロー

乗算を実行する前に、C ++はファクターをintより短くない同じタイプに変換し、結果のビット深度は指定されたファクターのビット深度と一致します。 精度を失わないために、乗算のために追加の演算を実行する必要がある場合があります。

問題を検討してください。 システムは、関数を呼び出して、プログラムがマイクロプロセッサーのティックで起動された瞬間からの時間を決定します。 

unsigned long long getTickCount();


符号なしlong longは64ビットです。 システムの物理的な時間単位に変換するには、定数があります： 

 const unsigned long long TICKS_PER_SECOND = 1999000001ULL;


セマンティクスを使用して、ティックをナノ秒getNsec（符号なしロングロングティック）に変換する機能を定義する必要があります。 

 unsigned long long getNsecNaive(unsigned long long ticks) { static const unsigned long long NSEC_PER_SECOND = 1000000000ULL; unsigned long long nsec = NSEC_PER_SECOND * ticks / TICKS_PER_SECOND; return nsec; }


getNsec（）関数はできるだけ正確でなければなりません。 ticksパラメーターは、大きくても小さくてもかまいません。 小さなティック（たとえば、2 ^ 34まで）の場合、次の順序で計算を実行する必要があります。 

 (NSEC_PER_SECOND * ticks) / TICKS_PER_SECOND


つまり、最初に乗算し、次に除算します。 NSEC_PER_SECOND <2 ^ 30なので、結果は2 ^ 64未満になるため、乗算はオーバーフローを引き起こしません。

大きなティックの場合、乗算によりオーバーフローが発生する可能性があるため、次の順序で操作を実行することをお勧めします。 

 NSEC_PER_SECOND * (ticks / TICKS_PER_SECOND)


この場合の問題は、2番目の要素が常に全体であり、10進法の結果が常に9つのゼロで終わることです。つまり、2番目の精度が保証され、getNsec（）関数の名前をgetSec（）に変更する必要があります。 一方、ソースデータを使用すると、精度が向上します。

乗算と除算の機械操作の非関連性を考えると、考えられる2つの計算に加えて、4つの可能な計算順序があります。 

 (NSEC_PER_SECOND / TICKS_PER_SECOND) * ticks


そして 

 ticks / (TICKS_PER_SECOND / NSEC_PER_SECOND)


最初は常にゼロ、2番目は-ティック、つまりほぼ50％のエラー（この場合は0.1％に減らすことができますが、このエラーは可能な限り小さくありません）。

したがって、最良の場合、2番目の精度が得られます。 精度の向上の問題は、次の方法で解決できます（優先度の高い順に）。

  1. 実（二重）型で計算を実行する
  2. 引数を128ビット整数にキャストします
  3. multdiv（）関数を使用する
これらのアプローチは、プラットフォーム（プロセッサ）の制限、プログラミング環境とライブラリ、およびプロジェクト要件の理由から適用できない場合があります。

次のアプローチを使用します。 ティックをTICKS_PER_SECONDで除算すると、不完全な秒の商と残りのrが得られるとします。 

 unsigned long long seconds = ticks / TICKS_PER_SECOND; unsigned long long r = ticks % TICKS_PER_SECOND;


その後、ティック=秒* TICKS_PER_SECOND + r。 nsecの式で置き換えます。

nsec = NSEC_PER_SECOND *（秒* TICKS_PER_SECOND + r）/ TICKS_PER_SECOND = NSEC_PER_SECOND *秒+（NSEC_PER_SECOND * r）/ TICKS_PER_SECOND。 r <TICKS_PER_SECONDであるため、（NSEC_PER_SECOND * r）は決してオーバーフローを与えません。 サマリー機能： 

 unsigned long long getNsec(unsigned long long ticks) { static const unsigned long long NSEC_PER_SECOND = 1000000000ULL; return NSEC_PER_SECOND * (ticks / TICKS_PER_SECOND) + ((NSEC_PER_SECOND)*(ticks % TICKS_PER_SECOND))/TICKS_PER_SECOND; }


結果は、NSEC_PER_SECOND * ticksを128ビット値としてカウントし、それをTICKS_PER_SECONDに分割した場合とまったく同じです。つまり、指定された初期値と結果のこのビット表現に対して最大の精度が保証されます。 returnステートメントの式は、決して簡素化されません。NSEC_PER_SECONDも/ TICKS_PER_SECONDも括弧で囲まれません。

実際、この問題の解決策は、a * b / cを計算するMultDiv（a、b、c）関数の実装に限定されます。ここで、bとcは大きな定数であり、小数部b / cは還元できません。


More articles:


All Articles