Корни разные нужны, корни разные важны

Вместо вступления

Прежде всего хочется выразить признательность всем, кто откликнулся на первую статью об оптимизации кода на языке C/C++ на примере функции для вычисления квадратного корня из целого с округлением до ближайшего целого. Благодаря экспертному вниманию была исправлена опечатка в тексте; копилка эффективных алгоритмов пополнилась.

Интересен алгоритм sqrxi32 от @Sdima1357 — Пример 1, далее для краткости именуемый как «_i32». Алгоритм «_i32» безусловно выполняет главное условие задачи — «округление до ближайшего целого» — на всём множестве значений аргумента [ 0 .. 0xFFFFFFFF ], при этом показывает высокую производительность.

Пример 1: Вычисление квадратного корня из целого с округлением до ближайшего целого.

uint16_t sqrxi32( uint32_t y )
{
        if ( y == 1 )
                return 1;

        uint32_t xh = y > 0x10000ul ? 0x10000ul : y;
        uint32_t xl = 0;
        uint32_t xc;

        for ( int k = 0; k < 16; k++ )
        {
                xc = ( xh + xl ) >> 1ul;
                if ( xc * xc - xc >= y )
                {
                        xh = xc;
                }
                else
                {
                        xl = xc;
                }
        }
        return ( xh + xl ) >> 1ul;
}

Другое хорошее качество алгоритма «_i32» — предсказуемость по времени. Время работы «_i32» постоянно в отличие от алгоритма «_evn», потребляющего машинное время пропорционально модулю аргумента.

О чём этот текст

Наблюдение комплексного влияния параметров сборки и целевой аппаратной платформы на итоговую производительность, применительно к одному и тому же исходному коду.

Исходный код содержит решение одной задачи разными алгоритмами.

Анализ результатов наблюдений за рамками настоящей публикации.

Условия и допуски

Для сокращение текста принимаем:

• аппаратных платформ для тестов — 3 платформы;

• вариантов оптимизации сборки — 3 значения

Для сборки двоичного кода применяем:

• Одну единицу компиляции теста (файл main.c)

• Компиляцию в моно-поточный исполняемый файл

• Единую сборочную среду: CubeIDE (она же Eclipce CDT)

• Стандартные настройки профиля сборки RELEASE в среде CubeIDE

• Единый диалект компилятора: «ISO C11 + gnu extensions» (-std=gnu11)

• Применительно к микроконтроллерам:

  • CubeMX — default settings, +48MHz, +USART1, +HAL;

  • Runtime lib: Reduced C ( --spec=nano.specs );

  • Use float with printf from new lib nano ( -u _printf_float );

Таблица 1: Варианты сборки исполняемого кода

Таблица 2: Общие характеристики аппаратных платформ

Таблица 3: Технические характеристики аппаратных платформ

Тестовый набор содержит некоторые алгоритмы из предыдущей статьи и комментариев к ней.

Для оценки FPU платформы «M4» в тестовый набор добавлена функция sqrt_fps, решающая вычислительную задачу с применением коротких действительных (float), именуемая далее «_fps» (Float Point Short) — Пример 2.

Пример 2: Квадратный корень из целого с точностью float

uint16_t sqrt_fps( uint32_t number )
{
        if ( number < 2 )
                return (uint16_t) number;

        float f_rslt = sqrtf( number );
        uint32_t rslt = (uint32_t) f_rslt;

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

        return (uint16_t) rslt;
}

Функция «_fps» работает без ошибок с аргументом менее 22-х бит, что соответствует десятичному порядку 1+E5 — Иллюстрация 1.

Иллюстрация 1: Ошибки функции "_fps" на порядках 1+E6+

Для всех наблюдаемых алгоритмов ограничиваем диапазон аргумента множеством значений
[0 .. 1+E5].

Таблица 4: Список наблюдаемых алгоритмов

Основная единица измерения — производительность, среднее число циклических вызовов функции за одну миллисекунду.

Относительная производительность платформ

