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

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

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

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

Пример 1: Квадратный корень из целого с округлением до ближайшего целого — «_i32».

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 — «_fps»

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-х бит, что соответствует десятичному порядку 1E+5 — Иллюстрация 1.

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

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

Таблица 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» гарантируется в диапазоном 1E+5 (см. Иллюстрация 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