c# - C#の固定小数点演算?

Question

ここで誰かが c# の固定小数点演算に適したリソースを知っているかどうか疑問に思っていましたか? 私はこれ ( http://2ddev.72dpiarmy.com/viewtopic.php?id=156 ) やこれ (固定小数点演算を行う最良の方法は何ですか? )のようなものを見てきました。は実際には固定小数点または実際には浮動小数点です (更新: レスポンダーは、それが間違いなく浮動小数点であることを確認しています)。

私のニーズは単純です。基本的な演算子に加えて、cosine、sine、arctan2、PI が必要です...それだけだと思います。多分平方。私は主に作業している2D RTSゲームをプログラミングしていますが、浮動小数点演算（倍精度）を使用するときのユニットの動きは、複数のマシンで時間の経過とともに（10〜30分）非常にわずかな不正確さを持ち、非同期につながります。これは現在、32 ビット OS と 64 ビット OS の間だけで、すべての 32 ビット マシンは問題なく同期しているように見えます。

私はこれを最初から考えられる問題として認識していたので、非整数位置計算の使用を可能な限り制限しましたが、さまざまな速度でのスムーズな斜め移動のために、ポイント間の角度をラジアンで計算しています。 sin と cos を使用して、運動の x 成分と y 成分を取得します。それが主な問題です。また、マシン間の問題を回避するために浮動小数点から固定小数点に移動する必要がある、線分の交点、線と円の交点、円と四角形の交点などの計算も行っています。

Java や VB、または他の同等の言語で何かオープン ソースがある場合は、コードを自分の用途に合わせて変換できます。私にとっての最優先事項は精度ですが、現在のパフォーマンスよりも速度の低下をできるだけ少なくしたいと考えています。この固定小数点演算全体は私にとって非常に新しいものであり、グーグルでの実用的な情報がほとんどないことに驚いています-ほとんどのものは理論または高密度のC++ヘッダーファイルのようです.

私を正しい方向に向けるためにあなたができることは何でも大歓迎です。これを機能させることができれば、私がまとめた数学関数をオープンソース化して、他の C# プログラマー向けのリソースを提供する予定です。

更新: コサイン/サイン ルックアップ テーブルを自分の目的に合わせて機能させることは間違いありませんが、約 64,000x64,000 エントリのテーブルを生成する必要があるため、arctan2 では機能しないと思います (yikes)。arctan2 のようなものを計算する効率的な方法のプログラムによる説明を知っていれば、それは素晴らしいことです。私の数学のバックグラウンドは大丈夫ですが、高度な数式と従来の数学表記をコードに変換するのは非常に困難です。

Answer 1

わかりました、元の質問のリンクに基づいて固定小数点構造体について思いついたものですが、除算と乗算の処理方法に対するいくつかの修正、およびモジュール、比較、シフトなどのロジックの追加も含まれています:

public struct FInt
{
    public long RawValue;
    public const int SHIFT_AMOUNT = 12; //12 is 4096

    public const long One = 1 << SHIFT_AMOUNT;
    public const int OneI = 1 << SHIFT_AMOUNT;
    public static FInt OneF = FInt.Create( 1, true );

    #region Constructors
    public static FInt Create( long StartingRawValue, bool UseMultiple )
    {
        FInt fInt;
        fInt.RawValue = StartingRawValue;
        if ( UseMultiple )
            fInt.RawValue = fInt.RawValue << SHIFT_AMOUNT;
        return fInt;
    }
    public static FInt Create( double DoubleValue )
    {
        FInt fInt;
        DoubleValue *= (double)One;
        fInt.RawValue = (int)Math.Round( DoubleValue );
        return fInt;
    }
    #endregion

    public int IntValue
    {
        get { return (int)( this.RawValue >> SHIFT_AMOUNT ); }
    }

    public int ToInt()
    {
        return (int)( this.RawValue >> SHIFT_AMOUNT );
    }

    public double ToDouble()
    {
        return (double)this.RawValue / (double)One;
    }

    public FInt Inverse
    {
        get { return FInt.Create( -this.RawValue, false ); }
    }