Ожидаемо, производительность платформы «x86» выше производительности платформы «ARM Cortex» безотносительно характера оптимизации сборки. Последнее демонстрирует левая часть графика — Иллюстрация 2.

Иллюстрация 2: Относительная производительность аппаратных платформ

На левой части графика по оси Y отображается среднее время последовательного выполнения всех тестов (Таблица 4), измеренное в секундах. На оси X — аппаратные платформы.

Чем ниже высота столбика на левой части графика (Иллюстрация 2), тем выше скорость работы, тем лучше производительность соответствующей аппаратной платформы.

График каждой платформы, в свою очередь, представлен тремя столбцами, демонстрирующими зависимость производительности от варианта оптимизации сборки: -O0, -Os, -O3.

Правая часть графика (Иллюстрация 2) показывает относительный прирост производительности у каждой аппаратной платформы в зависимости от варианта оптимизации сборки: -O0, -Os, -O3.

Производительность 100% демонстрирует двоичный код, собранный без оптимизации ( -O0 ). Это базовая производительность платформы.

Чем выше высота столбика относительно базовой производительности ( ‑O0 ) в правой части графика, тем лучше оптимизационные возможности программно-аппаратной платформы.

Наблюдаем наибольший прирост производительности от оптимизации на этапе сборки на платформе «M4».

Платформа x86

На графике (Иллюстрация 3) по оси Y отображается число цикличных вызовов наблюдаемых функций за одну миллисекунду. На оси X — наблюдаемые функции (Таблица 4).

Чем выше на графике столбики, тем лучше производительность.

Цветом на оси X обозначен способ оптимизации на этапе сборки. Соответствие цвета и характера оптимизации отражает легенда.

Иллюстрация 3: Производительность алгоритмов на платформе x86

Платформа «x86» максимально раскрывает преимущества алгоритмов с плавающей точкой перед целочисленными.

Заслуживает отдельного внимания часть графика в оранжевом контуре.

Производительность кода без оптимизации ( ‑O0 ) лучше на 39% для алгоритма «_fpu» ( ‑Os ) и на 16% для алгоритма «_fps» ( ‑O3 ). Другими словами, любая оптимизация на этапе сборки снижает производительность платформы «x86» на действительных числах.

В то же время, целочисленные алгоритмы показывают ожидаемый прирост производительности при сборке с параметрами -O3 и -Os.

Платформа M4

Платформа «M4» демонстрирует предсказуемый результат (Иллюстрация 4).

Иллюстрация 4: Производительность алгоритмов на платформе M4

Модуль с плавающей точкой «M4» даёт ожидаемый прирост производительности для алгоритма «_fps», основанного на коротком действительном — float.

Последнее подтверждается результатом сравнения производительности алгоритмов при отключенном модуле FPU на платформе «M4» — Иллюстрация 5.

Наблюдая графики помним, что точность вычислений алгоритма «_fps» гарантируется в диапазоном 1+E5 (см. Иллюстрация 1) без относительно того, включен ли модуль FPU на «M4» или нет.

Иллюстрация 5: Производительность алгоритмов на платформе M4 без FPU

Платформа M0

Результаты платформы «M0» похожи на результаты платформы «M4» без FPU (Иллюстрация 5), только медленнее — Иллюстрация 6.

Заметим, тактовая частота при тестировании устанавливалась одинаковой и для «M4», и для «M0» — 48 MHz. Однако, производительность «M0» хуже в два с лишним раза, чем «M4», в условиях равенства прочих характеристик.

Иллюстрация 6: Производительность алгоритмов на платформе M0

Алгоритм «_fps» на платформе «M0» ожидаемо опережает в два раза алгоритм «_fpu».

Целочисленные алгоритмы опережают алгоритмы с плавающей точкой.

По странному стечению обстоятельств в заключительном графике (Иллюстрация 6) снова есть место для оранжевого контура.

При сборке без оптимизации ( ‑O0 ) алгоритм «_evn» быстрее алгоритма «_i32». И алгоритм «_evn» медленнее, чем «_i32», если сборка проводится с оптимизацией.

