エラーマージンとオーバーフローの問題

私の同僚が最近私に植え付けた小さなアルゴリズムのタスクをあなたと共有したいと思います。 解決策は非常にエレガントであることが判明したようです。



問題の本質は次のとおりです。 32ビット整数値のみを処理でき、浮動小数点の操作方法がわからない特定のデバイス（マイクロコントローラー）があります。

そのようなデバイスには、毎秒32768ティックを生成するタイマーがあります。 精度を損なうことなく（できれば丸めを使用して）ティックをミリ秒に変換する関数を作成する必要があります。



注：この記事の例はすべてJavaで作成されていますが、これはアルゴリズムの理解を妨げるものではありません。



明らかに、「正面」ソリューションm = (ticks * 1000) / (2^15)



適切でm = (ticks * 1000) / (2^15)



ません。簡単にオーバーフローにつながる可能性があるためです。

ユーリカ？

従業員が話した最初のオプションは、愚かに32で割られますが、ここでは大きなエラーが発生します。

別の解決策は、各ステップで32ビットをオーバーフローさせないように、複数の段階で一連のチェックを行う乗算による「スマート」除算であると想定されていました。



すぐに、次の一連の変換が思い浮かびました（ 1000 = 1024 - 24



ことを思い出してください）：

ticks * 1000 * 2^(-15) =

ticks * 2^(-5) - ticks * 24 * 2^(-15) = ticks * 2^(-5) - 3 * ticks * 2^(-12)







合計：

  private int getMillis(int ticks) { return (ticks >> 5) - 3*(ticks >> 12); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

いいね！ これがうまくいかないのは残念です。

最初のアプローチ

私は、もう一度確認したと思った-引数に明らかなエラーはありません。 私はいくつかのテスト例をチェックしました-そのようなアルゴリズムは考慮しますが、常に正しくはありません。 場合によっては、正しい結果から+ -3の偏差があります。 どうやら、数学に問題はないようです（そうでなければ、答えは真実に似ていなかったでしょう）が、エラーがあります。



問題が何であるかを理解するには、ビットシフトがどのように機能するかを覚えておく価値があります。 nだけ右にビットシフトする操作は、2のn乗で完全に除算することに対応します。 これは整数演算であるため、ゼロビットの「右側」にあるビットは単純に破棄されます。



提案されたアルゴリズムをよく見ると、2つのシフト操作、結果の1つの乗算と差があります。 概略的に、この操作を以下に示します。



明らかに、エラーはゼロビットの右側のビットに正確に蓄積する可能性があります。



当初、最後の破棄された（マイナスが最初の）ビットの疑いがありましたが、乗算と差の演算に欠けていたのかもしれません。 その結果、機能コードはやや複雑になりました。

  private int getMillis(int ticks) { int err = ((ticks & 16) >> 4) - 3 * ((ticks & 2048) >> 11); if (err < 0) { return (ticks >> 5) - 3 * (ticks >> 12) - (Math.abs(err) >> 1); } else { return (ticks >> 5) - 3 * (ticks >> 12) + (err >> 1); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

err変数には、シフト操作中に破棄されたビットを配置し、 x - 3 * y



という形式の同じ操作が個別に実行されます。 このために、4番目と11番目のビットが割り当てられ、ゼロ位置にシフトされ、演算が計算され、結果が再び1ビットだけ右にシフトされます。

結果として、シフト後に残っているのは失われたビットだけであり、これを使用して結果を調整します。

結果は改善されました：絶対誤差は2以下になりました。

解決策

これで、思考の方向が正しいことが明らかになりましたが、小数点の右側の1ビットだけでなく、交差する5つすべて（つまり、上の図の-1から-5の位置に表示されます）が参加する必要があります。



その結果、関数の最終バージョンを取得しましたが、そのエラーは0.5未満でした。

一般的な考え方は前の例と同じでしたが、各オペランドから1ビットではなく、それぞれ5個がエラーソースとして割り当てられました。



さらに、 i番目のビットがi + 1番目のビットの半分に等しいという考えに基づいた丸めが実装されます。



他のすべてはコードから明確でなければなりません:)

  private int getMillis(int ticks) { int l = (ticks & 0x1F) << 7; int r = ticks & 0xFFF; // 2^12 - 1 int err = l - 3 * r; int fraction = (Math.abs(err) & 0xFFF); int fractionRound = fraction >> 11; //== 1 <=> there is 0.5xxx fraction = fraction & 0x7FF; // 0.5xxx => 0.0xxx if (err < 0) { fraction = fraction > 0 ? 1 : 0; return (ticks >> 5) - 3 * (ticks >> 12) - (Math.abs(err) >> 12) - (fractionRound & fraction); } else { return (ticks >> 5) - 3 * (ticks >> 12) + (err >> 12) + fractionRound; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

良いプログラマーになり、良い週末を過ごしましょう！