/******************************************************************************

                            Online C Compiler.
                Code, Compile, Run and Debug C program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

uint32_t int_sqrt(uint32_t x) {
    if (x < 2) return x;

    uint32_t left = 0, right = x / 2 + 1;
    uint32_t mid, square;

    while (left <= right) {
        mid = (left + right) / 2;
        square = mid * mid;

        if (square == x) {
            return mid;
        } else if (square < x) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return right;
}

uint32_t int_sqrt2(uint32_t x) {
    if (x < 2) return x;

    uint32_t res = x;
    uint32_t temp;

    // Метод Ньютона
    while (1) {
        temp = (res + x / res) / 2;
        if (temp >= res) {
            break;
        }
        res = temp;
    }

    return res;
}


uint32_t int_sqrt3(uint32_t x) {
    if (x < 2) return x;

    // Начальное приближение: половина x
    uint32_t res = x >> 1;

    // Если x меньше 4, нужно вернуть 1
    if (res == 0) return 1;

    // Метод Ньютона с оптимизированным начальным приближением
    while (1) {
        uint32_t temp = (res + x / res) >> 1;
        if (temp >= res) {
            break;
        }
        res = temp;
    }

    return res;
}

uint32_t sqrtInt32(uint32_t n) {
	int32_t ret = 0;
	int32_t s;
	int32_t ret_sq = -n - 1;
	for (s = 30; s >= 0; s -= 2) {
		int32_t b;
		ret += ret;
		b = ret_sq + ((2 * ret + 1) << s);
		if (b < 0) {
			ret_sq = b;
			ret++;
		}
	}
	return ret;
}

uint32_t int_sqrt4(uint32_t x) {
    if (x < 2) return x;

    // Магическое начальное приближение
    uint32_t res = x;
    if (x > 0xFFFF) res = (x >> 16) + 1;
    else if (x > 0xFF) res = (x >> 8) + 1;
    else if (x > 0xF) res = (x >> 4) + 1;
    else res = (x >> 1) + 1;

    // Одна итерация Ньютона
    res = (res + x / res) >> 1;

    // Вторая итерация (можно убрать, если нужна супер-скорость, но точность будет ниже)
    res = (res + x / res) >> 1;

    return res;
}

int main()
{
    
    uint16_t i,j;
    uint32_t sqrt, res;
    for(j=0;j<6000;j++)
    for(i=0;i<4095;i++){
        sqrt = i;
        sqrt = sqrt * sqrt;
        res = sqrtInt32(sqrt);
        if(i != res){
            
            printf("error %d res %d\n\r",i,res);
            j=1000;
            break;
        }
    }
    
    
    
    
    printf("Hello World");

    return 0;
}