Снова наблюдается относительное снижение производительности от оптимизации на этапе сборки. Заметим, у целочисленных алгоритмов на платформах «M4» и «x86» подобного эффекта нет.

Вместо заключения

Производительность программы зависит от многих причин.

Оптимизация на этапе сборки способна ухудшать производительность, замедлять программу, что демонстрируют экспериментальные данные в оранжевых контурах выше (Иллюстрация 3 и Иллюстрация 6).

Цена аппаратной платформы безусловно повышает производительность программы безотносительно качества исходного кода и эффективности компилятора.

Общего правила, как создавать эффективные программы, нет. Задача оптимизации и профилирования решается индивидуально в каждом конкретном случае.

Приложение 1. Порядок тестирования платформы x86

1. Создать в среде CubeIDE (Eclipse CDT) проект C штатным способом

2. Написать текст программы — Пример 3

3. Добавить в проект файл sqrt_cmp.h — Пример 6

4. Осуществить сборку и запуск программы:

   1. штатными средствами IDE;

   2. или из командной строки — Пример 4

5. Меняя вид оптимизации ( -O0, -O3, -Os ) наблюдать результат.

Пример 3: Исходный текст программы x86 — main.c

#include "sqrt_cmp.h"

int main( void )
{
        main_Of_SqrtComp();
        return 0;
}

Пример 4 Запуск теста на платформе x86 из терминала

gcc main.c -o main -I. -Wall -lm -std=gnu11 -O3 && ./main

Запуск теста из терминала платформы «x86» предполагает, что файлы main.c и sqrt_cmp.h располагаются в одном каталоге, и этот каталог выбран рабочим (pwd).

Иллюстрация 7: Запуск теста из терминала «x86»

Приложение 2. Порядок тестирования платформы STM32

1. Создать в среде CubeIDE проект STM32 штатным способом (CubeMX)

2. Добавить файл sqrt_cmp.h в проект STM32 — Пример 6

3. Включить sqrt_cmp.h в файл main.c — Пример 5

4. Осуществить сборку и запуск программы штатными средствами IDE

5. Меняя вид оптимизации ( -O0, -O3, -Os ) наблюдать результат

Пример 5: Исходный текст для STM32 (с пропусками < ... >) — main.c

< … >
/* Private includes ----------------------------------------------------------*/
/* USER CODE BEGIN Includes */
#include "sqrt_cmp.h"
/* USER CODE END Includes */
< … >
/**
  * @brief  The application entry point.
  * @retval int
  */
