Quelles techniques d'approximation existent pour calculer la racine carrée?

J'ai des ressources très limitées car je travaille avec un microcontrôleur. Existe-t-il une extension de la série Taylor, une table de recherche commune ou une approche récursive?

Je préfère faire quelque chose sans utiliser sqrt () de math.h

http://www.cplusplus.com/reference/cmath/sqrt/

si vous voulez une expansion de la série de puissance optimisée bon marché et sale (les coefficients de la série Taylor convergent lentement) pour sqrt()et un tas d'autres trancendentals, j'ai du code d'il y a longtemps. J'avais l'habitude de vendre ce code, mais personne ne me l'a payé pendant près d'une décennie. donc je pense que je vais le publier pour la consommation publique. ce fichier particulier était destiné à une application dans laquelle le processeur avait une virgule flottante (simple précision IEEE-754) et ils avaient un compilateur C et un système de développement, mais ils n'en avaient pasavoir (ou ils ne voulaient pas lier) le stdlib qui aurait eu les fonctions mathématiques standard. ils n'avaient pas besoin d'une précision parfaite, mais ils voulaient que les choses soient rapides. vous pouvez assez facilement désosser le code pour voir quels sont les coefficients de la série de puissance et écrire votre propre code. ce code suppose IEEE-754 et masque les bits pour la mantisse et l'exposant.

il semble que le "balisage de code" de SE ne soit pas convivial avec les caractères angulaires (vous savez ">" ou "<"), vous devrez donc probablement appuyer sur "modifier" pour tout voir.

//
//    FILE: __functions.h
//
//    fast and approximate transcendental functions
//
//    copyright (c) 2004  Robert Bristow-Johnson
//
//    [email protected]
//


#ifndef __FUNCTIONS_H
#define __FUNCTIONS_H

#define TINY 1.0e-8
#define HUGE 1.0e8

#define PI              (3.1415926535897932384626433832795028841972)        /* pi */
#define ONE_OVER_PI     (0.3183098861837906661338147750939)
#define TWOPI           (6.2831853071795864769252867665590057683943)        /* 2*pi */
#define ONE_OVER_TWOPI  (0.15915494309189535682609381638)
#define PI_2            (1.5707963267948966192313216916397514420986)        /* pi/2 */
#define TWO_OVER_PI     (0.636619772367581332267629550188)
#define LN2             (0.6931471805599453094172321214581765680755)        /* ln(2) */
#define ONE_OVER_LN2    (1.44269504088896333066907387547)
#define LN10            (2.3025850929940456840179914546843642076011)        /* ln(10) */
#define ONE_OVER_LN10   (0.43429448190325177635683940025)
#define ROOT2           (1.4142135623730950488016887242096980785697)        /* sqrt(2) */
#define ONE_OVER_ROOT2  (0.707106781186547438494264988549)

#define DB_LOG2_ENERGY          (3.01029995663981154631945610163)           /* dB = DB_LOG2_ENERGY*__log2(energy) */
#define DB_LOG2_AMPL            (6.02059991327962309263891220326)           /* dB = DB_LOG2_AMPL*__log2(amplitude) */
#define ONE_OVER_DB_LOG2_AMPL   (0.16609640474436811218256075335)           /* amplitude = __exp2(ONE_OVER_DB_LOG2_AMPL*dB) */

#define LONG_OFFSET     4096L
#define FLOAT_OFFSET    4096.0



float   __sqrt(float x);

float   __log2(float x);
float   __exp2(float x);

float   __log(float x);
float   __exp(float x);

float   __pow(float x, float y);

float   __sin_pi(float x);
float   __cos_pi(float x);

float   __sin(float x);
float   __cos(float x);
float   __tan(float x);

float   __atan(float x);
float   __asin(float x);
float   __acos(float x);

float   __arg(float Imag, float Real);

float   __poly(float *a, int order, float x);
float   __map(float *f, float scaler, float x);
float   __discreteMap(float *f, float scaler, float x);

unsigned long __random();

#endif




//
//    FILE: __functions.c
//
//    fast and approximate transcendental functions
//
//    copyright (c) 2004  Robert Bristow-Johnson
//
//    [email protected]
//

#define STD_MATH_LIB 0

#include "__functions.h"

#if STD_MATH_LIB
#include "math.h"   // angle brackets don't work with SE markup
#endif