    #region FromParts
    /// <summary>
    /// Create a fixed-int number from parts.  For example, to create 1.5 pass in 1 and 500.
    /// </summary>
    /// <param name="PreDecimal">The number above the decimal.  For 1.5, this would be 1.</param>
    /// <param name="PostDecimal">The number below the decimal, to three digits.  
    /// For 1.5, this would be 500. For 1.005, this would be 5.</param>
    /// <returns>A fixed-int representation of the number parts</returns>
    public static FInt FromParts( int PreDecimal, int PostDecimal )
    {
        FInt f = FInt.Create( PreDecimal, true );
        if ( PostDecimal != 0 )
            f.RawValue += ( FInt.Create( PostDecimal ) / 1000 ).RawValue;

        return f;
    }
    #endregion

    #region *
    public static FInt operator *( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue * other.RawValue ) >> SHIFT_AMOUNT;
        return fInt;
    }

    public static FInt operator *( FInt one, int multi )
    {
        return one * (FInt)multi;
    }

    public static FInt operator *( int multi, FInt one )
    {
        return one * (FInt)multi;
    }
    #endregion

    #region /
    public static FInt operator /( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue << SHIFT_AMOUNT ) / ( other.RawValue );
        return fInt;
    }

    public static FInt operator /( FInt one, int divisor )
    {
        return one / (FInt)divisor;
    }

    public static FInt operator /( int divisor, FInt one )
    {
        return (FInt)divisor / one;
    }
    #endregion

    #region %
    public static FInt operator %( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = ( one.RawValue ) % ( other.RawValue );
        return fInt;
    }

    public static FInt operator %( FInt one, int divisor )
    {
        return one % (FInt)divisor;
    }

    public static FInt operator %( int divisor, FInt one )
    {
        return (FInt)divisor % one;
    }
    #endregion

    #region +
    public static FInt operator +( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = one.RawValue + other.RawValue;
        return fInt;
    }

    public static FInt operator +( FInt one, int other )
    {
        return one + (FInt)other;
    }

    public static FInt operator +( int other, FInt one )
    {
        return one + (FInt)other;
    }
    #endregion

    #region -
    public static FInt operator -( FInt one, FInt other )
    {
        FInt fInt;
        fInt.RawValue = one.RawValue - other.RawValue;
        return fInt;
    }

    public static FInt operator -( FInt one, int other )
    {
        return one - (FInt)other;
    }

    public static FInt operator -( int other, FInt one )
    {
        return (FInt)other - one;
    }
    #endregion

    #region ==
    public static bool operator ==( FInt one, FInt other )
    {
        return one.RawValue == other.RawValue;
    }

    public static bool operator ==( FInt one, int other )
    {
        return one == (FInt)other;
    }

    public static bool operator ==( int other, FInt one )
    {
        return (FInt)other == one;
    }
    #endregion

    #region !=
    public static bool operator !=( FInt one, FInt other )
    {
        return one.RawValue != other.RawValue;
    }

    public static bool operator !=( FInt one, int other )
    {
        return one != (FInt)other;
    }

    public static bool operator !=( int other, FInt one )
    {
        return (FInt)other != one;
    }
    #endregion

    #region >=
    public static bool operator >=( FInt one, FInt other )
    {
        return one.RawValue >= other.RawValue;
    }

    public static bool operator >=( FInt one, int other )
    {
        return one >= (FInt)other;
    }

    public static bool operator >=( int other, FInt one )
    {
        return (FInt)other >= one;
    }
    #endregion

    #region <=
    public static bool operator <=( FInt one, FInt other )
    {
        return one.RawValue <= other.RawValue;
    }

    public static bool operator <=( FInt one, int other )
    {
        return one <= (FInt)other;
    }

    public static bool operator <=( int other, FInt one )
    {
        return (FInt)other <= one;
    }
    #endregion

    #region >
    public static bool operator >( FInt one, FInt other )
    {
        return one.RawValue > other.RawValue;
    }

    public static bool operator >( FInt one, int other )
    {
        return one > (FInt)other;
    }

    public static bool operator >( int other, FInt one )
    {
        return (FInt)other > one;
    }
    #endregion

    #region <
    public static bool operator <( FInt one, FInt other )
    {
        return one.RawValue < other.RawValue;
    }

    public static bool operator <( FInt one, int other )
    {
        return one < (FInt)other;
    }

    public static bool operator <( int other, FInt one )
    {
        return (FInt)other < one;
    }
    #endregion

    public static explicit operator int( FInt src )
    {
        return (int)( src.RawValue >> SHIFT_AMOUNT );
    }

    public static explicit operator FInt( int src )
    {
        return FInt.Create( src, true );
    }

    public static explicit operator FInt( long src )
    {
        return FInt.Create( src, true );
    }

    public static explicit operator FInt( ulong src )
    {
        return FInt.Create( (long)src, true );
    }

    public static FInt operator <<( FInt one, int Amount )
    {
        return FInt.Create( one.RawValue << Amount, false );
    }

    public static FInt operator >>( FInt one, int Amount )
    {
        return FInt.Create( one.RawValue >> Amount, false );
    }

    public override bool Equals( object obj )
    {
        if ( obj is FInt )
            return ( (FInt)obj ).RawValue == this.RawValue;
        else
            return false;
    }

    public override int GetHashCode()
    {
        return RawValue.GetHashCode();
    }

    public override string ToString()
    {
        return this.RawValue.ToString();
    }
}

