Goldschmidt部門の良い最初の推定値を選ぶ

https://stackoverflow.com/questions/2661541

27-09-2019
|

質問

Q22.10で固定ポイントの往復を計算していますゴールドシュミット部門 ARMのソフトウェアラスタライザーで使用するため。

これは、分子を1に設定するだけで行われます。つまり、分子は最初の反復時にスカラーになります。正直に言うと、私はここで盲目的にウィキペディアのアルゴリズムをフォローしています。この記事では、分母が半分の範囲（0.5、1.0）でスケーリングされている場合、良い最初の推定値は分母のみに基づいている可能性があると述べています。 D.

しかし、これを行うとき、私は多くの精度を失います。 512.00002Fの相互のものを見つけたい場合は言います。数を減らすために、私は分数部分で10ビットの精度を失い、これはシフトします。だから、私の質問は次のとおりです。

正規化を必要としないより良い見積もりを選択する方法はありますか？なんで？なぜだめですか？これがなぜであるか、または不可能な理由の数学的な証拠は素晴らしいでしょう。
また、シリーズがより速く収束するように、最初の推定値を事前に計算することは可能ですか？現在、それは平均して4回目の反復の後に収束しています。 ARMでは、これは約50サイクルの最悪の場合であり、CLZ/BSRのエミュレーションを考慮していないし、メモリの検索も受けていません。それが可能であれば、そうすることでエラーが増加するかどうか、そしていくらで増加するかどうかを知りたいです。

これが私のテストケースです。注：のソフトウェア実装 clz 13行目は私の投稿からですここ. 。必要に応じて、本質的なものに置き換えることができます。 clz 主要なゼロの数、および値0の場合は32を返す必要があります。

#include <stdio.h>
#include <stdint.h>

const unsigned int BASE = 22ULL;

static unsigned int divfp(unsigned int val, int* iter)
{
  /* Numerator, denominator, estimate scalar and previous denominator */
  unsigned long long N,D,F, DPREV;
  int bitpos;

  *iter = 1;
  D = val;
  /* Get the shift amount + is right-shift, - is left-shift. */
  bitpos = 31 - clz(val) - BASE;
  /* Normalize into the half-range (0.5, 1.0] */
  if(0 < bitpos)
    D >>= bitpos;
  else
    D <<= (-bitpos);

  /* (FNi / FDi) == (FN(i+1) / FD(i+1)) */
  /* F = 2 - D */
  F = (2ULL<<BASE) - D;
  /* N = F for the first iteration, because the numerator is simply 1.
     So don't waste a 64-bit UMULL on a multiply with 1 */
  N = F;
  D = ((unsigned long long)D*F)>>BASE;

  while(1){
    DPREV = D;
    F = (2<<(BASE)) - D;
    D = ((unsigned long long)D*F)>>BASE;
    /* Bail when we get the same value for two denominators in a row.
      This means that the error is too small to make any further progress. */
    if(D == DPREV)
      break;
    N = ((unsigned long long)N*F)>>BASE;
    *iter = *iter + 1;
  }
  if(0 < bitpos)
    N >>= bitpos;
  else
    N <<= (-bitpos);
  return N;
}


int main(int argc, char* argv[])
{
  double fv, fa;
  int iter;
  unsigned int D, result;

  sscanf(argv[1], "%lf", &fv);

  D = fv*(double)(1<<BASE);
  result = divfp(D, &iter); 

  fa = (double)result / (double)(1UL << BASE);
  printf("Value: %8.8lf 1/value: %8.8lf FP value: 0x%.8X\n", fv, fa, result);
  printf("iteration: %d\n",iter);

  return 0;
}

解決

私はあなたの問題に1時間を費やすことに抵抗できませんでした...

