この除算近似アルゴリズムはどのように機能しますか？

Question

私は最も正確なPS1の外観を得るためにソフトウェアレンダラを使ってゲームを進めています。私はPS1のグラフィックス/レンダリングシステムがどのように働いたのか、揺れる頂点の理由などを研究していたので、彼らの分裂の仕方に関するいくつかのドキュメンテーションに出くわしました。ここではそれへのリンクです：http://problemkaputt.de/psx-spx.htm#gteoverview（「GTE部門不正確」の項を参照）

関連するコード：

if (H < SZ3*2) then       ;check if overflow 
    z = count_leading_zeroes(SZ3)    ;z=0..0Fh (for 16bit SZ3) 
    n = (H SHL z)        ;n=0..7FFF8000h 
    d = (SZ3 SHL z)        ;d=8000h..FFFFh 
    u = unr_table[(d-7FC0h) SHR 7] + 101h  ;u=200h..101h 
    d = ((2000080h - (d * u)) SHR 8)    ;d=10000h..0FF01h 
    d = ((0000080h + (d * u)) SHR 8)    ;d=20000h..10000h 
    n = min(1FFFFh, (((n*d) + 8000h) SHR 16)) ;n=0..1FFFFh 
    else n = 1FFFFh, FLAG.Bit17=1, FLAG.Bit31=1 ;n=1FFFFh plus overflow flag 

が、私はこの「UNR何であるか、これがどのように機能するかを理解することに苦労しています'テーブル？なぜ私たちは物事を変えていますか？ 誰かがこの事柄がどのように実際に分裂を達成しているかについてより詳細な説明を与えることができれば、それは認められるでしょう。

Answer 1

このアルゴリズムは、[0,1]内の2つの符号なし16ビット小数値の固定小数点除算です。最初にテーブルルックアップを介して除数の逆数に対する最初の9ビット近似を計算し、これを逆数のための単一のニュートンラフソン反復で除算すると、x _{i + 1}：= x _i *（2-d * x _i）、約16ビットの精度の逆数が得られ、最終的にこれを被除数で乗算し、[0,2]に17ビットの商を生成する。

倍率は、最初に倍率2を適用することによって[0.5,1]に正規化されます。明らかに配当は同じ倍率で調整する必要があります。 [0.5、1]のオペランドの逆数は[1,2]になるので、逆数の整数ビットは1であることが分かっているので、8ビットのテーブルエントリを使用して1.8の固定小数点を生成することができます0x100（= 1）を加算して逆数を計算します。ここでは0x101が使用されている理由は明確ではありません。このステップが常に真の逆数を過大評価するという要件が原因である可能性があります。

次の2つのステップは、固定小数点スケールファクタを考慮に入れて、ニュートンラフソンの反復の逐語的な変換です。したがって0x2000000は2.0を表します。コードでは、0x2000080が使用されます。これは、後続の除算に丸め定数0x80（= 128）を組み込み、結果をリスケールするために使用されるためです。次のステップでは同様に、256分のリスケーリング除算の丸め定数として0x00000080が加算されます。スケーリングがなければ、これは純粋な乗算になります。

最後の乗算n*dは、dの逆数にnの被除数を掛けて33ビットで商を得ます。再び、0x8000の丸め定数が65536で除算されて適切な範囲に再スケーリングされる前に適用され、1.16の固定小数点形式の商が与えられます。

連続リスケーリングは、最終結果の精度を最大にするために、中間結果をできるだけ大きく保つことを目的とする固定小数点計算の典型です。少し珍しいことは、最後のステップだけでなく、中間の算術のすべてで丸めが適用されるということです。たぶん、特定のレベルの精度を達成する必要があったかもしれません。

しかし、この関数はすべて正確ではありませんが、初期近似の不正確さに起因する可能性があります。例外的でないすべてのケースでは、2,424,807,756は正確に丸められた1.16の固定小数点結果に一致し、780,692,403は1 ulpの誤差を持ち、15,606,093は2 ulpの誤差を有し、86,452は3 ulpの誤差を有する。簡単な実験では、の相対の誤差は、初期近似uの誤差は3.89e-3であった。テーブル参照を改善すると、uの最大相対誤差が2に減少します。85e-3、最終結果で3μlの誤差を減少させるが、排除しない。

あなたは具体的な例を見てみたい場合は、h = 0.3（0x4ccd）SZ3 = 0.2（0x3333）で割った値を検討してください。次に、z = 2、したがってd = 0.2 * 4 = 0.8（0xcccc）。これにより、u = 1.25（0x140）になります。推定値はかなり正確であるため、（2-d * u）は1に近く、実際にはd = 1.000015（0x10001）になると予想しています。洗練された逆数は、d = 1.250015（0x14001）になるので、商はn = 1.500031（0x18002）です。