public struct FPoint
{
    public FInt X;
    public FInt Y;

    public static FPoint Create( FInt X, FInt Y )
    {
        FPoint fp;
        fp.X = X;
        fp.Y = Y;
        return fp;
    }

    public static FPoint FromPoint( Point p )
    {
        FPoint f;
        f.X = (FInt)p.X;
        f.Y = (FInt)p.Y;
        return f;
    }

    public static Point ToPoint( FPoint f )
    {
        return new Point( f.X.IntValue, f.Y.IntValue );
    }

    #region Vector Operations
    public static FPoint VectorAdd( FPoint F1, FPoint F2 )
    {
        FPoint result;
        result.X = F1.X + F2.X;
        result.Y = F1.Y + F2.Y;
        return result;
    }

    public static FPoint VectorSubtract( FPoint F1, FPoint F2 )
    {
        FPoint result;
        result.X = F1.X - F2.X;
        result.Y = F1.Y - F2.Y;
        return result;
    }

    public static FPoint VectorDivide( FPoint F1, int Divisor )
    {
        FPoint result;
        result.X = F1.X / Divisor;
        result.Y = F1.Y / Divisor;
        return result;
    }
    #endregion
}

ShuggyCoUk からのコメントに基づいて、これは Q12 形式であることがわかります。それは私の目的にとってかなり正確です。もちろん、バグ修正は別として、私が質問する前に、この基本的なフォーマットは既に持っていました。私が探していたのは、このような構造を使用して C# で Sqrt、Atan2、Sin、および Cos を計算する方法でした。これを処理する C# で私が知っていることは他にありませんが、Java ではOnno Hommesによる MathFPライブラリを見つけることができました。これはリベラルなソース ソフトウェア ライセンスなので、彼の関数の一部を私の目的に合わせて C# に変換しました (atan2 を修正したと思います)。楽しみ：

    #region PI, DoublePI
    public static FInt PI = FInt.Create( 12868, false ); //PI x 2^12
    public static FInt TwoPIF = PI * 2; //radian equivalent of 260 degrees
    public static FInt PIOver180F = PI / (FInt)180; //PI / 180
    #endregion

    #region Sqrt
    public static FInt Sqrt( FInt f, int NumberOfIterations )
    {
        if ( f.RawValue < 0 ) //NaN in Math.Sqrt
            throw new ArithmeticException( "Input Error" );
        if ( f.RawValue == 0 )
            return (FInt)0;
        FInt k = f + FInt.OneF >> 1;
        for ( int i = 0; i < NumberOfIterations; i++ )
            k = ( k + ( f / k ) ) >> 1;

        if ( k.RawValue < 0 )
            throw new ArithmeticException( "Overflow" );
        else
            return k;
    }

    public static FInt Sqrt( FInt f )
    {
        byte numberOfIterations = 8;
        if ( f.RawValue > 0x64000 )
            numberOfIterations = 12;
        if ( f.RawValue > 0x3e8000 )
            numberOfIterations = 16;
        return Sqrt( f, numberOfIterations );
    }
    #endregion

    #region Sin
    public static FInt Sin( FInt i )
    {
        FInt j = (FInt)0;
        for ( ; i < 0; i += FInt.Create( 25736, false ) ) ;
        if ( i > FInt.Create( 25736, false ) )
            i %= FInt.Create( 25736, false );
        FInt k = ( i * FInt.Create( 10, false ) ) / FInt.Create( 714, false );
        if ( i != 0 && i != FInt.Create( 6434, false ) && i != FInt.Create( 12868, false ) && 
            i != FInt.Create( 19302, false ) && i != FInt.Create( 25736, false ) )
            j = ( i * FInt.Create( 100, false ) ) / FInt.Create( 714, false ) - k * FInt.Create( 10, false );
        if ( k <= FInt.Create( 90, false ) )
            return sin_lookup( k, j );
        if ( k <= FInt.Create( 180, false ) )
            return sin_lookup( FInt.Create( 180, false ) - k, j );
        if ( k <= FInt.Create( 270, false ) )
            return sin_lookup( k - FInt.Create( 180, false ), j ).Inverse;
        else
            return sin_lookup( FInt.Create( 360, false ) - k, j ).Inverse;
    }

    private static FInt sin_lookup( FInt i, FInt j )
    {
        if ( j > 0 && j < FInt.Create( 10, false ) && i < FInt.Create( 90, false ) )
            return FInt.Create( SIN_TABLE[i.RawValue], false ) + 
                ( ( FInt.Create( SIN_TABLE[i.RawValue + 1], false ) - FInt.Create( SIN_TABLE[i.RawValue], false ) ) / 
                FInt.Create( 10, false ) ) * j;
        else
            return FInt.Create( SIN_TABLE[i.RawValue], false );
    }

    private static int[] SIN_TABLE = {
        0, 71, 142, 214, 285, 357, 428, 499, 570, 641, 
        711, 781, 851, 921, 990, 1060, 1128, 1197, 1265, 1333, 
        1400, 1468, 1534, 1600, 1665, 1730, 1795, 1859, 1922, 1985, 
        2048, 2109, 2170, 2230, 2290, 2349, 2407, 2464, 2521, 2577, 
        2632, 2686, 2740, 2793, 2845, 2896, 2946, 2995, 3043, 3091, 
        3137, 3183, 3227, 3271, 3313, 3355, 3395, 3434, 3473, 3510, 
        3547, 3582, 3616, 3649, 3681, 3712, 3741, 3770, 3797, 3823, 
        3849, 3872, 3895, 3917, 3937, 3956, 3974, 3991, 4006, 4020, 
        4033, 4045, 4056, 4065, 4073, 4080, 4086, 4090, 4093, 4095, 
        4096
    };
    #endregion

    private static FInt mul( FInt F1, FInt F2 )
    {
        return F1 * F2;
    }

    #region Cos, Tan, Asin
    public static FInt Cos( FInt i )
    {
        return Sin( i + FInt.Create( 6435, false ) );
    }

    public static FInt Tan( FInt i )
    {
        return Sin( i ) / Cos( i );
    }

    public static FInt Asin( FInt F )
    {
        bool isNegative = F < 0;
        F = Abs( F );

        if ( F > FInt.OneF )
            throw new ArithmeticException( "Bad Asin Input:" + F.ToDouble() );

        FInt f1 = mul( mul( mul( mul( FInt.Create( 145103 >> FInt.SHIFT_AMOUNT, false ), F ) -
            FInt.Create( 599880 >> FInt.SHIFT_AMOUNT, false ), F ) +
            FInt.Create( 1420468 >> FInt.SHIFT_AMOUNT, false ), F ) -
            FInt.Create( 3592413 >> FInt.SHIFT_AMOUNT, false ), F ) +
            FInt.Create( 26353447 >> FInt.SHIFT_AMOUNT, false );
        FInt f2 = PI / FInt.Create( 2, true ) - ( Sqrt( FInt.OneF - F ) * f1 );

        return isNegative ? f2.Inverse : f2;
    }
    #endregion

    #region ATan, ATan2
    public static FInt Atan( FInt F )
    {
        return Asin( F / Sqrt( FInt.OneF + ( F * F ) ) );
    }

    public static FInt Atan2( FInt F1, FInt F2 )
    {
        if ( F2.RawValue == 0 && F1.RawValue == 0 )
            return (FInt)0;

        FInt result = (FInt)0;
        if ( F2 > 0 )
            result = Atan( F1 / F2 );
        else if ( F2 < 0 )
        {
            if ( F1 >= 0 )
                result = ( PI - Atan( Abs( F1 / F2 ) ) );
            else
                result = ( PI - Atan( Abs( F1 / F2 ) ) ).Inverse;
        }
        else
            result = ( F1 >= 0 ? PI : PI.Inverse ) / FInt.Create( 2, true );

        return result;
    }
    #endregion

    #region Abs
    public static FInt Abs( FInt F )
    {
        if ( F < 0 )
            return F.Inverse;
        else
            return F;
    }
    #endregion

