Point fixe de mathématiques en c#?

Question

Je me demandais si quelqu'un ici sait de toute bonne ressources pour point fixe de mathématiques en c#? J'ai vu des choses comme ça (http://2ddev.72dpiarmy.com/viewtopic.php?id=156) et ce (http://stackoverflow.com/questions/79677/whats-the-best-way-to-do-fixed-point-math), et un certain nombre de discussions quant à savoir si la décimale est vraiment de point fixe ou en fait à virgule flottante (mise à jour: les intervenants ont confirmé que c'est certainement à virgule flottante), mais je n'ai pas vu un solide C# bibliothèque pour des choses comme le calcul de cosinus et de sinus.

Mes besoins sont simples -- j'ai besoin des opérateurs de base, plus le cosinus, le sinus, le arctan2, PI... je pense que c'est tout. Peut-être sqrt. Je suis de la programmation d'un 2D jeu de RTS, dont j'ai largement de travail, mais l'unité de mouvement lors de l'utilisation de mathématiques à virgule flottante (double) a de très petites inexactitudes dans le temps (de 10 à 30 minutes) sur plusieurs machines, conduisant à des désynchronisations. C'est actuellement uniquement entre un OS 32 bits et une version 64 bits de l'OS, tous les 32 bits de machines semblent rester dans la synchronisation sans problème, qui est ce qui me fait penser que c'est une virgule flottante question.

J'étais au courant de cette question dès le départ, et ont limité l'utilisation de la non-entier position de maths autant que possible, mais pour une fluidité de mouvement en diagonale à des vitesses variables, je suis le calcul de l'angle entre les points en radians, les composants x et y de mouvement avec sin et cos. C'est la grande question. Je suis aussi de faire quelques calculs pour le segment de la ligne, des intersections, des ligne-cercle intersections, cercle-rect intersections, etc, qui sera aussi probablement besoin de se déplacer à partir de floating-point à point fixe, afin d'éviter la machine à questions.

Si il y a quelque chose de l'open source en Java ou visual basic ou d'une autre comparable langue, je pourrais probablement convertir le code pour mes utilisations. La principale priorité pour moi est de la précision, mais j'aimerais que peu de perte de vitesse en plus de présenter des performances que possible. L'ensemble de ce point fixe de mathématiques chose est très nouveau pour moi, et je suis surpris par la façon dont, en pratique, peu d'informations sur elle il y a sur google -- la plupart des choses semble être la théorie denses ou C++ fichiers d'en-tête.

Tout ce que vous faites pour me pointer dans la bonne direction est très apprécié; si je peux obtenir ce travail, j'ai l'intention d'ouvrir-source les fonctions math j'ai mis en place de sorte qu'il sera une ressource pour les autres C#, programmeurs là-bas.

Mise à JOUR: je pourrais certainement faire un cosinus/sinus table de travail pour mes fins, mais je ne pense pas que cela fonctionnerait pour arctan2, puisque j'avais besoin de générer une table avec environ 64,000x64,000 entrées (aïe). Si vous connaissez toutes les programmatique explications de moyens efficaces pour calculer des choses comme arctan2, ce serait génial. Ma formation en mathématiques est tout droit, mais les formules avancées et de la traditionnelle notation mathématique est très difficile pour moi de traduire en code.

Answer 1

Ok, voici ce que j'ai trouvé pour un point fixe struct, basé sur le lien dans ma question d'origine mais aussi, y compris certains des correctifs à la façon dont elle a été la manipulation de la division et de la multiplication, et ajouté logique pour les modules, les comparaisons, les quarts de travail, 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
}