float   __sqrt(register float x)
    {
#if STD_MATH_LIB
    return (float) sqrt((double)x);
#else
    if (x > 5.877471754e-39)
        {
        register float accumulator, xPower;
        register long intPart;
        register union {float f; long i;} xBits;

        xBits.f = x;

        intPart = ((xBits.i)>>23);                  /* get biased exponent */
        intPart -= 127;                             /* unbias it */

        x = (float)(xBits.i & 0x007FFFFF);          /* mask off exponent leaving 0x800000*(mantissa - 1) */
        x *= 1.192092895507812e-07;                 /* divide by 0x800000 */

        accumulator =  1.0 + 0.49959804148061*x;
        xPower = x*x;
        accumulator += -0.12047308243453*xPower;
        xPower *= x;
        accumulator += 0.04585425015501*xPower;
        xPower *= x;
        accumulator += -0.01076564682800*xPower;

        if (intPart & 0x00000001)
            {
            accumulator *= ROOT2;                   /* an odd input exponent means an extra sqrt(2) in the output */
            }

        xBits.i = intPart >> 1;                     /* divide exponent by 2, lose LSB */
        xBits.i += 127;                             /* rebias exponent */
        xBits.i <<= 23;                             /* move biased exponent into exponent bits */

        return accumulator * xBits.f;
        }
     else
        {
        return 0.0;
        }
#endif
    }




float   __log2(register float x)
    {
#if STD_MATH_LIB
    return (float) (ONE_OVER_LN2*log((double)x));
#else
    if (x > 5.877471754e-39)
        {
        register float accumulator, xPower;
        register long intPart;

        register union {float f; long i;} xBits;

        xBits.f = x;

        intPart = ((xBits.i)>>23);                  /* get biased exponent */
        intPart -= 127;                             /* unbias it */

        x = (float)(xBits.i & 0x007FFFFF);          /* mask off exponent leaving 0x800000*(mantissa - 1) */
        x *= 1.192092895507812e-07;                 /* divide by 0x800000 */

        accumulator = 1.44254494359510*x;
        xPower = x*x;
        accumulator += -0.71814525675041*xPower;
        xPower *= x;
        accumulator += 0.45754919692582*xPower;
        xPower *= x;
        accumulator += -0.27790534462866*xPower;
        xPower *= x;
        accumulator += 0.12179791068782*xPower;
        xPower *= x;
        accumulator += -0.02584144982967*xPower;

        return accumulator + (float)intPart;
        }
     else
        {
        return -HUGE;
        }
#endif
    }


float   __exp2(register float x)
    {
#if STD_MATH_LIB
    return (float) exp(LN2*(double)x);
#else
    if (x >= -127.0)
        {
        register float accumulator, xPower;
        register union {float f; long i;} xBits;

        xBits.i = (long)(x + FLOAT_OFFSET) - LONG_OFFSET;       /* integer part */
        x -= (float)(xBits.i);                                  /* fractional part */

        accumulator = 1.0 + 0.69303212081966*x;
        xPower = x*x;
        accumulator += 0.24137976293709*xPower;
        xPower *= x;
        accumulator += 0.05203236900844*xPower;
        xPower *= x;
        accumulator += 0.01355574723481*xPower;

        xBits.i += 127;                                         /* bias integer part */
        xBits.i <<= 23;                                         /* move biased int part into exponent bits */

        return accumulator * xBits.f;
        }
     else
        {
        return 0.0;
        }
#endif
    }


float   __log(register float x)
    {
#if STD_MATH_LIB
    return (float) log((double)x);
#else
    return LN2*__log2(x);
#endif
    }

float   __exp(register float x)
    {
#if STD_MATH_LIB
    return (float) exp((double)x);
#else
    return __exp2(ONE_OVER_LN2*x);
#endif
    }

float   __pow(float x, float y)
    {
#if STD_MATH_LIB
    return (float) pow((double)x, (double)y);
#else
    return __exp2(y*__log2(x));
#endif
    }




float   __sin_pi(register float x)
    {
#if STD_MATH_LIB
    return (float) sin(PI*(double)x);
#else
    register float accumulator, xPower, xSquared;

    register long evenIntPart = ((long)(0.5*x + 1024.5) - 1024)<<1;
    x -= (float)evenIntPart;

    xSquared = x*x;
    accumulator = 3.14159265358979*x;
    xPower = xSquared*x;
    accumulator += -5.16731953364340*xPower;
    xPower *= xSquared;
    accumulator += 2.54620566822659*xPower;
    xPower *= xSquared;
    accumulator += -0.586027023087261*xPower;
    xPower *= xSquared;
    accumulator += 0.06554823491427*xPower;

    return accumulator;
#endif
    }


