8

タイムスタンプ (秒の小数部のみ) をナノ秒 (10^-9 秒単位) から NTP タイムスタンプの下半分 (2^-32 秒単位) に再スケーリングしようとしています。事実上、これは 4.2949673 を掛けることを意味します。しかし、浮動小数点演算や 32 ビットを超える整数を使用せずにそれを行う必要があります (実際、これは実際には 8 ビット マイクロコントローラー用に書いているため、32 ビット演算でさえ、特に除算ではコストがかかります)。

かなりうまく機能するいくつかのアルゴリズムを思いつきましたが、数値的方法に実際の根拠がないため、それらを改善する方法、またはより正確で他のアルゴリズムに関する提案をいただければ幸いです。 /またはより高速。

アルゴリズム 1

uint32_t intts = (ns >> 16) * 281474 + (ns << 16) / 15259 + ns / 67078;

最初の 2 つの定数は、正しい数値をオーバーシュートするのではなく、わずかにアンダーシュートするように選択され、最終的な係数 67078 はこれを修正するために経験的に決定されました。正しい値の +/- 4 NTP 単位内の結果を生成します。これは +/- 1 ns です。許容範囲ですが、残差はns. 別の用語を追加できると思います。

アルゴリズム 2

uint32_t ns2 = (2 * ns) + 1;
uint32_t intts = (ns2 << 1)
  + (ns2 >> 3) + (ns2 >> 6) + (ns2 >> 8) + (ns2 >> 9) + (ns2 >> 10)
  + (ns2 >> 16) + (ns2 >> 18) + (ns2 >> 19) + (ns2 >> 20) + (ns2 >> 21)
  + (ns2 >> 22) + (ns2 >> 24) + (ns2 >> 30) + 3;

4.2949673 の 2 進展開に基づいています (実際には 2.14748365 の 2 進展開に基づいています。これは、丸めを行うために 2 倍にして 1 を追加することから始めているためです)。おそらくアルゴリズム 1 よりも高速です (まだベンチマークを取得していません)。+3 は、すべての下位ビットを切り捨てることによるアンダーシュートを相殺するために経験的に決定されましたが、可能な限り最善の仕事をするわけではありません。

4

2 に答える 2

8 
uint32_t convert(uint32_t x) {
    const uint32_t chi = 0x4b82;
    const uint32_t clo = 0xfa09;
    const uint32_t round = 0x9525;
    const uint32_t xhi = x >> 16;
    const uint32_t xlo = x & 0xffff;
    uint32_t lowTerm = xlo*clo;
    uint32_t crossTerms = xhi*clo + xlo*chi;
    uint32_t rounded = crossTerms + (lowTerm >> 16) + round >> 16;
    uint32_t highTerm = xhi*chi;
    return (x << 2) + highTerm + rounded;
}

基本的な固定小数点乗算。4つの16x16->32積を使用して32x32->64積をシミュレートします。定数roundは、単純な二分探索を使用してエラーを最小限に抑えるように選択されました。この式は、有効な範囲全体で+/-0.6NTPに適しています。

4スケールファクターの先頭はシフトで処理されます。コンパイラーは通常、この種のコードに対してかなり適切なコードを生成できますが、必要に応じて、手書きのアセンブリーを使用して合理化できることもよくあります。

それほど正確さを必要としない場合は、を取り除き、+/-1.15NTPに適した答えを得るlowTermことができます。round

uint32_t convert(uint32_t x) {
    const uint32_t chi = 0x4b82;
    const uint32_t clo = 0xfa09;
    const uint32_t xhi = x >> 16;
    const uint32_t xlo = x & 0xffff;
    uint32_t crossTerms = xhi*clo + xlo*chi;
    uint32_t highTerm = xhi*chi;
    return (x << 2) + highTerm + (crossTerms >> 16) + 1;
}
于 2011-03-04T00:37:42.510 に答える
1

当たり前のことを言っているかもしれませんが、固定小数点数学ライブラリについて interwebz をググったことはありますか? それらはたくさんあります。これは、Flipcode のアーカイブに C++ と x86 を実装した優れたものです。

http://www.flipcode.com/archives/Fixed_Point_Routines.shtml

于 2011-03-03T23:56:04.110 に答える