Clever Geek Handbook

stm32. Miramos la raíz

En lugar de presentar



El artículo contiene un ejemplo de optimización manual de una sección crítica de un programa de aplicación aplicado a microcontroladores stm32 de presupuesto, que aumenta el rendimiento 5 veces o más en comparación con una función de biblioteca.



La extracción de raíz cuadrada se usa a menudo en aplicaciones. La función sqrt está incluida en la biblioteca C estándar y opera con números reales:



double sqrt (double num);
long double sqrtl (long double num);


Los microcontroladores funcionan principalmente con números enteros; por lo general, no tienen registros para números reales.



En la práctica, además de la pérdida de velocidad computacional en múltiples transformaciones "entero <=> real" , también se pierde precisión - Ejemplo 1.



Ejemplo 1: pérdida de precisión en conversiones hacia adelante y hacia atrás



//  
uint32_t L1 = 169;
uint32_t L2 = 168;

//  
uint32_t r1 = ( uint32_t )sqrt( ( double ) L1 );
uint32_t r2 = ( uint32_t )sqrt( ( double ) L2 );

//  
L1 = r1*r1; // r1 = 13
L2 = r2*r2; // r2 = 12

//  
// L1 = 169 —  169
// L2 = 144 —  168,    14%


Formulación del problema



Aumente la precisión de los cálculos de sqrt redondeando al entero más cercano.

Si es posible, aumente la productividad.



La solucion del problema



Cree una función personalizada, por ejemplo, sqrt_fpu basada en la estándar - Ejemplo 2.



Ejemplo 2: cálculo de una raíz entera con el algoritmo sqrt_fpu



uint16_t sqrt_fpu ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    double f_rslt = sqrt( ( double ) L );
    uint32_t rslt = ( uint32_t ) f_rslt;

    if ( !( f_rslt - ( double ) rslt < .5 ) )
        rslt++;

    return ( uint16_t ) rslt;
}


Ventajas de sqrt_fpu:



  • código compacto;
  • se logra la precisión requerida.


Desventajas de sqrt_fpu:



  • pérdida de rendimiento debido a una llamada adicional y operaciones de punto flotante adicionales;
  • falta de potencial evidente para optimizar la velocidad de cálculo a nivel de usuario.


sqrt_fpu .



— - ().



-: , .



1. :



« , , .»

sqrt_odd — 3.



3: sqrt_odd



uint16_t sqrt_odd ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint16_t div = 1, rslt = 1;

    while ( 1 )
    {
        div += 2;

        if ( ( uint32_t ) div >= L )
            return rslt;

        L -= div, rslt++;
    }
}


,

.



sqrt_odd:



  • ;


sqrt_odd:



  • ;
  • ; , 10e4+ 150 — 1;
  • .


1: sqrt_odd



2. :



« »:

Rj = ( N / Ri + Ri ) / 2

sqrt_new — 4.



4: sqrt_new



uint16_t sqrt_new ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint32_t rslt, div;

    rslt = L;
    div = L / 2;

    while ( 1 )
    {
        div = ( L / div + div ) / 2;

        if ( rslt > div )
            rslt = div;
        else
            return ( uint16_t ) rslt;
    }
}


sqrt_new — sqrt_fpu ( 2).



sqrt_new:



  • ;
  • — sqrt_fpu;
  • ;


sqrt_new:



  • .


sqrt_new ( 2):



  • ;
  • .


2: sqtr_new (!)



(!) — 10e5+ 8 .



sqrt_new :



  • , , ( );
  • , -, ;
  • .


2. sqrt_evn ( 5).



sqrt_evn , , [ 0… 0xFFFFFFFF ].



sqrt_evn 2- 5- , sqrt_new ~40%.



[ 1… 10 000 000 ] sqtr_evn 2-3 .



sqrt_evn — 3.

3: sqtr_evn



, sqrt_evn — 5.

5: sqrt_evn



uint16_t sqrt_evn ( uint32_t L )
{
    if ( L < 2 )
        return ( uint16_t ) L;

    uint32_t div;
    uint32_t rslt;
    uint32_t temp;

    if ( L & 0xFFFF0000L )
        if ( L & 0xFF000000L )
            if ( L & 0xF0000000L )
                if ( L & 0xE0000000L )
                    div = 43771;
                else
                    div = 22250;
            else
                if ( L & 0x0C000000L )
                    div = 11310;
                else
                    div = 5749;
        else
            if ( L & 0x00F00000L )
                if ( L & 0x00C00000L )
                    div = 2923;
                else
                    div = 1486;
            else
                if ( L & 0x000C0000L )
                    div = 755;
                else
                    div = 384;
    else
        if ( L & 0xFF00L )
            if ( L & 0xF000L )
                if ( L & 0xC000L )
                    div = 195;
                else
                    div = 99;
            else
                if ( L & 0x0C00L )
                    div = 50;
                else
                    div = 25;
        else
            if ( L & 0xF0L )
                if ( L & 0x80L )
                    div = 13;
                else
                    div = 7;
            else
                div = 3;

    rslt = L;

    while ( 1 )
    {
        temp = L / div;
        temp += div;

        div = temp >> 1;
        div += temp & 1;

        if ( rslt > div )
            rslt = div;
        else
        {
            if ( L / rslt == rslt - 1 && L % rslt == 0 )
                rslt--;

            return ( uint16_t ) rslt;
        }
    }
}


«» — . 1 .



sqrt_evn , .

( 2).



— .



.

[ 3, 7, 13, 25 ] « ». (). .



— .





:



  • : STM32F0308-DISCO, MCU STM32F030R8T6
  • : STM32CubeIDE
  • : USB-UART PL2303HX


:



  • :
  • : CPU — 48 MHz, UART (RS485) — 9600 bit/s
  • : , Release
  • : MCU GCC Linker: Miscellaneous: -u _printf_float


sqrt_fpu, sqrt_new sqrt_evn.



100 000 3- — 4.

4:



.



— sqrt_fpu, . — .



, ( 4), .



( 5) .



5:



( 6) , 1 .

sqrt_fpu 19 531, sqrt_evn 147 059 ; sqrt_evn ~7,5 , sqrt_fpu.



6:





, , , .



Al mismo tiempo, la optimización algorítmica manual del código puede ser efectiva en la producción en masa de pequeñas IoT, debido al uso de modelos de microcontroladores de bajo costo, liberando espacio de tareas complejas para modelos más antiguos.



More articles:


All Articles