c#中的定点数学? [英] Fixed point math in c#?
问题描述
我想知道这里是否有人知道 C# 中定点数学的任何好的资源?我见过这样的事情(http://2ddev.72dpairmy.com/viewtopic.php?id=156)和这个(什么是进行定点数学的最佳方法?)，以及关于小数是真正定点还是实际浮点的一些讨论(更新:响应者已经确认它肯定是浮点)，但我还没有看到一个可靠的 C# 库，用于计算余弦和正弦.
I was wondering if anyone here knows of any good resources for fixed point math in c#? I've seen things like this (http://2ddev.72dpiarmy.com/viewtopic.php?id=156) and this (What's the best way to do fixed-point math?), and a number of discussions about whether decimal is really fixed point or actually floating point (update: responders have confirmed that it's definitely floating point), but I haven't seen a solid C# library for things like calculating cosine and sine.
我的需求很简单——我需要基本的运算符，加上余弦、正弦、arctan2、PI……我想就是这样.也许sqrt.我正在编写一个 2D RTS 游戏，我已经在很大程度上工作了，但是在多台机器上使用浮点数学(双打)时的单位移动随着时间的推移(10-30 分钟)有非常小的误差，导致不同步.这目前只在 32 位操作系统和 64 位操作系统之间，所有 32 位机器似乎都保持同步没有问题，这让我觉得这是一个浮点问题.
My needs are simple -- I need the basic operators, plus cosine, sine, arctan2, PI... I think that's about it. Maybe sqrt. I'm programming a 2D RTS game, which I have largely working, but the unit movement when using floating-point math (doubles) has very small inaccuracies over time (10-30 minutes) across multiple machines, leading to desyncs. This is presently only between a 32 bit OS and a 64 bit OS, all the 32 bit machines seem to stay in sync without issue, which is what makes me think this is a floating point issue.
我从一开始就意识到这是一个可能的问题，因此尽可能地限制了我对非整数位置数学的使用，但为了以不同的速度平滑对角线移动，我正在计算点之间的角度弧度，然后使用 sin 和 cos 获取运动的 x 和 y 分量.这是主要问题.我也在做一些线段交点、线-圆交点、圆-矩形交点等的计算，这些计算也可能需要从浮点到定点来避免跨机问题.
I was aware from this as a possible issue from the outset, and so have limited my use of non-integer position math as much as possible, but for smooth diagonal movement at varying speeds I'm calculating the angle between points in radians, then getting the x and y components of movement with sin and cos. That's the main issue. I'm also doing some calculations for line segment intersections, line-circle intersections, circle-rect intersections, etc, that also probably need to move from floating-point to fixed-point to avoid cross-machine issues.
如果在 Java 或 VB 或其他类似语言中有一些开源的东西，我可能会转换代码以供我使用.对我来说，主要优先事项是准确性，尽管我希望速度损失尽可能低于目前的性能.这整个定点数学的东西对我来说很新，我很惊讶谷歌上关于它的实用信息如此之少——大多数东西似乎要么是理论要么是密集的 C++ 头文件.
If there's something open source in Java or VB or another comparable language, I could probably convert the code for my uses. The main priority for me is accuracy, although I'd like as little speed loss over present performance as possible. This whole fixed point math thing is very new to me, and I'm surprised by how little practical information on it there is on google -- most stuff seems to be either theory or dense C++ header files.
非常感谢您为我指明正确方向所做的任何事情；如果我能做到这一点，我计划将我放在一起的数学函数开源，以便为其他 C# 程序员提供资源.
Anything you could do to point me in the right direction is much appreciated; if I can get this working, I plan to open-source the math functions I put together so that there will be a resource for other C# programmers out there.
更新:我绝对可以为我的目的制作一个余弦/正弦查找表，但我认为这不适用于 arctan2，因为我需要生成一个包含大约 64,000x64,000 个条目的表(是的).如果您知道计算诸如 arctan2 之类的有效方法的任何编程解释，那就太棒了.我的数学背景还可以，但是高级公式和传统数学符号对我来说很难翻译成代码.
UPDATE: I could definitely make a cosine/sine lookup table work for my purposes, but I don't think that would work for arctan2, since I'd need to generate a table with about 64,000x64,000 entries (yikes). If you know any programmatic explanations of efficient ways to calculate things like arctan2, that would be awesome. My math background is all right, but the advanced formulas and traditional math notation are very difficult for me to translate into code.
推荐答案
好的，这是我为定点结构提出的，基于我原来问题中的链接，但还包括一些修复方法正在处理除法和乘法，并为模块、比较、移位等添加逻辑:
Ok, here's what I've come up with for a fixed-point struct, based on the link in my original question but also including some fixes to how it was handling division and multiplication, and added logic for modules, comparisons, shifts, etc:
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 库.这是一个自由的源软件许可证，所以我已经将他的一些功能转换为我在 C# 中的用途(我认为修复了 atan2).享受:
Based on the comments from ShuggyCoUk, I see that this is in Q12 format. That's reasonably precise for my purposes. Of course, aside from the bugfixes, I already had this basic format before I asked my question. What I was looking for were ways to calculate Sqrt, Atan2, Sin, and Cos in C# using a structure like this. There aren't any other things that I know of in C# that will handle this, but in Java I managed to find the MathFP library by Onno Hommes. It's a liberal source software license, so I've converted some of his functions to my purposes in C# (with a fix to atan2, I think). Enjoy:
#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 结构，这使得转换规则很难立即看到).
There are a number of other functions in Dr. Hommes' MathFP library, but they were beyond what I needed, and so I have not taken the time to translate them to C# (that process was made extra difficult by the fact that he was using a long, and I am using the FInt struct, which makes the conversion rules are a bit challenging to see immediately).
这里编码的这些函数的准确性对于我的目的来说已经足够了，但是如果您需要更多，您可以增加 FInt 上的 SHIFT AMOUNT.请注意，如果这样做，则需要将 Hommes 博士函数的常数除以 4096，然后再乘以新的 SHIFT AMOUNT 所需的值.如果您这样做并且不小心，您可能会遇到一些错误，因此请务必针对内置数学函数运行检查，以确保您的结果不会因错误地调整常量而推迟.
The accuracy of these functions as they are coded here is more than enough for my purposes, but if you need more you can increase the SHIFT AMOUNT on FInt. Just be aware that if you do so, the constants on Dr. Hommes' functions will then need to be divided by 4096 and then multiplied by whatever your new SHIFT AMOUNT requires. You're likely to run into some bugs if you do that and aren't careful, so be sure to run checks against the built-in Math functions to make sure that your results aren't being put off by incorrectly adjusting a constant.
到目前为止，这种 FInt 逻辑似乎与等效的内置 .net 函数一样快，甚至可能快一点.这显然会因机器而异，因为 fp 协处理器会确定这一点，所以我没有运行特定的基准测试.但它们现在已集成到我的游戏中，我发现处理器利用率与以前相比略有下降(这是在 Q6600 四核上——平均使用率下降约 1%).
So far, this FInt logic seems as fast, if not perhaps a bit faster, than the equivalent built in .net functions. That would obviously vary by machine, since the fp coprocessor would determine that, so I have not run specific benchmarks. But they are integrated into my game now, and I've seen a slight decrease in processor utilization compared to before (this is on a Q6600 quad core -- about a 1% drop in usage on average).
再次感谢所有评论您的帮助.没有人直接指出我要找的东西，但你给了我一些帮助我自己在谷歌上找到的线索.我希望这段代码对其他人有用，因为在公开发布的 C# 中似乎没有任何可比的东西.
Thanks again to everyone who commented for your help. No one pointed me directly to what I was looking for, but you gave me some clues that helped me find it myself on google. I hope this code turns out to be useful for someone else, since there doesn't seem to be anything comparable in C# posted publicly.
这篇关于c#中的定点数学?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