int main(void)
{
< … >
  /* Infinite loop */
  /* USER CODE BEGIN WHILE */
  main_Of_SqrtComp();
  while (1)
  {
    /* USER CODE END WHILE */
    /* USER CODE BEGIN 3 */
  }
  /* USER CODE END 3 */

Приложение 3. Порядок тестирования других алгоритмов и платформ

Сборка теста для других платформ проводится по аналогии.

Для отличных от упомянутых выше аппаратных платформ (Таблица 3), вероятно, потребуется косметическая модификация файла «sqrt_cmp.h».

Пример 6: Содержание файла sqrt_cmp.h

/******************************************************************************
 * File: sqrt_cmp.h Created on 5 авг. 2020 г.
 * CC0 1.0 Universal (CC0 1.0)
 * Creative Commons Public Domain Dedication
 * No Copyright
 *
 * TAB Size .EQ 4
 ********************************************************************************/

#ifndef __SQRT_CMP_H
#define __SQRT_CMP_H

#include        <math.h>
#include        <stdio.h>
#include        <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

/******************************************************************************
 * Interface of the entry point for all sqrt tests
 ******************************************************************************/

void main_Of_SqrtComp();

/******************************************************************************
 * test case selection: TEST_SET
 * select one of the test suite via a comment.
 ******************************************************************************/

#define TEST_SET                        TEST_ALL
//#define TEST_SET                      TEST_ROUNDING
//#define TEST_SET                      TEST_PERFORMANCE

/******************************************************************************
 * Interfaces of test functions.
 * See implementation of them at the end of this file.
 ******************************************************************************/

typedef uint16_t (*sqrt_func)( uint32_t number );

uint16_t sqrt_fpu( uint32_t number );   // floating point function from article
uint16_t sqrt_evn( uint32_t number );   // integer function from article

uint16_t sqrxi32( uint32_t y );                 // integer function from comment by

uint16_t sqrt_fps( uint32_t number );   // optimized floating point function for Cortex M4

                                                                                // <-- insert interface of your function here

/******************************************************************************
 * Set to variable named as 'round_test_func' below
 * to the alias of one of the functions above.
 * The NULL will select last function in comp_list[]
 ******************************************************************************/

sqrt_func round_test_func = sqrt_fps;   // specific instance for the rounding test
//sqrt_func round_test_func = sqrxi32;  // specific instance for the rounding test
//sqrt_func round_test_func = sqrt_evn; // specific instance for the rounding test

//sqrt_func round_test_func = NULL;             // last function in comp_list[]

/******************************************************************************
 * The array of test functions for competing routines is called comp_list[].
 * Adding a new function to the test:
 - copy the implementation of the new function to the end of this file;
 - declare the function interface at the beginning of this file;
 - add the alias and declaration of the new function to
 end of array named comp_list[].
 ******************************************************************************/

// @formatter:off

typedef struct
{
        sqrt_func       fsqrt;
        char *          alias;
} SCompFunc;

SCompFunc comp_list[] = // competition list
{
        { sqrt_fpu, "_fpu" },
        { sqrt_fps, "_fps" },
        { sqrt_evn, "_evn" },
        { sqrxi32,  "_i32" }
                                                        // <-- insert your function name & alias here
};

/* @formatter:on */

/******************************************************************************
 * Platform-independent definitions
 ******************************************************************************/

#define PUT_FORMAT_MSG(f_, ...) { \
                                sprintf( (char *)s_buf, (char *)f_, ##__VA_ARGS__ ); \
                                PUT_MSG( (char *)s_buf ); }

#define MS_PER_SEC      1000
#define US_PER_SEC      ( MS_PER_SEC * MS_PER_SEC )

#define ARRAY_SIZE(a) (sizeof a / sizeof *a)    // size of static array at runtime

#define SIRV(f) if ( f ) ;                                              // suppress Ignore Return Value warning

/******************************************************************************
 * Platform-specific defines
 ******************************************************************************/

#if defined( USE_HAL_DRIVER )   // STM32 ARM Cortex platform

#       include <string.h>
#       include "main.h"

        //*****************************************************************************
        // Platform-specific defines for the helper functions

#       define SCALE_RATE               1       // must be .GE than 1

#       define X_CLOCK                  HAL_GetTick()
#       define X_DELAY( ms )    HAL_Delay( ms )

        //*****************************************************************************
        // Platform-specific defines for the terminal output

#       define USART_HANDLE             huart1  // set valid USART handler alias here defined by the config of MCU
#       define USART_TIMEOUT    150             // max timeout for HAL_UART_Transmit

extern UART_HandleTypeDef USART_HANDLE;
extern HAL_StatusTypeDef HAL_UART_Transmit ( UART_HandleTypeDef *huart, uint8_t *pData, uint16_t Size, uint32_t Timeout );

#       define PUT_MSG( msg ) \
                HAL_UART_Transmit( &USART_HANDLE, (uint8_t *)msg, strlen( (char *)msg ), USART_TIMEOUT )

#       define CPU_CLOCK_MHz    ( SystemCoreClock / US_PER_SEC )        // CPU CLK in MHz

#       if defined( STM32F0 )
#               define  CPU_ID ( "STM32 ARM Cortex M0" )
#       elif defined ( STM32F3 )
#               define  CPU_ID ( "STM32 ARM Cortex M4" )
#       else
#               define  CPU_ID ( "Maybe STM32 ARM Cortex" )
#       endif

#       define PUT_SYS_INFO     PUT_FORMAT_MSG( " %s @ "fdU()" MHz\n", CPU_ID, CPU_CLOCK_MHz )

#else   // #if defined( USE_HAL_DRIVER  )

#               include <time.h>
#               include <stdlib.h>

        //*****************************************************************************
        // Platform-specific defines for the helper functions

#       define SCALE_RATE               100             // must be .GE than 1

#       define X_CLOCK                  (uint32_t) x_clock()
#       define X_DELAY( ms )    x_delay( ms )

uint32_t x_clock()
{
        uint64_t result = (uint64_t) clock();
        result *= MS_PER_SEC;
        result /= CLOCKS_PER_SEC;
        return (uint32_t) result;
}

void x_delay( uint32_t ms )
{
        uint64_t tm = x_clock();
        while ( ( x_clock() - tm ) < ms )
                ;
}

        //*****************************************************************************
        // Platform-specific defines for the terminal output

#       define PUT_MSG( msg ) \
                printf( "%s", (char *)msg ), fflush ( stdout );

#       if defined( __unix__ )          // anybody other platform for gcc

#               define PUT_SYS_INFO     SIRV( system( "cat /proc/cpuinfo | grep 'model name' | head -1 | sed s/'model name\t:'/''/" ) )

#       else

#               define PUT_SYS_INFO     PUT_MSG( "Undefined System & CPU" )

#       endif   // #    if defined( __unix__ )  // anybody other platform for gcc

#endif          // #if defined( USE_HAL_DRIVER  )

#if  ( __WORDSIZE == 64 )

#       define fdI(s)   "%" #s "d"
#       define fdU(s)   "%" #s "u"
#       define fdX(s)   "%" #s "x"

#else   // let's say __WORDSIZE == 32

#       define fdI(s)   "%" #s "ld"
#       define fdU(s)   "%" #s "lu"
#       define fdX(s)   "%" #s "lx"

#endif  // #if ( __WORDSIZE == 64 )

#if defined ( DEBUG ) || defined ( _DEBUG ) // chk build mode of CubeIDE

#       define  BUILD_MODE      "DEBUG"

#else // Maybe Release

#       define  BUILD_MODE      "RELEASE"

#endif  // #if defined ( DEBUG ) || defined ( _DEBUG )

/******************************************************************************
 * the helper data with testing ranges
 ******************************************************************************/

// @formatter:off

typedef struct
{
        uint32_t        start;
        uint32_t        stop;
        uint32_t        repeat;
} STestRange;

STestRange      test_rngs[] =
{
        { 0, 1000, 100 * SCALE_RATE },
        { 0, 10000, 10 * SCALE_RATE },
        { 0, 100000, 1 * SCALE_RATE }
};

uint32_t test_results[ARRAY_SIZE( test_rngs )][ARRAY_SIZE( comp_list ) + 1];

#define MSG_BUFF_SIZE   512

uint8_t s_buf[MSG_BUFF_SIZE];   // buffer for a terminal output

/* @formatter:on */

/******************************************************************************
 * Test sets definitions. Do not change it.
 ******************************************************************************/

#define TEST_ROUNDING           1
#define TEST_PERFORMANCE        2
#define TEST_ALL                        ( TEST_ROUNDING | TEST_PERFORMANCE )

#ifndef TEST_SET
#       define  TEST_SET        TEST_ALL
#endif

#define HI_ROUND_TEST_RANGE_END         0x007FFFFFUL
#define HI_ROUND_TEST_RANGE_START       ( HI_ROUND_TEST_RANGE_END >> 4 )

/******************************************************************************
 * Interface of helper functions
 ******************************************************************************/

void main_Header();
void testRounding();
void testPerformance();

/******************************************************************************
 * Implementation of the entry point for all sqrt tests
 ******************************************************************************/

void main_Of_SqrtComp()
{

        X_DELAY( MS_PER_SEC / 2 );      // suppress the output of a previous instance
                                                                // while the new instance is loading into the MCU

        uint32_t start_time = X_CLOCK;

        main_Header();

        // checking normal and extended ranges for rounding
        if ( TEST_SET & TEST_ROUNDING )
                testRounding();

        // checking normal ranges on execution time
        if ( TEST_SET & TEST_PERFORMANCE )
                testPerformance();

        uint32_t test_time = X_CLOCK - start_time;

        uint32_t test_m = ( test_time / MS_PER_SEC ) / 60;
        uint32_t test_s = ( test_time / MS_PER_SEC ) % 60;
        uint32_t test_ms = test_time % MS_PER_SEC;

        PUT_FORMAT_MSG( "\ndone, spent time: "fdU()" m, "fdU()"."fdU()" s\n", test_m, test_s, test_ms );
}

/******************************************************************************
 * Implementation of the helper functions
 ******************************************************************************/

void main_Header()
{

        PUT_MSG( "\n\n**********************************************************\n" );
        PUT_SYS_INFO;
        PUT_FORMAT_MSG( "*********** %s, built at %s\n", BUILD_MODE, __TIME__ );
}

void testPerformance()
{
        uint32_t i_func, i_rpt, i_rng;
        uint32_t number, first, second, diff;
        uint64_t temp;

        PUT_MSG( "----------+ Performance test" );

        for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )
        {
                PUT_MSG( "\n" );
                PUT_FORMAT_MSG( "test range:["fdU()".."fdU()"], repeat="fdU()"\n", test_rngs[i_rng].start, test_rngs[i_rng].stop,
                                test_rngs[i_rng].repeat );

                test_results[i_rng][0] = test_rngs[i_rng].stop;

                for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ )
                {
                        PUT_FORMAT_MSG( "%s ... ", comp_list[i_func].alias );

                        first = X_CLOCK;

                        for ( i_rpt = 0; i_rpt < test_rngs[i_rng].repeat; i_rpt++ )
                                for ( number = test_rngs[i_rng].start; number < test_rngs[i_rng].stop; number++ )
                                        comp_list[i_func].fsqrt( number );

                        second = X_CLOCK;

                        diff = second - first;

                        temp = ( test_rngs[i_rng].stop - test_rngs[i_rng].start ) * test_rngs[i_rng].repeat;
                        test_results[i_rng][i_func + 1] = (uint32_t) ( temp / diff );

                        if ( i_func < ARRAY_SIZE( comp_list ) - 1 )
                                PUT_MSG( ", " );
                }
        }

        // small report
        PUT_FORMAT_MSG( "\n----------+ Report: sqrt`s calls per ms\n%10s", "range" );

        for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ )
                PUT_FORMAT_MSG( "%10s", comp_list[i_func].alias );

        for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )
        {
                PUT_MSG( "\n" );
                for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ) + 1; i_func++ )
                        PUT_FORMAT_MSG( fdU( 10 ), test_results[i_rng][i_func] );
        }

        PUT_FORMAT_MSG( "\n----------+\n%10s", "average" );

        for ( i_func = 0; i_func < ARRAY_SIZE( comp_list ); i_func++ )
        {
                temp = 0;

                for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )
                        temp += test_results[i_rng][i_func + 1];

                temp /= ARRAY_SIZE( test_rngs );

                PUT_FORMAT_MSG( fdU( 10 ), (uint32_t)temp );
        }
}

