Fixed point math in C #?

Question

I was wondering if anyone knows of good resources for fixed point math in C #? I have seen things like this ( http://2ddev.72dpiarmy.com/viewtopic.php?id=156 ) and that ( What is the best way to fixed-point math? ) And a series of discussions about whether the decimal point is really a fixed point or actually a floating point (update: respondents confirmed that it is definitely a floating point), but I have not seen a solid C # library for things like calculating cosine and sine.

My needs are simple - I need basic operators, plus cosine, sine, arctan2, PI ... I think about it. Maybe sqrt. I am programming a RTS 2D game in which I mainly work, but unit movement when using floating point mathematics (doubles) has very small errors over time (10-30 minutes) on several machines, which leads to gutting. It is currently only between a 32-bit OS and a 64-bit OS, all 32-bit machines seem to remain in sync without problems, and this makes me think that this is a floating point problem.

I knew about this as a possible problem from the very beginning and therefore limited my use of non-integer mathematics to the position as much as possible, but for smooth diagonal movement at different speeds, I calculate the angle between points in radians, then getting the components of the motion x and y with sin and cos. This is the main question. I also do some calculations for intersections of line segments, intersections of straight lines, intersections with a direct connection, etc., which also should probably be floating to a fixed point to avoid problems with multiple cars.

If there is something open in Java or VB or another comparable language, I could probably convert the code for my purposes. The main priority for me is accuracy, although I would like as little speed loss as possible compared to current performance. This whole fixed-point math thing is very useful to me, and I am surprised at how little practical information there is about it on google - most things seem to be either theory or dense C ++ header files.

Anything you could do to point me in the right direction is greatly appreciated; if I can get this working, I plan to open up the original math functions that I put together so that there is a resource for other C # programmers.

UPDATE: I could definitely create a cosine / sine lookup table for my purposes, but I don't think this would work for arctan2, since I would need to create a table about 64,000x64,000 records (yikes) in size. If you know any programmatic explanation of effective ways to calculate things like arctan2, that would be awesome. My math background is fine, but advanced formulas and traditional math notation are very difficult to translate into code.

Answer 1

Ok, here is what I came up with for a fixed-point structure based on the link in my original question, but also including some fixes to how it handled 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; fX = (FInt)pX; fY = (FInt)pY; return f; } public static Point ToPoint( FPoint f ) { return new Point( fXIntValue, fYIntValue ); } #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 } 

Based on comments from ShuggyCoUk, I see that it is in Q12 format. This is accurate enough for my purposes. Of course, in addition to corrections, I already had this basic format before I asked my question. What I was looking for was a way to calculate Sqrt, Atan2, Sin and Cos in C # using such a structure. In C #, I don't know any other things that will handle this, but in Java I managed to find the MathFP Onno Hommes library. This is a free software license, so I reworked some of my functions for my purposes in C # (with atan2 fix, 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 

Dr. Homme's MathFP library has a number of other functions, but they were higher than what I needed, so I did not find the time to translate them into C # (this process was complicated by the fact that it used a long one, and I use the structure FInt, which makes the conversion rules a bit complicated to see immediately).

The accuracy of these functions, since they are encoded here, is more than enough for my purposes, but if you need more, you can increase the SHIFT AMOUNT by FInt. Just keep in mind that if you do this, then the Dr. Hommes function constants should then be divided by 4096 and then multiplied by what your new SHIFT AMOUNT sum requires. You’ll probably encounter some errors if you do this and you won’t be careful, so be sure to check against the built-in math functions to make sure that your results are not delayed if you set the constant incorrectly.

So far, this FInt logic has looked just as fast, if not a little faster than the equivalent .net built-in function. This will obviously be changed by the machine, as the fp coprocessor will detect this, so I do not run certain tests. But now they are integrated into my game, and I saw a slight decrease in processor load compared to the previous one (this is in the Q6600 quad core with an average of 1%).

Thanks again to everyone who commented on your help. No one pointed me directly to what I was looking for, but you gave me some clues that helped me find it on Google. I hope this code proves useful to someone else, as it seems nothing is comparable to C # publicly.

Answer 2

Use 64-bit integers, for example, a scale of 1/1000. You can add and subtract usually. When you need to multiply, then multiply the integers, and then divide them by 1000. When you need sqrt, sin, cos, etc., Then convert to long double, divide by 1000, sqrt, multiply by 1000, convert to integer . Differences between machines should not matter.

You can use a different scale for faster divisions, for example 1024 as x/1024 == x >> 10 .

Answer 3

I know this thread is a bit outdated, but for the record here is a link to a project that implements fixed-point math in C #: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 4

I implemented in Q # the type Q31.32 with a fixed point. It does all the basic arithmetic, sqrt, sin, cos, tan and is well lit by unit tests. You can find here , an interesting type is Fix64 .:

Please note that the library also includes types Fix32, Fix16 and Fix8, but they were mainly for experiments and were not so complete and without errors.

Answer 5

Like scaled integers, there are several arbitrary number libraries of numbers that typically include the BigRational type, and a fixed point is a fixed power of ten denominators.

Answer 6

I created a similar fixed point structure. You get a performance hit using new () because it puts data in a heap, even if you use a structure. See Google (C # Heap (ing) Vs Stack (ing) in .NET: Part I), the true power of using struct is the inability to not use new and pass by value the stack. My example below does the following on the stack. 1. [result of int] on the stack 2. [a int] on the stack 3. [b int] on the stack 4. The operator [*] on the stack 5. The result of the result did not return any costs for the heap.

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