float   __cos_pi(register float x)
    {
#if STD_MATH_LIB
    return (float) cos(PI*(double)x);
#else
    register float accumulator, xPower, xSquared;

    register long evenIntPart = ((long)(0.5*x + 1024.5) - 1024)<<1;
    x -= (float)evenIntPart;

    xSquared = x*x;
    accumulator = 1.57079632679490*x;                       /* series for sin(PI/2*x) */
    xPower = xSquared*x;
    accumulator += -0.64596406188166*xPower;
    xPower *= xSquared;
    accumulator += 0.07969158490912*xPower;
    xPower *= xSquared;
    accumulator += -0.00467687997706*xPower;
    xPower *= xSquared;
    accumulator += 0.00015303015470*xPower;

    return 1.0 - 2.0*accumulator*accumulator;               /* cos(w) = 1 - 2*(sin(w/2))^2 */
#endif
    }


float   __sin(register float x)
    {
#if STD_MATH_LIB
    return (float) sin((double)x);
#else
    x *= ONE_OVER_PI;
    return __sin_pi(x);
#endif
    }

float   __cos(register float x)
    {
#if STD_MATH_LIB
    return (float) cos((double)x);
#else
    x *= ONE_OVER_PI;
    return __cos_pi(x);
#endif
    }

float   __tan(register float x)
    {
#if STD_MATH_LIB
    return (float) tan((double)x);
#else
    x *= ONE_OVER_PI;
    return __sin_pi(x)/__cos_pi(x);
#endif
    }




float   __atan(register float x)
    {
#if STD_MATH_LIB
    return (float) atan((double)x);
#else
    register float accumulator, xPower, xSquared, offset;

    offset = 0.0;

    if (x < -1.0)
        {
        offset = -PI_2;
        x = -1.0/x;
        }
     else if (x > 1.0)
        {
        offset = PI_2;
        x = -1.0/x;
        }
    xSquared = x*x;
    accumulator = 1.0;
    xPower = xSquared;
    accumulator += 0.33288950512027*xPower;
    xPower *= xSquared;
    accumulator += -0.08467922817644*xPower;
    xPower *= xSquared;
    accumulator += 0.03252232640125*xPower;
    xPower *= xSquared;
    accumulator += -0.00749305860992*xPower;

    return offset + x/accumulator;
#endif
    }


float   __asin(register float x)
    {
#if STD_MATH_LIB
    return (float) asin((double)x);
#else
    return __atan(x/__sqrt(1.0 - x*x));
#endif
    }

float   __acos(register float x)
    {
#if STD_MATH_LIB
    return (float) acos((double)x);
#else
    return __atan(__sqrt(1.0 - x*x)/x);
#endif
    }


float   __arg(float Imag, float Real)
    {
#if STD_MATH_LIB
    return (float) atan2((double)Imag, (double)Real);
#else
    register float accumulator, xPower, xSquared, offset, x;

    if (Imag > 0.0)
        {
        if (Imag <= -Real)
            {
            offset = PI;
            x = Imag/Real;
            }
         else if (Imag > Real)
            {
            offset = PI_2;
            x = -Real/Imag;
            }
         else
            {
            offset = 0.0;
            x = Imag/Real;
            }
        }
     else
        {
        if (Imag >= Real)
            {
            offset = -PI;
            x = Imag/Real;
            }
         else if (Imag < -Real)
            {
            offset = -PI_2;
            x = -Real/Imag;
            }
         else
            {
            offset = 0.0;
            x = Imag/Real;
            }
        }

    xSquared = x*x;
    accumulator = 1.0;
    xPower = xSquared;
    accumulator += 0.33288950512027*xPower;
    xPower *= xSquared;
    accumulator += -0.08467922817644*xPower;
    xPower *= xSquared;
    accumulator += 0.03252232640125*xPower;
    xPower *= xSquared;
    accumulator += -0.00749305860992*xPower;

    return offset + x/accumulator;
#endif
    }




float   __poly(float *a, int order, float x)
    {
    register float accumulator = 0.0, xPower;
    register int n;

    accumulator = a[0];
    xPower = x;
    for (n=1; n<=order; n++)
        {
        accumulator += a[n]*xPower;
        xPower *= x;
        }

    return accumulator;
    }