void testRoundingFunction( uint32_t start, uint32_t finish, sqrt_func psqrt, char *fname );

void testRounding()
{
        uint16_t i_rng;
        uint16_t f_rng;

        PUT_MSG( "----------+ Rounding test\n" );

        // checking the existence for the test function
        for ( f_rng = 0; f_rng < ARRAY_SIZE( comp_list ); f_rng++ )
                if ( comp_list[f_rng].fsqrt == round_test_func )
                        break;

        if ( !( f_rng < ARRAY_SIZE( comp_list ) ) )
        {
                f_rng = ARRAY_SIZE( comp_list ) - 1;
                PUT_FORMAT_MSG( "Value of 'round_test_func' not found.\n" );
        }

        PUT_FORMAT_MSG( "Function '%s' is tested for rounding.\n", comp_list[f_rng].alias );

        // checking standard ranges
        for ( i_rng = 0; i_rng < ARRAY_SIZE( test_rngs ); i_rng++ )
                testRoundingFunction( test_rngs[i_rng].start, test_rngs[i_rng].stop, comp_list[f_rng].fsqrt, comp_list[f_rng].alias );

        // checking extended range
        testRoundingFunction( HI_ROUND_TEST_RANGE_START, HI_ROUND_TEST_RANGE_END, comp_list[f_rng].fsqrt, comp_list[f_rng].alias );
}

