stm32. Nós olhamos para a raiz

Em vez de apresentar

O artigo contém um exemplo de otimização manual de uma seção crítica de um programa aplicativo em relação a microcontroladores stm32 de orçamento, o que aumenta o desempenho 5 vezes ou mais em comparação com uma função de biblioteca.

A extração de raiz quadrada é freqüentemente usada em aplicativos. A função sqrt está incluída na biblioteca C padrão e opera em números reais:

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

Os microcontroladores funcionam principalmente com números inteiros; eles geralmente não têm registros para números reais.

Na prática, além da perda de velocidade computacional em várias transformações "inteiro <=> real" , a precisão também é perdida - Exemplo 1.

Exemplo 1: perda de precisão em conversões para frente e para trá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%

Formulação do problema

Aumente a precisão dos cálculos sqrt arredondando para o número inteiro mais próximo.

Se possível, aumente a produtividade.

A solução do problema

Crie uma função personalizada, por exemplo, sqrt_fpu com base na função padrão - Exemplo 2.

Exemplo 2: Calculando uma raiz inteira com o 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;
} 

Vantagens do Sqrt_fpu:

• código compacto;
• a precisão necessária é alcançada.

Desvantagens de sqrt_fpu:

• perda de desempenho devido a uma chamada extra e operações adicionais de ponto flutuante;
• falta de potencial óbvio para otimizar a velocidade de computação no nível do usuário.

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:

, , , .

Ao mesmo tempo, a otimização de código algorítmico manual pode ser eficaz na produção em massa de pequenas IoT, devido ao uso de modelos de microcontroladores de baixo custo, liberando espaço de tarefas complexas para modelos mais antigos.