Dr. Hommes の MathFP ライブラリには他にも多くの関数がありますが、それらは私が必要とする以上のものでした。ロングであり、私は FInt 構造体を使用しているため、変換ルールをすぐに確認するのは少し困難です)。

ここでコーディングされているこれらの関数の精度は、私の目的には十分ですが、さらに必要な場合は、FInt の SHIFT AMOUNT を増やすことができます。その場合、Dr. Hommes の関数の定数を 4096 で割り、新しい SHIFT AMOUNT に必要な値を掛ける必要があることに注意してください。注意を怠るとバグに遭遇する可能性が高いため、組み込みの数学関数に対してチェックを実行して、定数を誤って調整して結果が遅れないようにしてください。

これまでのところ、この FInt ロジックは、同等の組み込みの .net 関数よりも少し速くはないにしても、同じくらい高速に見えます。fp コプロセッサーがそれを決定するため、これはマシンによって明らかに異なるため、特定のベンチマークは実行していません。しかし、それらは現在私のゲームに統合されており、以前と比較してプロセッサの使用率がわずかに低下していることがわかりました (これは Q6600 クアッド コア上であり、平均して使用率が約 1% 低下しています)。

あなたの助けのためにコメントしてくれたすべての人に再び感謝します. 私が探しているものを直接教えてくれる人は誰もいませんでしたが、Google で自分で見つけるのに役立ついくつかの手がかりを教えてくれました。公に投稿された C# に匹敵するものはないように見えるので、このコードが他の誰かにとって有用であることが判明することを願っています。