void turn_the_fan( uint32_t ms );

void testRoundingFunction( uint32_t start, uint32_t finish, sqrt_func psqrt, char *fname )
{
        uint32_t rf, ri;
        uint32_t n, c = 0;

        PUT_FORMAT_MSG( "test range:["fdU( 10 )".."fdU( 10 )"] ... ", start, finish );

        for ( n = start; n < finish; n++ )
        {
                rf = sqrt_fpu( n );
                ri = ( *psqrt )( n );
                if ( rf != ri )
                {
                        if ( c++ > 3 )
                        {
                                PUT_FORMAT_MSG( "\b\n(!)too many mistakes in '%s', ", fname );
                                break;
                        }
                        else
                        {
                                double d = sqrt( (double) n );
                                PUT_FORMAT_MSG( "\b\n%s("fdU( 10 )")="fdU()" != "fdU(), fname, n, ri, rf );
                                PUT_FORMAT_MSG( " (real value is %.6lf)", d );
                        }
                }
                turn_the_fan( MS_PER_SEC );
        }

        if ( !c )
        {
                PUT_FORMAT_MSG( "\b done.\n" );
        }
        else
        {
                PUT_FORMAT_MSG( "test failed.\n" );
        }
}

void turn_the_fan( uint32_t ms )
{
        static char ca[] = "|/-\\";
        static uint32_t cs = ARRAY_SIZE(ca) - 1;
        static uint32_t cn = 0;

        static uint32_t at = 0;

        uint32_t ct = X_CLOCK;
        if ( ct - at > ms )
        {
                at = ct;
                PUT_FORMAT_MSG( "\b%c", ca[cn++ % cs] );
        }
}

