Математика с фиксированной точкой в ​​C #?

Question

Мне было интересно, если кто-нибудь здесь знает какие-либо хорошие ресурсы для математики с фиксированной запятой в c #? Я видел такие вещи (http://2ddev.72dpiarmy.com/viewtopic.php?id=156) и это ( Какой лучший способ сделать математику с фиксированной точкой? * ), и ряд дискуссий о том, является ли десятичная дробь действительно фиксированной точкой или фактически с плавающей запятой (обновление: респонденты подтвердили, что это определенно с плавающей запятой), но я не видел надежной библиотеки C # для таких вещей, как вычисление косинуса и синуса.

Мои потребности просты - мне нужны основные операторы, плюс косинус, синус, arctan2, PI ... Я думаю, что это все. Может быть, sqrt. Я программирую 2D RTS-игру, над которой я в основном работаю, но движение юнитов при использовании математики с плавающей запятой (удваивается) имеет очень малые неточности во времени (10-30 минут) на нескольких машинах, что приводит к рассинхронизации. В настоящее время это происходит только между 32-битной и 64-битной ОС, все 32-битные машины, кажется, синхронизируются без проблем, что заставляет меня думать, что это проблема с плавающей запятой.

С самого начала я знал об этом как о возможной проблеме, и поэтому я ограничил использование математики нецелым положением настолько, насколько это возможно, но для плавного диагонального движения на разных скоростях я вычисляю угол между точками в радианы, затем получая x и y компоненты движения с помощью sin и cos. Это главная проблема. Я также делаю некоторые расчеты для пересечений отрезков, пересечений линий и окружностей, пересечений между окружностями и т. Д., Которые также, вероятно, должны переходить от плавающей точки к фиксированной точке, чтобы избежать проблем между машинами.

Если есть что-то с открытым исходным кодом в Java или VB или другом сопоставимом языке, я мог бы, вероятно, преобразовать код для своих нужд. Главным приоритетом для меня является точность, хотя я бы хотел, чтобы потеря скорости была минимальной по сравнению с нынешними показателями. Вся эта математика с фиксированной запятой очень нова для меня, и я удивлен тем, как мало практической информации об этом есть в Google - большинство вещей, похоже, являются либо теорией, либо плотными заголовочными файлами C ++.

Все, что вы могли сделать, чтобы указать мне правильное направление, высоко ценится; если я смогу заставить это работать, я планирую открыть с открытым исходным кодом математические функции, которые я собрал, чтобы был ресурс для других программистов на C #.

ОБНОВЛЕНИЕ: Я определенно мог бы заставить таблицу поиска косинус / синус работать для моих целей, но я не думаю, что это сработало бы для arctan2, так как мне нужно было бы сгенерировать таблицу с примерно 64 000 x 64 000 записей (yikes ). Если вам известны какие-либо программные объяснения эффективных способов вычисления таких вещей, как 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. Это достаточно точно для моих целей. Конечно, кроме исправлений, у меня уже был этот базовый формат, прежде чем я задал свой вопрос. Я искал способы вычисления 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 # (этот процесс усложнился из-за того, что он использовал long, а я использую структуру FInt, из-за чего правила преобразования немного сложно увидеть сразу).

Точность этих функций, поскольку они здесь закодированы, более чем достаточна для моих целей, но если вам нужно больше, вы можете увеличить СУММУ СДВИГА на FInt. Просто имейте в виду, что если вы сделаете это, константы функций доктора Хоммса нужно будет затем разделить на 4096, а затем умножить на все, что требуется вашей новой сумме SHIFT. Вы, вероятно, столкнетесь с некоторыми ошибками, если будете это делать и не будете осторожны, поэтому обязательно запустите проверку встроенных математических функций, чтобы убедиться, что ваши результаты не откладываются из-за неправильной настройки константы.

Пока что эта логика FInt кажется такой же быстрой, если не чуть более быстрой, чем эквивалентные встроенные функции .net. Очевидно, это будет зависеть от машины, так как сопроцессор fp определит это, поэтому я не проводил конкретные тесты. Но теперь они интегрированы в мою игру, и я заметил небольшое снижение загрузки процессора по сравнению с предыдущим (это на четырехъядерном процессоре Q6600 - в среднем примерно на 1% меньше).

Еще раз спасибо всем, кто прокомментировал вашу помощь. Никто не указал мне прямо на то, что я искал, но вы дали мне несколько подсказок, которые помогли мне найти его в Google. Я надеюсь, что этот код окажется полезным для кого-то другого, поскольку в C #, опубликованном публично, нет ничего похожего.

Answer 2

Используйте 64-битные целые числа, например, в масштабе 1/1000. Вы можете сложить и вычесть нормально. Когда вам нужно умножить, затем умножить целые числа, а затем разделить на 1000. Когда вам нужно sqrt, sin, cos и т. Д., Затем конвертировать в long double, разделить на 1000, sqrt, умножить на 1000, преобразовать в целое число Тогда различия между машинами не должны иметь значения.

Вы можете использовать другую шкалу для более быстрого деления, например 1024 как x/1024 == x >> 10.

Answer 3

Я реализовал тип Q31.32 с фиксированной запятой в C #. Он выполняет всю основную арифметику, sqrt, sin, cos, tan и хорошо освещается модульными тестами. Вы можете найти его здесь , интересный тип - Fix64. :

Обратите внимание, что библиотека также включает в себя типы Fix32, Fix16 и Fix8, но они были в основном для экспериментов и не так полны и не содержат ошибок.

Answer 4

Я знаю, что этот поток немного староват, но для справки вот ссылка на проект, который реализует математику с фиксированной точкой в ​​C #: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 5

Я создал похожую структуру с фиксированной точкой. Вы получаете снижение производительности, используя new (), потому что он помещает данные в кучу, даже если вы используете структуру. См. Google (C # Heap (ing) против стека (ing) в .NET: Часть I), истинная сила использования struct - это способность не использовать new и передавать значение в стек. Мой пример ниже делает следующее в стеке. 1. [результат int] в стеке 2. [int] в стеке 3. [b int] в стеке 4. [*] оператор в стеке 5. Значение результата вернулось без кучи выделенных затрат.

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

Answer 6

Наряду с масштабируемыми целыми числами существует несколько числовых библиотек произвольной точности, которые обычно включают тип "BigRational", а фиксированная точка - это просто фиксированная степень десяти знаменателя.