Answer 2

C# で固定小数点 Q31.32 型を実装しました。すべての基本的な算術演算、sqrt、sin、cos、tan を実行し、単体テストで十分にカバーされています。ここで見つけることができます。興味深いタイプは Fix64 です。:

ライブラリには Fix32、Fix16、および Fix8 タイプも含まれていることに注意してください。ただし、これらは主に実験用であり、完全でバグのないものではありません。

Answer 3

このスレッドが少し古いことは知っていますが、記録として、C# で固定小数点演算を実装するプロジェクトへのリンクを次に示します: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 4

同様の固定小数点構造体を作成しました。構造体を使用している場合でもデータをヒープに配置するため、new（）を使用するとパフォーマンスが低下します。Google（.NETのC＃ヒープ（ing）とスタック（ing）：パートI）を参照してください。構造体を使用する真の力は、新しいものを使用せず、スタックに値を渡すことができることです。以下の私の例は、スタック上で次のことを行います。1.スタック上の[resultint]2.スタック上の[aint]3.スタック上の[bint]4.スタック上の[*]演算子5.値の結果はヒープに割り当てられたコストを返しませんでした。

    public static Num operator *(Num a, Num b)
    {
        Num result;
        result.NumValue = a.NumValue * b.NumValue;
        return result;
    }

Answer 5

スケーリングされた整数と同様に、通常「BigRational」タイプを含むいくつかの任意精度の数値ライブラリがあり、固定小数点は分母の 10 の固定累乗です。