Calcul du point fixe en c #?

Question

Je me demandais si quelqu'un ici connaissait de bonnes ressources pour le calcul mathématique à point fixe en c #? J'ai vu des choses comme celle-là ( http://2ddev.72dpiarmy.com/viewtopic.php ? id = 156 ) et cela ( à quoi sert le meilleure façon de faire des calculs en virgule fixe? ), et un certain nombre de discussions sur le point de savoir si le point décimal est vraiment un point fixe ou un point réellement flottant (mise à jour: les répondants ont confirmé qu'il s'agit bien d'un point flottant), mais je n'ai pas vu une bibliothèque solide en C # pour le calcul du cosinus et du sinus.

Mes besoins sont simples: j'ai besoin des opérateurs de base, ainsi que du cosinus, du sinus, de l'arctan2, de l'IP ... Je pense que c'est à peu près tout. Peut-être sqrt. Je programme un jeu RTS 2D, sur lequel je travaille en grande partie, mais le mouvement de l’unité utilisant des calculs en virgule flottante (doubles) présente de très petites inexactitudes dans le temps (10 à 30 minutes) sur plusieurs machines, ce qui entraîne des désynchronisations. C’est actuellement entre un système d’exploitation 32 bits et un système d’exploitation 64 bits, toutes les machines 32 bits semblent rester synchronisées sans problème, ce qui me fait penser que c’est un problème à virgule flottante.

Je savais dès le départ que cette question était possible, et j’ai donc limité autant que possible mon calcul mathématique sur les positions non entières, mais pour un mouvement diagonal régulier à des vitesses variables, je calcule l’angle entre points radians, puis obtenir les composantes x et y du mouvement avec sin et cos. C'est le problème principal. Je fais également des calculs pour les intersections de segments de ligne, les intersections de ligne-cercle, les intersections de cercle-rect, etc., qui doivent également probablement passer de la virgule flottante à la virgule fixe pour éviter les problèmes inters machine.

S'il existe quelque chose d'open source en Java ou VB ou dans un autre langage comparable, je pourrais probablement convertir le code pour mes utilisations. La priorité principale pour moi est la précision, bien que je veuille une perte de vitesse aussi faible que possible par rapport aux performances actuelles. Cette mathématique à points fixes est très nouvelle pour moi, et je suis étonnée par le peu d’informations pratiques qui s'y trouvent sur Google. La plupart des choses semblent être de la théorie ou des fichiers d’en-tête C ++ denses.

Tout ce que vous pourriez faire pour me diriger dans la bonne direction est très apprécié. si je parviens à faire fonctionner cela, je prévois d’ouvrir à la source les fonctions mathématiques que j’ai assemblées de manière à créer une ressource pour les autres programmeurs C #.

UPDATE: Je pourrais certainement faire fonctionner une table de conversion cosinus / sinus pour mes besoins, mais je ne pense pas que cela fonctionnerait pour arctan2, car il me faudrait générer une table avec environ 64 000 x 64 000 entrées (bib ). Si vous connaissez des explications programmatiques sur des moyens efficaces de calculer des choses comme arctan2, ce serait génial. Mes connaissances en mathématiques vont bien, mais les formules avancées et la notation mathématique traditionnelle sont très difficiles à traduire en code.

Answer 1

Ok, voici ce que je propose pour une structure à virgule fixe, basée sur le lien de ma question initiale, mais comprenant également des corrections sur la manière dont elle gérait la division et la multiplication, ainsi qu'une logique ajoutée pour les modules, les comparaisons, décalages, 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
}

D'après les commentaires de ShuggyCoUk, je vois qu'il s'agit du format Q12. C'est assez précis pour mes besoins. Bien sûr, mis à part les corrections de bugs, j'avais déjà ce format de base avant de poser ma question. Ce que je cherchais, ce sont des façons de calculer Sqrt, Atan2, Sin et Cos en C # en utilisant une structure comme celle-ci. Je ne connais rien d'autre en C # qui puisse gérer cela, mais en Java, j'ai trouvé le bibliothèque MathFP par Onno Hommes. C'est une licence de logiciel source libérale, j'ai donc converti certaines 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 plusieurs autres fonctions dans la bibliothèque MathFP de Dr. Hommes, mais elles allaient au-delà de ce dont j'avais besoin. Je n'ai donc pas pris le temps de les traduire en C # (ce processus a été rendu encore plus difficile par le fait que il utilisait un long terme, et j'utilise la structure FInt, ce qui rend les règles de conversion difficiles à voir immédiatement).