Sur la base des observations de ShuggyCoUk, je vois que c'est dans Q12 format. C'est assez précises pour mes fins. Bien sûr, outre les corrections de bugs, j'ai déjà eu ce format de base avant j'ai demandé à ma question. Ce que je cherchais à trouver des moyens pour calculer la Racine carrée, Atan2, Sin et Cos en C# à l'aide d'une structure de ce genre. Il n'y a pas d'autres choses que je connais en C# qui va traiter, mais en Java, j'ai réussi à trouver la MathFP bibliothèque par Onno Hommes. C'est un libéral de la source de licence du logiciel, donc j'ai converti quelques-uns de ses fonctions à mes fins en C# (avec un correctif pour atan2, je pense). Profitez de:

    #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

Il y a un certain nombre d'autres fonctions Dr Hommes' MathFP de la bibliothèque, mais ils ont été au-delà de ce dont j'avais besoin, et donc je n'ai pas pris le temps de les traduire en C# (ce processus a été rendu plus difficile par le fait qu'il a été à l'aide d'une longue, et je suis en utilisant le FInt struct, ce qui rend les règles de conversion sont un peu difficiles à voir immédiatement).

L'exactitude de ces fonctions, comme ils sont codés ici, c'est plus que suffisant pour mes besoins, mais si vous avez besoin de plus, vous pouvez augmenter la MAJ MONTANT de FInt. Juste être conscient que si vous le faites, l'une des constantes sur le Dr Hommes fonctions devront ensuite être divisé par 4096 et ensuite multiplié par quel que soit votre nouveau DÉCALAGE exige. Vous êtes susceptible de rencontrer quelques bugs si vous n'êtes pas prudent, alors assurez-vous d'exécuter les contrôles contre les fonctions Mathématiques pour vous assurer que vos résultats ne sont pas rebutés par incorrectement réglage d'une constante.

Jusqu'à présent, cette FInt logique semble aussi vite, si ce n'est peut-être un peu plus rapide, que l'équivalent construite dans .net fonctions. Que serait évidemment varier en fonction de la machine, depuis le fp coprocesseur serait de déterminer que, si je n'ai pas couru de référence spécifiques. Mais ils sont intégrés dans mon jeu maintenant, et j'ai vu une légère diminution de l'utilisation du processeur par rapport à avant (c'est sur un Q6600 quad core-sur une baisse de 1% de l'utilisation en moyenne).

Merci encore à tous ceux qui ont commenté pour votre aide. Personne ne m'a signalé directement à ce que je cherchais, mais vous m'avez donné quelques indices qui m'a aidé à me trouver moi-même sur google. J'espère que ce code s'avère être utile pour quelqu'un d'autre, car il ne semble pas être quelque chose de comparable en C# publié publiquement.

Answer 2

J'ai mis en place un point fixe Q31.32 type en C#. Il effectue toutes les opérations d'arithmétique de base, sqrt, sin, cos, tan, et il est bien couvert par les tests unitaires. Vous pouvez le trouver ici, l'intéressant est de type Fix64. :

Notez que la bibliothèque comprend également Fix32, Fix16 et Fix8 types, mais ceux-ci étaient principalement pour l'expérimentation et ne sont pas aussi complète et sans bug.

Answer 3

Utiliser des entiers 64 bits, par exemple, dans 1/1000 échelle. Vous pouvez ajouter et soustraire normalement. Lorsque vous avez besoin de multiplier ensuite multiplier des nombres entiers, puis diviser par 1000. Lorsque vous avez besoin de sqrt, sin, cos, etc. puis de les convertir à long double, diviser par 1000, sqrt, multipliez par 1000, à convertir en entier. Les différences entre les machines ne devrait pas d'importance alors.

Vous pouvez utiliser une autre échelle pour les plus rapides divise, par exemple 1024 comme x/1024 == x >> 10.

Answer 4

Je sais que ce thread est un peu vieux, mais pour la petite histoire, voici un lien vers un projet qui met en œuvre point fixe de mathématiques en C#: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 5

Ainsi que des entiers à l'échelle, il y a un peu de précision arbitraire numérique des bibliothèques qui comprennent généralement un "BigRational" le type, et le point fixe est juste une puissance fixe de dix dénominateur.