#include <iostream>
#include <random>
#include <functional>
#include <chrono>
#include <limits>
#include <cmath>

unsigned sqrtull(unsigned long long x) {
	if (x == 0) return 0;
	unsigned ans = 0;
	for (int i = ((std::numeric_limits<long long>::digits - __builtin_clzll(x)) & ~1);
		i >= 0; i -= 2) {
		ans <<= 1;
		if ((ans | 1) * (unsigned long long)(ans | 1) <= (x >> i)) ans |= 1;
	}
	return ans;
}

unsigned sqrtu_exact(unsigned x) {
	if (x == 0) return 0;
	unsigned ret = 0;
	for (int i = ((std::numeric_limits<int>::digits - __builtin_clz(x)) & ~1);
		i >= 0; i -= 2) {
		ret <<= 1;
		if ((ret | 1) * (ret | 1) <= (x >> i)) ret |= 1;
	}
	return ret;
}

unsigned sqrtu_usual(unsigned x) {
	unsigned ret = (unsigned)sqrt(x);
	return ret;
}

unsigned D[1000'0000];
unsigned D1[1000'0000];
unsigned D2[1000'0000];

int main() {
	using namespace std;

	// 32, 64
	cout << numeric_limits<unsigned>::digits << ", "
		<< numeric_limits<unsigned long long>::digits << endl;
	for (int i = 10; i >= 0; --i) cout << i << ": " << sqrtu_exact(i) << endl;

	mt19937 rnd;
	for (int i = 0; i < 1000'0000; ++i) D[i] = rnd();
	{
		const auto start = chrono::system_clock::now();
		for (int i = 0; i < 1000'0000; ++i) D1[i] = sqrtu_exact(D[i]);
		const auto end = chrono::system_clock::now();
		const chrono::duration<double> sec = end - start;
		cout << "Exact: " << sec.count() << "s\n";
	}
	{
		const auto start = chrono::system_clock::now();
		for (int i = 0; i < 1000'0000; ++i) D2[i] = sqrtu_usual(D[i]);
		const auto end = chrono::system_clock::now();
		const chrono::duration<double> sec = end - start;
		cout << "Usual: " << sec.count() << "s\n";
	}

	for (int i = 0; i < 1000'0000; ++i) {
		if (D1[i] != D2[i]) {
			cout << "Wrong: " << D[i] << ' ' << D1[i] << ' ' << D2[i] << endl;
			return 0;
		}
	}

	cout << "Correct!" << endl;
	return 0;
}

/*
Exact: 0.354943s
Usual: 0.0570476s
Correct!
*/