/******************************************************************************
 * Implementation of the sqrt functions
 ******************************************************************************/

// floating point arg & result with double
uint16_t sqrt_fpu( uint32_t number )
{
        if ( number < 2 )
                return (uint16_t) number;

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

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

        return (uint16_t) rslt;
}

// floating point arg & result with float
uint16_t sqrt_fps( uint32_t number )
{
        if ( number < 2 )
                return (uint16_t) number;

        float f_rslt = sqrtf( number );
        uint32_t rslt = (uint32_t) f_rslt;

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

        return (uint16_t) rslt;
}

// unsigned integer arg & result

// @formatter:off
uint16_t sqrt_evn ( uint32_t number )
{
        if ( number < 2 )
                return ( uint16_t ) number;

        uint32_t temp;
        uint32_t div;
        uint32_t rslt;

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

        rslt = number;

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

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

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

                        return ( uint16_t ) rslt;
                }
        }
}
/* @formatter:on */

// unsigned integer arg & result
uint16_t sqrxi32( uint32_t y )
{

        if ( y == 1 )
                return 1;

        uint32_t xh = y > 0x10000ul ? 0x10000ul : y;
        uint32_t xl = 0;
        uint32_t xc;

        for ( int k = 0; k < 16; k++ )
        {
                xc = ( xh + xl ) >> 1ul;
                if ( xc * xc - xc >= y )
                {
                        xh = xc;
                }
                else
                {
                        xl = xc;
                }
        }
        return ( xh + xl ) >> 1ul;
}

// <-- insert implementation of your function sqrt here

#ifdef __cplusplus
}
#endif

#endif // __SQRT_CMP_H

Adblock test (Why?)