float   __map(float *f, float scaler, float x)
    {
    register long i;

    x *= scaler;

    i = (long)(x + FLOAT_OFFSET) - LONG_OFFSET;         /* round down without floor() */

    return f[i] + (f[i+1] - f[i])*(x - (float)i);       /* linear interpolate between points */
    }


float   __discreteMap(float *f, float scaler, float x)
    {
    register long i;

    x *= scaler;

    i = (long)(x + (FLOAT_OFFSET+0.5)) - LONG_OFFSET;   /* round to nearest */

    return f[i];
    }


unsigned long __random()
    {
    static unsigned long seed0 = 0x5B7A2775, seed1 = 0x80C7169F;

    seed0 += seed1;
    seed1 += seed0;

    return seed1;
    }

Si vous ne l'avez pas vu, la "racine carrée de Quake" est tout simplement mystificatrice. Il utilise une magie au niveau du bit pour vous donner une très bonne première approximation, puis utilise une ou deux approximations de Newton pour réviser. Cela pourrait vous aider si vous travaillez avec des ressources limitées.

https://en.wikipedia.org/wiki/Fast_inverse_square_root

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

Vous pouvez également approximer la fonction racine carrée en utilisant la méthode de Newton . La méthode de Newton est un moyen d'estimer où se trouvent les racines d'une fonction. C'est aussi une méthode itérative où le résultat de l'itération précédente est utilisé dans l'itération suivante jusqu'à la convergence. L'équation de la méthode de Newton pour deviner où se trouve la racine d'une fonction étant donné une supposition initiale x 0 est définie comme suit:$f(x)$$x_0$

$$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

est la première estimation de l'emplacement de la racine. Nous continuons de recycler l'équation et d'utiliser les résultats des itérations précédentes jusqu'à ce que la réponse ne change pas. En général, pour déterminer la supposition de la racine à l'itération ( n + 1 ) , étant donné que la supposition à l'itération n est définie comme:$x_1$$(n+1)$$n$

$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

Pour utiliser la méthode de Newton pour approximer la racine carrée, supposons que l'on nous donne un nombre . En tant que tel, pour calculer la racine carrée, nous devons calculer $a$ En tant que tel, nous cherchons à trouver une réponse telle quex=$\sqrt{a}$ . Mettre les deux côtés au carré et déplacerade l'autre côté de l'équation donnex2-a=0. En tant que tel, la réponse à cette équation est$x = \sqrt{a}$$a$$x^2 - a = 0$ et est donc laracinede la fonction. En tant que tel, soitf(x)=x2-al'équation dont nous voulons trouver la racine. En substituant ceci dans la méthode de Newton,f′(x)=2x, et donc:$\sqrt{a}$$f(x) = x^2 - a$$f'(x) = 2x$

xn+1=

$$x_{n+1} = x_n - \frac{x_{n}^2 - a}{2x_{n}}$$ $$x_{n+1} = \frac{1}{2}\left(x_n + \frac{a}{x_n}\right)$$

Par conséquent, pour calculer la racine carrée de , nous devons simplement calculer la méthode de Newton jusqu'à ce que nous convergions. Cependant, comme l'a noté @ robertbristow-johnson, la division est une opération très coûteuse - en particulier pour les microcontrôleurs / DSP avec des ressources limitées. De plus, il peut y avoir un cas où une estimation peut être 0, ce qui entraînerait une erreur de division par 0 en raison de l'opération de division. En tant que tel, ce que nous pouvons faire est d'utiliser la méthode de Newton et de résoudre la fonction réciproque à la place, c'est-à-dire $a$ . Cela évite également toute division, comme nous le verrons plus loin. Équerrage des deux côtés et déplacement$\frac{1}{x} = \sqrt{a}$ vers la gauche donne donc$\sqrt{a}$. Par conséquent, la solution à ce problème serait$\frac{1}{x^2} - a = 0$ . En multipliant para, nous obtiendrions le résultat souhaité. Encore une fois, en utilisant la méthode de Newton, nous avons donc:$\frac{1}{\sqrt{a}}$$a$

xn+1=xn-

$$x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}$$ xn+1= $$x_{n+1} = x_{n} - \frac{\frac{1}{(x_n)^2} - a}{\frac{-2}{(x_n)^3}}$$ $$x_{n+1} = \frac{1}{2}\left(3x_n - (x_n)^3a\right)$$

Cependant, il y a un avertissement que nous devons considérer lors de l'examen de l'équation ci-dessus. Pour les racines carrées, la solution doit être positive et donc pour que les itérations (et le résultat) soient positifs, la condition suivante doit être remplie:

$$3x_n - (x_n)^3a > 0$$ $$3x_n > (x_n)^3a$$ $$(x_n)^2a < 3$$

Par conséquent:

$$(x_0)^2a < 3$$

$x_0$$x_0$$x_0$$10^{-6}$ environ).

Comme votre balise recherche un algorithme C, écrivons-en un très rapidement:

#include <stdio.h> // For printf
#include <math.h> // For fabs
void main() 
{
   float a = 5.0; // Number we want to take the square root of
   float x = 1.0; // Initial guess
   float xprev; // Root for previous iteration
   int count; // Counter for iterations

   // Find a better initial guess
   // Half at each step until condition is satisfied
   while (x*x*a >= 3.0)
       x *= 0.5;

   printf("Initial guess: %f\n", x);

   count = 1; 
   do { 
       xprev = x; // Save for previous iteration
       printf("Iteration #%d: %f\n", count++, x);                   
       x = 0.5*(3*xprev - (xprev*xprev*xprev)*a); // Find square root of the reciprocal
   } while (fabs(x - xprev) > 1e-6); 

   x *= a; // Actual answer - Multiply by a
   printf("Square root is: %f\n", x);
   printf("Done!");
}

Il s'agit d'une implémentation assez basique de la méthode de Newton. Notez que je continue de diminuer de moitié la supposition initiale jusqu'à ce que la condition dont nous avons parlé plus tôt soit satisfaite. J'essaie également de trouver la racine carrée de 5. Nous savons que cela est à peu près égal à 2,236 environ. L'utilisation du code ci-dessus donne la sortie suivante:

Initial guess: 0.500000
Iteration #1: 0.500000
Iteration #2: 0.437500
Iteration #3: 0.446899
Iteration #4: 0.447213
Square root is: 2.236068
Done!

$a$

Initial guess: 0.015625
Iteration #1: 0.015625
Iteration #2: 0.004601
Iteration #3: 0.006420
Iteration #4: 0.008323
Iteration #5: 0.009638
Iteration #6: 0.010036
Iteration #7: 0.010062
Square root is: 99.378067
Done!

Comme vous pouvez le voir, la seule chose qui est différente est le nombre d'itérations nécessaires pour calculer la racine carrée. Plus le nombre de ce que vous voulez calculer est élevé, plus il faudra d'itérations.

Je sais que cette méthode a déjà été suggérée dans un article précédent, mais je me suis dit que je dériverais la méthode et fournirais du code!

$\sqrt{x}$

oui, une série de puissances peut rapidement et efficacement se rapprocher de la fonction racine carrée, et uniquement sur un domaine limité. plus le domaine est large, plus vous aurez besoin de termes dans votre série de puissance pour maintenir l'erreur suffisamment faible.

$1 \le x \le 2$

$$\begin{align} \sqrt{x} \ &\approx \ 1 + a_1 (x-1) + a_2 (x-1)^2 + a_3 (x-1)^3 + a_4 (x-1)^4 \\ \\ & = 1 + (x-1)\bigg( a_1 + (x-1)\Big( a_2 + (x-1)\big( a_3 + (x-1)a_4 \big) \Big) \bigg) \\ \end{align}$$

où

$a_1$ = 0,49959804148061

$a_2$ = -0,12047308243453

$a_3$ = 0,04585425015501

$a_4$ = -0,01076564682800

$x=1$$x=2$ et le maximum relatif erreur entre les deux est minimisée.

$2n$$n$$\sqrt{2}$ , qui peut être stocké en tant que constante dans votre code.

s'il s'agit d'une virgule flottante, vous devez séparer l'exposant et la mantisse comme mon code C le fait dans l'autre réponse.

En fait, cela se fait en résolvant une équation quadratique en utilisant la méthode de Newton:

http://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Pour les nombres supérieurs à un, vous pouvez utiliser l'extension Taylor suivante:

http://planetmath.org/taylorexpansionofsqrt1x

Une expansion de racine carrée qui m'a intrigué dans le passé est celle de l'ampleur complexe (ou diagonale dans un rectangle); si$a>b$, puis:

$$\sqrt{a^2+b^2}\approx 0.96a+0.4 b.$$

Dans une précision de 4%, si je me souviens bien. Il a été utilisé par les ingénieurs, avant les règles logarithmiques et les calculatrices. Je l'ai appris dans Notes et formules de l'ingénieur, De Laharpe , 1923