fork download
copy 
  1. /******************************************************************************
  2.  
  3.                             Online C Compiler.
  4.                 Code, Compile, Run and Debug C program online.
  5. Write your code in this editor and press "Run" button to compile and execute it.
  6.  
  7. *******************************************************************************/
  8.  
  9. #include <stdio.h>
  10. #include "stdint.h"
  11.  
  12. uint32_t int_sqrt(uint32_t x) {
  13.     if (x < 2) return x;
  14.  
  15.     uint32_t left = 0, right = x / 2 + 1;
  16.     uint32_t mid, square;
  17.  
  18.     while (left <= right) {
  19.         mid = (left + right) / 2;
  20.         square = mid * mid;
  21.  
  22.         if (square == x) {
  23.             return mid;
  24.         } else if (square < x) {
  25.             left = mid + 1;
  26.         } else {
  27.             right = mid - 1;
  28.         }
  29.     }
  30.  
  31.     return right;
  32. }
  33.  
  34. uint32_t int_sqrt2(uint32_t x) {
  35.     if (x < 2) return x;
  36.  
  37.     uint32_t res = x;
  38.     uint32_t temp;
  39.  
  40.     // Метод Ньютона
  41.     while (1) {
  42.         temp = (res + x / res) / 2;
  43.         if (temp >= res) {
  44.             break;
  45.         }
  46.         res = temp;
  47.     }
  48.  
  49.     return res;
  50. }
  51.  
  52.  
  53. uint32_t int_sqrt3(uint32_t x) {
  54.     if (x < 2) return x;
  55.  
  56.     // Начальное приближение: половина x
  57.     uint32_t res = x >> 1;
  58.  
  59.     // Если x меньше 4, нужно вернуть 1
  60.     if (res == 0) return 1;
  61.  
  62.     // Метод Ньютона с оптимизированным начальным приближением
  63.     while (1) {
  64.         uint32_t temp = (res + x / res) >> 1;
  65.         if (temp >= res) {
  66.             break;
  67.         }
  68.         res = temp;
  69.     }
  70.  
  71.     return res;
  72. }
  73.  
  74. uint32_t sqrtInt32(uint32_t n) {
  75. 	int32_t ret = 0;
  76. 	int32_t s;
  77. 	int32_t ret_sq = -n - 1;
  78. 	for (s = 30; s >= 0; s -= 2) {
  79. 		int32_t b;
  80. 		ret += ret;
  81. 		b = ret_sq + ((2 * ret + 1) << s);
  82. 		if (b < 0) {
  83. 			ret_sq = b;
  84. 			ret++;
  85. 		}
  86. 	}
  87. 	return ret;
  88. }
  89.  
  90. uint32_t int_sqrt4(uint32_t x) {
  91.     if (x < 2) return x;
  92.  
  93.     // Магическое начальное приближение
  94.     uint32_t res = x;
  95.     if (x > 0xFFFF) res = (x >> 16) + 1;
  96.     else if (x > 0xFF) res = (x >> 8) + 1;
  97.     else if (x > 0xF) res = (x >> 4) + 1;
  98.     else res = (x >> 1) + 1;
  99.  
  100.     // Одна итерация Ньютона
  101.     res = (res + x / res) >> 1;
  102.  
  103.     // Вторая итерация (можно убрать, если нужна супер-скорость, но точность будет ниже)
  104.     res = (res + x / res) >> 1;
  105.  
  106.     return res;
  107. }
  108.  
  109. int main()
  110. {
  111.  
  112.     uint16_t i,j;
  113.     uint32_t sqrt, res;
  114.     for(j=0;j<6000;j++)
  115.     for(i=0;i<4095;i++){
  116.         sqrt = i;
  117.         sqrt = sqrt * sqrt;
  118.         res = sqrtInt32(sqrt);
  119.         if(i != res){
  120.  
  121.             printf("error %d res %d\n\r",i,res);
  122.             j=1000;
  123.             break;
  124.         }
  125.     }
  126.  
  127.  
  128.  
  129.  
  130.     printf("Hello World");
  131.  
  132.     return 0;
  133. }
Success #stdin #stdout 0.98s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Hello World
https://ideone.com/XiYO2I
language:
C++ (gcc 8.3)
created:
9 days 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!