C# 中的定点数学

Question

C# 中有一些关于定点数学的好资源吗？

我见过这样的事情（http://2ddev.72dpiarmy.com/viewtopic.php ?id=156）和这个（进行定点数学的最佳方法是什么？），以及一些关于小数是真正的定点还是实际上的浮点的讨论（更新：响应者已经确认它绝对是浮点） ，但我还没有看到一个可靠的 C# 库来计算余弦和正弦之类的东西。

我的需求很简单——我需要基本运算符，加上余弦、正弦、arctan2、π，等等。我想就是这样。 也许开方。 我正在编写一个二维 RTS 游戏，我大部分时间都在工作，但是随着时间的推移（10-30 分钟）在多台机器上使用浮点数学（双精度）时的单位移动具有非常小的不准确性，从而导致不同步。 目前仅介于 32 位操作系统和 64 位操作系统之间。 所有 32 位机器似乎都保持同步，没有任何问题，这让我认为这是一个浮点问题。

我从一开始就意识到这是一个可能的问题，因此尽可能限制了我对非整数位置数学的使用，但为了以不同的速度平滑对角线移动，我正在以弧度计算点之间的角度，然后使用 sin 和 cos 获取运动的 x 和 y 分量。 这是主要问题。 我还在对线段相交、线圆相交、圆矩形相交等进行一些计算，这些计算也可能需要从浮点移动到定点以避免跨机器问题。

如果 Java 或 Visual Basic 或其他类似语言有开源的东西，我可能可以转换代码供我使用。 对我来说，最重要的是准确性，尽管我希望与当前性能相比速度损失尽可能小。 这整个定点数学的东西对我来说是非常新的，而且我很惊讶 Google 上关于它的实用信息如此之少——大多数东西似乎要么是理论，要么是密集的 C++ 头文件。

非常感谢您能做的任何事情来为我指明正确的方向； 如果我能做到这一点，我计划将我组装的数学函数开源，以便为其他 C# 程序员提供资源。

我绝对可以让余弦/正弦查找表满足我的目的，但我认为这不适用于 arctan2，因为我需要生成一个包含大约 64,000x64,000 个条目的表（哎呀）。 如果您知道任何关于计算 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 中我设法找到了 MathFP 库，作者：Onno Hommes。 这是一个自由源软件许可证，因此我将他的一些函数转换为我在 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

Hommes 博士的 MathFP 库中还有许多其他函数，但它们超出了我的需要，因此我没有花时间将它们转换为 C#（由于他我使用的是 long，而我使用的是 FInt 结构，这使得转换规则很难立即看到）。

此处编码的这些函数的准确性足以满足我的目的，但如果您需要更多，您可以增加 FInt 上的 SHIFT AMOUNT。 请注意，如果您这样做，Dr. Hommes 函数的常数将需要除以 4096，然后乘以新的 SHIFT AMOUNT 所需的值。 如果您这样做并且不小心，可能会遇到一些错误，因此请务必对内置数学函数进行检查，以确保您的结果不会因错误调整常量而推迟。

到目前为止，这个 FInt 逻辑看起来与等效的内置 .NET 函数一样快，甚至可能更快一些。 这显然会因机器而异，因为浮点协处理器会确定这一点，所以我没有运行特定的基准测试。 但它们现在已集成到我的游戏中，并且与以前相比，我发现处理器利用率略有下降（这是在 Q6600 四核——平均使用量下降约 1%）。

Answer 2

我已经在 C# 中实现了定点 Q31.32 类型。 它执行所有基本算术、sqrt、sin、cos、tan，并且很好地涵盖了单元测试。 你可以在这里找到它，有趣的类型是Fix64。

请注意，该库还包括 Fix32、Fix16 和 Fix8 类型，但这些主要用于实验，并不完整且没有错误。

Answer 3

使用 64 位整数，例如 1/1000 比例。 可以正常加减。 当您需要乘法时，然后乘以整数，然后除以1000。当您需要sqrt，sin，cos等，然后转换为long double，除以1000，sqrt，乘以1000，转换为整数。 那么机器之间的差异就不重要了。

您可以使用其他比例进行更快的除法，例如 1024 为 x/1024 == x >>> 10. .

Answer 4

XrossOne Mobile GDI+ 是一个在 C# 中实现定点数学的项目。

Answer 5

我创建了一个类似的定点结构。 使用 new() 会降低性能，因为即使您使用的是结构体，它也会将数据放入堆中。 请参阅 Google（.NET 中的 C# heap(ing) 与 stack(ing)：第 I 部分）。 使用结构体的真正威力是能够不使用 new 并按值传递到堆栈。 我下面的示例在堆栈上执行以下操作。

1. [结果 int ] 在堆栈上

2. [a int ] 在堆栈上

3. [b int ] 在堆栈上

4. [*] 运算符在堆栈上

5. 返回

   值结果。 没有堆分配成本。

    public static Num 运算符 *(Num a, Num b) 
      { 
          结果数； 
          结果.NumValue = a.NumValue * b.NumValue; 
          返回结果； 
      } 
     

Answer 6

除了缩放整数之外，还有一些任意精度的数值库，通常包含“BigRational”类型，而定点只是十分母的固定幂。