このアルゴリズムは、Jean-Michel Muller（フランス語）による「Arithmetique des Ordinateurs」のセクション5.5.2で説明されています。実際、それは1つのニュートン反復の特別なケースであり、1は出発点です。この本は、n/dを計算するためのアルゴリズムの単純な定式化を提供し、dを範囲で正規化します[1/2,1 [：

e = 1 - D
Q = N
repeat K times:
  Q = Q * (1+e)
  e = e*e

正しいビットの数は、各反復で2倍になります。 32ビットの場合、4回の反復で十分です。まで繰り返すこともできます e 変更するには小さすぎます Q.

結果に最大数の重要なビットを提供するため、正規化が使用されます。また、入力が既知の範囲にあるときに必要な反復のエラーと数の数を計算する方が簡単です。

入力値が正規化されたら、逆になるまでベースの値を気にする必要はありません。範囲0x80000000から0xfffffffffで正規化された32ビット番号xを使用し、y = 2^64/xの近似値を計算します（yは最大2^33）。

この単純化されたアルゴリズムは、次のようにQ22.10表現に実装できます。

// Fixed point inversion
// EB Apr 2010

#include <math.h>
#include <stdio.h>

// Number X is represented by integer I: X = I/2^BASE.
// We have (32-BASE) bits in integral part, and BASE bits in fractional part
#define BASE 22
typedef unsigned int uint32;
typedef unsigned long long int uint64;

// Convert FP to/from double (debug)
double toDouble(uint32 fp) { return fp/(double)(1<<BASE); }
uint32 toFP(double x) { return (int)floor(0.5+x*(1<<BASE)); }

// Return inverse of FP
uint32 inverse(uint32 fp)
{
  if (fp == 0) return (uint32)-1; // invalid

  // Shift FP to have the most significant bit set
  int shl = 0; // normalization shift
  uint32 nfp = fp; // normalized FP
  while ( (nfp & 0x80000000) == 0 ) { nfp <<= 1; shl++; } // use "clz" instead

  uint64 q = 0x100000000ULL; // 2^32
  uint64 e = 0x100000000ULL - (uint64)nfp; // 2^32-NFP
  int i;
  for (i=0;i<4;i++) // iterate
    {
      // Both multiplications are actually
      // 32x32 bits truncated to the 32 high bits
      q += (q*e)>>(uint64)32;
      e = (e*e)>>(uint64)32;
      printf("Q=0x%llx E=0x%llx\n",q,e);
    }
  // Here, (Q/2^32) is the inverse of (NFP/2^32).
  // We have 2^31<=NFP<2^32 and 2^32<Q<=2^33
  return (uint32)(q>>(64-2*BASE-shl));
}

int main()
{
  double x = 1.234567;
  uint32 xx = toFP(x);
  uint32 yy = inverse(xx);
  double y = toDouble(yy);

  printf("X=%f Y=%f X*Y=%f\n",x,y,x*y);
  printf("XX=0x%08x YY=0x%08x XX*YY=0x%016llx\n",xx,yy,(uint64)xx*(uint64)yy);
}

コードに記載されているように、乗算は32x32-> 64ビットではありません。 Eは小さくなり、より小さくなり、最初は32ビットで適合します。 Qは常に34ビットになります。私たちは、製品の32ビットのみを服用しています。

の派生 64-2*BASE-shl 読者のための演習として残されています:-)。 0または負になった場合、結果は表現できません（入力値は小さすぎます）。

編集。私のコメントのフォローアップとして、Qに暗黙的な32番目のビットを持つ2番目のバージョンがあります。EとQの両方が32ビットに保存されます。

uint32 inverse2(uint32 fp)
{
  if (fp == 0) return (uint32)-1; // invalid

  // Shift FP to have the most significant bit set
  int shl = 0; // normalization shift for FP
  uint32 nfp = fp; // normalized FP
  while ( (nfp & 0x80000000) == 0 ) { nfp <<= 1; shl++; } // use "clz" instead
  int shr = 64-2*BASE-shl; // normalization shift for Q
  if (shr <= 0) return (uint32)-1; // overflow

  uint64 e = 1 + (0xFFFFFFFF ^ nfp); // 2^32-NFP, max value is 2^31
  uint64 q = e; // 2^32 implicit bit, and implicit first iteration
  int i;
  for (i=0;i<3;i++) // iterate
    {
      e = (e*e)>>(uint64)32;
      q += e + ((q*e)>>(uint64)32);
    }
  return (uint32)(q>>shr) + (1<<(32-shr)); // insert implicit bit
}

他のヒント

あなたのためのいくつかのアイデアがありますが、述べられているようにあなたの問題を直接解決するものはありません。

なぜこのアルゴは部門のために？私が腕で見たほとんどの分裂


      adcs hi, den, hi, lsl #1
      subcc hi, hi, den
      adcs lo, lo, lo

CLZのバイナリ検索でNビット時間を繰り返して、どこから始めるかを決定します。それはかなり速いです。

精度が大きな問題である場合、固定点表現の32/64ビットに限定されません。少し遅くなりますが、レジスタ全体に値を移動するためにADD/ADCまたはSUB/SBCを実行できます。 MUL/MLAは、この種の作業用にも設計されています。

繰り返しますが、あなたのために直接的な答えではなく、おそらくこれを進めるためのいくつかのアイデアがあります。実際のアームコードを見ると、おそらく私も少し役立つでしょう。

マッド、あなたはまったく精度を失っていません。 512.00002Fを2^10で除算すると、フローティングポイント数の指数を10で減らすだけです。マンティッサは同じままです。もちろん、指数が最小値に達していない限り、それはあなたがスケーリングしているので起こらないはずです（0.5、1）。

編集：OKでは、固定小数点を使用しています。その場合、アルゴリズムの分母の異なる表現を許可する必要があります。 dの値は（0.5、1]の最初だけでなく、計算全体を通して（x <1でx *（2-x）<1を証明するのは簡単です）。したがって、小数を伴う分母を表現する必要があります。ベース= 32でポイントします。このようにして、常に32ビットの精度があります。

編集：これを実装するには、次のコード行を変更する必要があります。

  //bitpos = 31 - clz(val) - BASE;
  bitpos = 31 - clz(val) - 31;
...
  //F = (2ULL<<BASE) - D;
  //N = F;
  //D = ((unsigned long long)D*F)>>BASE;
  F = -D;
  N = F >> (31 - BASE);
  D = ((unsigned long long)D*F)>>31;
...
    //F = (2<<(BASE)) - D;
    //D = ((unsigned long long)D*F)>>BASE;
    F = -D;
    D = ((unsigned long long)D*F)>>31;
...
    //N = ((unsigned long long)N*F)>>BASE;
    N = ((unsigned long long)N*F)>>31;

また、最終的には、nをbitposではなく、私が今理解するにはあまりにも怠zyであるといういくつかの異なる値でシフトする必要があります:)。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow