56

我想知道这里是否有人知道 c# 中定点数学的任何好的资源？我见过这样的事情（http://2ddev.72dpiarmy.com/viewtopic.php?id=156）和这个（What's the best way to do fixed-point math?），以及一些关于是否十进制的讨论确实是定点或实际上是浮点（更新：响应者已确认它绝对是浮点），但我还没有看到用于计算余弦和正弦之类的可靠 C# 库。

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

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

如果有 Java 或 VB 或其他类似语言的开源代码，我可能会转换代码以供我使用。对我来说，首要任务是准确性，尽管我希望在目前的性能上尽可能少地损失速度。这整个定点数学的东西对我来说是非常新的，我很惊讶谷歌上关于它的实用信息如此之少——大多数东西似乎要么是理论，要么是密集的 C++ 头文件。

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

更新：我绝对可以为我的目的制作一个余弦/正弦查找表，但我认为这不适用于 arctan2，因为我需要生成一个包含大约 64,000x64,000 个条目的表（哎呀）。如果您知道任何关于计算诸如 arctan2 之类的有效方法的编程解释，那就太棒了。我的数学背景还可以，但是高级公式和传统的数学符号对我来说很难翻译成代码。

4

6 回答 6

63

好的，这是我根据原始问题中的链接提出的定点结构，但还包括对如何处理除法和乘法的一些修复，并为模块、比较、移位等添加了逻辑：

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

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

这些函数在此处编码的准确性对于我的目的来说绰绰有余，但如果您需要更多，您可以增加 FInt 上的 SHIFT AMOUNT。请注意，如果这样做，那么 Hommes 博士函数的常数将需要除以 4096，然后乘以新的 SHIFT AMOUNT 所需的任何值。如果您这样做并且不小心，您可能会遇到一些错误，因此请务必对内置的数学函数进行检查，以确保您的结果不会因错误地调整常数而被推迟。

到目前为止，这个 FINt 逻辑似乎与等效的内置 .net 函数一样快，如果不是快一点的话。这显然会因机器而异，因为 fp 协处理器会确定这一点，所以我没有运行特定的基准测试。但它们现在已集成到我的游戏中，与以前相比，我发现处理器利用率略有下降（这是在 Q6600 四核上 - 平均使用率下降约 1%）。

再次感谢所有为您的帮助发表评论的人。没有人直接指出我要找的东西，但你给了我一些线索，帮助我自己在谷歌上找到了它。我希望这段代码对其他人有用，因为在公开发布的 C# 中似乎没有任何可比的东西。

于 2009-03-05T18:36:03.340 回答
6

在例如 1/1000 比例中使用 64 位整数。您可以正常加减。当你需要乘然后乘整数然后除以1000。当你需要sqrt，sin，cos等然后转换为long double，除以1000，sqrt，乘以1000，转换为整数。机器之间的差异应该无关紧要。

您可以使用另一个比例来更快地划分，例如 1024 as x/1024 == x >> 10。

于 2009-03-03T09:00:26.483 回答
6

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

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

于 2013-10-14T21:53:07.280 回答
4

我知道这个线程有点旧，但为了记录，这里有一个在 C# 中实现定点数学的项目的链接：http ://www.isquaredsoftware.com/XrossOneGDIPlus.php

于 2011-07-06T16:49:55.833 回答
3

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

于 2009-03-03T10:31:01.413 回答
3

我创建了一个类似的定点结构。使用 new() 会降低性能，因为即使您使用的是结构，它也会将数据放入堆中。请参阅 Google（.NET 中的 C# Heap(ing) Vs Stack(ing)：第 I 部分）使用 struct 的真正力量是能够不使用 new 并将值传递给堆栈。我下面的示例在堆栈上执行以下操作。1. [result int ] 在堆栈 2. [a int ] 在堆栈 3. [b int ] 在堆栈 4. [* ] 运算符在堆栈 5. value 结果返回没有堆分配的成本。

    public static Num operator *(Num a, Num b)
    {
        Num result;
        result.NumValue = a.NumValue * b.NumValue;
        return result;
    }
于 2010-03-27T14:28:12.017 回答