L’exactitude de ces fonctions, telles qu’elles sont codées ici, est amplement suffisante pour mes besoins, mais si vous avez besoin de plus d’informations, vous pouvez augmenter le décalage du montant sur FInt. Sachez simplement que si vous le faites, les constantes des fonctions de Dr. Hommes devront ensuite être divisées par 4 096, puis multipliées par tout ce que votre nouveau SHIFT AMOUNT exigera. Si vous faites cela, vous risquez de rencontrer des bogues sans être prudent. Veillez donc à vérifier les fonctions Math intégrées pour vous assurer que vos résultats ne sont pas altérés par un mauvais réglage d'une constante.

Jusqu'à présent, cette logique FinT semble aussi rapide, sinon peut-être un peu plus rapide, que l'équivalent dans les fonctions .net intégrées. Cela varierait évidemment d'une machine à l'autre, puisque le coprocesseur fp le déterminerait, aussi je n'ai pas exécuté de tests de performance spécifiques. Mais ils sont maintenant intégrés à mon jeu et j’ai constaté une légère diminution de l’utilisation du processeur par rapport à l’avant (il s’agit d’un quad-core Q6600 - environ 1% d’utilisation en moyenne).

Merci encore à tous ceux qui ont commenté votre aide. Personne ne m'a indiqué directement ce que je cherchais, mais vous m'avez donné des indices qui m'ont aidé à le trouver moi-même sur Google. J'espère que ce code sera utile pour quelqu'un d'autre, car rien ne semble comparable en C # publié publiquement.

Answer 2

Utilisez des entiers 64 bits dans, par exemple, l'échelle 1/1000. Vous pouvez ajouter et soustraire normalement. Lorsque vous devez multiplier, multipliez les nombres entiers, puis divisez par 1000. Lorsque vous devez définir sqrt, sin, cos, etc., convertissez-les en long double, divisez par 1000, sqrt, multipliez par 1000, convertissez-les en entier. Les différences entre les machines ne devraient donc pas avoir d’importance.

Vous pouvez utiliser une autre échelle pour des divisions plus rapides, par exemple 1024 sous la forme x / 1024 == x > > 10 .

Answer 3

Je sais que ce fil est un peu vieux, mais voici un lien vers un projet qui implémente les calculs à virgule fixe en C #: http://www.isquaredsoftware.com/XrossOneGDIPlus.php

Answer 4

J'ai implémenté un type Q31.32 à virgule fixe en C #. Il exécute toutes les opérations arithmétiques de base, sqrt, sin, cos, tan, et est bien couvert par les tests unitaires. Vous pouvez le trouver ici , le type intéressant est Fix64. :

Notez que la bibliothèque inclut également les types Fix32, Fix16 et Fix8, mais ceux-ci étaient principalement destinés à l'expérimentation et ne sont pas aussi complets et sans anomalies.

Answer 5

Outre les entiers mis à l'échelle, il existe quelques bibliothèques numériques de précision arbitraire qui incluent généralement un "BigRational". type, et le point fixe est juste une puissance fixe de dix dénominateur.

Answer 6

J'ai créé une structure similaire à point fixe. New () vous donne un impact négatif sur les performances car il place des données sur le tas même si vous utilisez une structure. Voir Google (C # Heap (ing) vs Stack (ing) dans .NET: partie I) le véritable pouvoir de l'utilisation de struct est la possibilité de ne pas utiliser new et de transmettre valeur à la pile. Mon exemple ci-dessous fait ce qui suit sur la pile. 1. [result int] sur la pile 2. [un int] sur la pile 3. [b int] sur la pile 4. Opérateur [*] sur pile 5. value result n'a renvoyé aucun coût alloué au segment de mémoire.

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