#include <iostream>
#include <limits>

template <typename T>
bool is_safely_multiplicable(T a, T b) {
  if (b == 0) return true;
  return a <= (std::numeric_limits<T>::max() / b);
}

uint64_t sqrt_int(uint64_t x) {
  if (x == 0) return 0;
  uint64_t a = 1, b = x, c;
  while (b - a > 1) {
    c = (b - a) / 2 + a;
    if (is_safely_multiplicable(c, c) && x >= c * c) a = c;
    else b = c;
  }
  return a;
}

bool is_square_number(uint64_t x) {
  uint64_t rt_x = sqrt_int(x);
  return rt_x * rt_x == x;
}

int main()
{
	for (
		uint64_t i = sqrt_int(std::numeric_limits<uint64_t>::max());
		i > 0;
		i >>= 1
	) {
		std::cout << i << " * " << i  << " = " << i * i << ", " << sqrt_int(i * i) << std::endl;
	}
	
	return 0;
}