fork(2) download
copy 
  1. #include <iostream>
  2. #include <limits>
  3.  
  4. template <typename T>
  5. bool is_safely_multiplicable(T a, T b) {
  6.   if (b == 0) return true;
  7.   return a <= (std::numeric_limits<T>::max() / b);
  8. }
  9.  
  10. uint64_t sqrt_int(uint64_t x) {
  11.   if (x == 0) return 0;
  12.   uint64_t a = 1, b = x, c;
  13.   while (b - a > 1) {
  14.     c = (b - a) / 2 + a;
  15.     if (is_safely_multiplicable(c, c) && x >= c * c) a = c;
  16.     else b = c;
  17.   }
  18.   return a;
  19. }
  20.  
  21. bool is_square_number(uint64_t x) {
  22.   uint64_t rt_x = sqrt_int(x);
  23.   return rt_x * rt_x == x;
  24. }
  25.  
  26. int main()
  27. {
  28. 	for (
  29. 		uint64_t i = sqrt_int(std::numeric_limits<uint64_t>::max());
  30. 		i > 0;
  31. 		i >>= 1
  32. 	) {
  33. 		std::cout << i << " * " << i  << " = " << i * i << ", " << sqrt_int(i * i) << std::endl;
  34. 	}
  35.  
  36. 	return 0;
  37. }
Success #stdin #stdout 0s 15232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4294967295 * 4294967295 = 18446744065119617025, 4294967295
2147483647 * 2147483647 = 4611686014132420609, 2147483647
1073741823 * 1073741823 = 1152921502459363329, 1073741823
536870911 * 536870911 = 288230375077969921, 536870911
268435455 * 268435455 = 72057593501057025, 268435455
134217727 * 134217727 = 18014398241046529, 134217727
67108863 * 67108863 = 4503599493152769, 67108863
33554431 * 33554431 = 1125899839733761, 33554431
16777215 * 16777215 = 281474943156225, 16777215
8388607 * 8388607 = 70368727400449, 8388607
4194303 * 4194303 = 17592177655809, 4194303
2097151 * 2097151 = 4398042316801, 2097151
1048575 * 1048575 = 1099509530625, 1048575
524287 * 524287 = 274876858369, 524287
262143 * 262143 = 68718952449, 262143
131071 * 131071 = 17179607041, 131071
65535 * 65535 = 4294836225, 65535
32767 * 32767 = 1073676289, 32767
16383 * 16383 = 268402689, 16383
8191 * 8191 = 67092481, 8191
4095 * 4095 = 16769025, 4095
2047 * 2047 = 4190209, 2047
1023 * 1023 = 1046529, 1023
511 * 511 = 261121, 511
255 * 255 = 65025, 255
127 * 127 = 16129, 127
63 * 63 = 3969, 63
31 * 31 = 961, 31
15 * 15 = 225, 15
7 * 7 = 49, 7
3 * 3 = 9, 3
1 * 1 = 1, 1
https://ideone.com/xr1vcE
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!