Математика с фиксированной точкой в C#?
Мне было интересно, если кто-нибудь здесь знает какие-либо хорошие ресурсы для математики с фиксированной запятой в C#? Я видел такие вещи ( http://2ddev.72dpiarmy.com/viewtopic.php?id=156) и это ( Каков лучший способ сделать математику с фиксированной запятой?) И ряд дискуссий о том, является ли десятичная дробь действительно с фиксированной или с плавающей точкой (обновление: респонденты подтвердили, что это определенно с плавающей точкой), но я не видел надежной библиотеки C# для таких вещей, как вычисление косинуса и синуса.
Мои потребности просты - мне нужны основные операторы, плюс косинус, синус, arctan2, PI... Я думаю, что это все. Может быть, sqrt. Я программирую 2D-игру RTS, над которой я в основном работаю, но движение юнитов при использовании математики с плавающей запятой (удваивается) имеет очень небольшие неточности во времени (10-30 минут) на нескольких машинах, что приводит к рассинхронизации. В настоящее время это происходит только между 32-битной и 64-битной ОС, все 32-битные машины, кажется, синхронизируются без проблем, что заставляет меня думать, что это проблема с плавающей запятой.
Я знал об этом как возможную проблему с самого начала, и поэтому я ограничил мое использование нецелочисленной математики позиции настолько, насколько это возможно, но для плавного диагонального перемещения с различными скоростями я вычисляю угол между точками в радианах, затем получить x и y составляющие движения с грехом и cos. Это основная проблема. Я также делаю некоторые расчеты для пересечений отрезков, пересечений линий и окружностей, пересечений между окружностями и т. Д., Которые также, вероятно, должны перейти от плавающей точки к фиксированной точке, чтобы избежать проблем между машинами.
Если есть что-то с открытым исходным кодом в Java или VB или другом сопоставимом языке, я мог бы, вероятно, преобразовать код для своих нужд. Основным приоритетом для меня является точность, хотя я бы хотел как можно меньше потери скорости по сравнению с нынешними показателями. Вся эта математика с фиксированной запятой очень нова для меня, и меня удивляет, как мало практической информации об этом есть в Google - большинство вещей, похоже, являются либо теорией, либо плотными заголовочными файлами C++.
Все, что вы могли сделать, чтобы указать мне правильное направление, высоко ценится; если я смогу заставить это работать, я планирую открыть с открытым исходным кодом математические функции, которые я собрал, чтобы был ресурс для других программистов на C#.
ОБНОВЛЕНИЕ: Я определенно мог бы заставить таблицу поиска косинус / синус работать для моих целей, но я не думаю, что это сработало бы для arctan2, так как мне нужно было бы сгенерировать таблицу с примерно 64 000x64 000 записей (йек). Если вы знаете какие-либо программные объяснения эффективных способов вычисления таких вещей, как arctan2, это было бы замечательно. С моим математическим фоном все в порядке, но сложные формулы и традиционные математические обозначения мне очень трудно перевести в код.
6 ответов
Хорошо, вот что я придумал для структуры с фиксированной запятой, основанной на ссылке в моем исходном вопросе, но также включающей некоторые исправления того, как она обрабатывает деление и умножение, и добавила логику для модулей, сравнений, сдвигов и т. Д.:
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. Это достаточно точно для моих целей. Конечно, кроме исправлений, у меня уже был этот базовый формат, прежде чем я задал свой вопрос. Я искал способы вычисления Sqrt, Atan2, Sin и Cos в C# с использованием такой структуры. В 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
В библиотеке MathFP доктора Хоммса есть ряд других функций, но они оказались за рамками того, что мне было нужно, и поэтому я не потратил время на их перевод на C# (этот процесс стал очень сложным из-за того, что он использовал долго, и я использую структуру FInt, что делает правила конвертации немного сложными для просмотра сразу).
Точность этих функций в том виде, как они здесь закодированы, более чем достаточна для моих целей, но если вам нужно больше, вы можете увеличить СУММУ СДВИГА на FInt. Просто имейте в виду, что если вы сделаете это, константы функций доктора Хоммса нужно будет затем разделить на 4096, а затем умножить на все, что требуется вашей новой СУММЕ СДВИГА. Вы, вероятно, столкнетесь с некоторыми ошибками, если будете это делать и не будете осторожны, поэтому обязательно запустите проверку встроенных математических функций, чтобы убедиться, что ваши результаты не откладываются из-за неправильной настройки константы.
Пока что эта логика FInt кажется такой же быстрой, если не чуть более быстрой, чем эквивалентные встроенные функции.net. Очевидно, это будет зависеть от машины, так как сопроцессор fp определит это, поэтому я не проводил конкретные тесты. Но теперь они интегрированы в мою игру, и я заметил небольшое снижение загрузки процессора по сравнению с предыдущим (это на четырехъядерном процессоре Q6600 - в среднем примерно на 1%).
Еще раз спасибо всем, кто прокомментировал вашу помощь. Никто не указал мне прямо на то, что я искал, но вы дали мне несколько подсказок, которые помогли мне найти это в Google. Я надеюсь, что этот код окажется полезным для кого-то еще, так как в C#, опубликованном публично, нет ничего похожего.
Я реализовал тип Q31.32 с фиксированной запятой в C#. Он выполняет всю основную арифметику, sqrt, sin, cos, tan и хорошо покрыт юнит-тестами. Вы можете найти его здесь, интересный тип Fix64.:
Обратите внимание, что библиотека также включает в себя типы Fix32, Fix16 и Fix8, но они были в основном для экспериментов и не так полны и не содержат ошибок.
Используйте 64-битные целые числа, например, в масштабе 1/1000. Вы можете сложить и вычесть нормально. Когда вам нужно умножить, умножьте целые числа, а затем разделите на 1000. Когда вам нужно сделать sqrt, sin, cos и т. Д., Затем преобразовать в long double, разделить на 1000, sqrt, умножить на 1000, преобразовать в целое число. Различия между машинами тогда не должны иметь значения.
Вы можете использовать другую шкалу для более быстрого деления, например 1024 как x/1024 == x >> 10,
Я знаю, что этот поток немного староват, но для справки приведу ссылку на проект, который реализует математику с фиксированной запятой в C#: http://www.isquaredsoftware.com/XrossOneGDIPlus.php
Я создал похожую структуру с фиксированной точкой. Вы получаете снижение производительности, используя new(), потому что он помещает данные в кучу, даже если вы используете структуру. См. Google(C# Heap(ing) против стека (ing) в.NET: часть I), истинная сила использования struct - это способность не использовать new и передавать по значению в стек. Мой пример ниже делает следующее в стеке. 1. [результат int ] в стеке 2. [a int ] в стеке 3. [b int ] в стеке 4. оператор [[]] в стеке 5. возвращаемое значение не выделяет кучу затрат.
public static Num operator *(Num a, Num b)
{
Num result;
result.NumValue = a.NumValue * b.NumValue;
return result;
}
Наряду с масштабируемыми целыми числами существует несколько числовых библиотек произвольной точности, которые обычно включают тип "BigRational", а фиксированная точка - это просто фиксированная степень десяти знаменателя.