#include "inv_sqrt.h"

#define Strict_size          2048
#define Num_different_roots    69

int strict [Strict_size + 1] = {
   0,
   4096, 2896, 2364, 2048, 1831, 1672, 1548, 1448,
   1365, 1295, 1234, 1182, 1136, 1094, 1057, 1024,
   993, 965, 939, 915, 893, 873, 854, 836,
   819, 803, 788, 774, 760, 747, 735, 724,
   713, 702, 692, 682, 673, 664, 655, 647,
   639, 632, 624, 617, 610, 603, 597, 591,
   585, 579, 573, 568, 562, 557, 552, 547,
   542, 537, 533, 528, 524, 520, 516, 512,
   508, 504, 500, 496, 493, 489, 486, 482,
   479, 476, 472, 469, 466, 463, 460, 457,
   455, 452, 449, 446, 444, 441, 439, 436,
   434, 431, 429, 427, 424, 422, 420, 418,
   415, 413, 411, 409, 407, 405, 403, 401,
   399, 397, 395, 394, 392, 390, 388, 387,
   385, 383, 381, 380, 378, 377, 375, 373,
   372, 370, 369, 367, 366, 364, 363, 362,
   360, 359, 357, 356, 355, 353, 352, 351,
   349, 348, 347, 346, 344, 343, 342, 341,
   340, 338, 337, 336, 335, 334, 333, 332,
   331, 330, 328, 327, 326, 325, 324, 323,
   322, 321, 320, 319, 318, 317, 316, 316,
   315, 314, 313, 312, 311, 310, 309, 308,
   307, 307, 306, 305, 304, 303, 302, 301,
   301, 300, 299, 298, 297, 297, 296, 295,
   294, 294, 293, 292, 291, 291, 290, 289,
   288, 288, 287, 286, 286, 285, 284, 284,
   283, 282, 281, 281, 280, 279, 279, 278,
   278, 277, 276, 276, 275, 274, 274, 273,
   273, 272, 271, 271, 270, 270, 269, 268,
   268, 267, 267, 266, 266, 265, 264, 264,
   263, 263, 262, 262, 261, 261, 260, 260,
   259, 259, 258, 258, 257, 257, 256, 256,
   255, 255, 254, 254, 253, 253, 252, 252,
   251, 251, 250, 250, 249, 249, 248, 248,
   247, 247, 246, 246, 246, 245, 245, 244,
   244, 243, 243, 243, 242, 242, 241, 241,
   240, 240, 240, 239, 239, 238, 238, 238,
   237, 237, 236, 236, 236, 235, 235, 234,
   234, 234, 233, 233, 233, 232, 232, 231,
   231, 231, 230, 230, 230, 229, 229, 228,
   228, 228, 227, 227, 227, 226, 226, 226,
   225, 225, 225, 224, 224, 224, 223, 223,
   223, 222, 222, 222, 221, 221, 221, 220,
   220, 220, 219, 219, 219, 218, 218, 218,
   218, 217, 217, 217, 216, 216, 216, 215,
   215, 215, 214, 214, 214, 214, 213, 213,
   213, 212, 212, 212, 212, 211, 211, 211,
   210, 210, 210, 210, 209, 209, 209, 209,
   208, 208, 208, 207, 207, 207, 207, 206,
   206, 206, 206, 205, 205, 205, 205, 204,
   204, 204, 204, 203, 203, 203, 203, 202,
   202, 202, 202, 201, 201, 201, 201, 200,
   200, 200, 200, 199, 199, 199, 199, 198,
   198, 198, 198, 197, 197, 197, 197, 197,
   196, 196, 196, 196, 195, 195, 195, 195,
   195, 194, 194, 194, 194, 193, 193, 193,
   193, 193, 192, 192, 192, 192, 192, 191,
   191, 191, 191, 190, 190, 190, 190, 190,
   189, 189, 189, 189, 189, 188, 188, 188,
   188, 188, 187, 187, 187, 187, 187, 186,
   186, 186, 186, 186, 185, 185, 185, 185,
   185, 185, 184, 184, 184, 184, 184, 183,
   183, 183, 183, 183, 182, 182, 182, 182,
   182, 182, 181, 181, 181, 181, 181, 181,
   180, 180, 180, 180, 180, 179, 179, 179,
   179, 179, 179, 178, 178, 178, 178, 178,
   178, 177, 177, 177, 177, 177, 177, 176,
   176, 176, 176, 176, 176, 175, 175, 175,
   175, 175, 175, 174, 174, 174, 174, 174,
   174, 174, 173, 173, 173, 173, 173, 173,
   172, 172, 172, 172, 172, 172, 172, 171,
   171, 171, 171, 171, 171, 170, 170, 170,
   170, 170, 170, 170, 169, 169, 169, 169,
   169, 169, 169, 168, 168, 168, 168, 168,
   168, 168, 167, 167, 167, 167, 167, 167,
   167, 166, 166, 166, 166, 166, 166, 166,
   165, 165, 165, 165, 165, 165, 165, 165,
   164, 164, 164, 164, 164, 164, 164, 163,
   163, 163, 163, 163, 163, 163, 163, 162,
   162, 162, 162, 162, 162, 162, 162, 161,
   161, 161, 161, 161, 161, 161, 161, 160,
   160, 160, 160, 160, 160, 160, 160, 159,
   159, 159, 159, 159, 159, 159, 159, 158,
   158, 158, 158, 158, 158, 158, 158, 158,
   157, 157, 157, 157, 157, 157, 157, 157,
   156, 156, 156, 156, 156, 156, 156, 156,
   156, 155, 155, 155, 155, 155, 155, 155,
   155, 155, 154, 154, 154, 154, 154, 154,
   154, 154, 154, 153, 153, 153, 153, 153,
   153, 153, 153, 153, 152, 152, 152, 152,
   152, 152, 152, 152, 152, 152, 151, 151,
   151, 151, 151, 151, 151, 151, 151, 150,
   150, 150, 150, 150, 150, 150, 150, 150,
   150, 149, 149, 149, 149, 149, 149, 149,
   149, 149, 149, 148, 148, 148, 148, 148,
   148, 148, 148, 148, 148, 147, 147, 147,
   147, 147, 147, 147, 147, 147, 147, 147,
   146, 146, 146, 146, 146, 146, 146, 146,
   146, 146, 146, 145, 145, 145, 145, 145,
   145, 145, 145, 145, 145, 144, 144, 144,
   144, 144, 144, 144, 144, 144, 144, 144,
   144, 143, 143, 143, 143, 143, 143, 143,
   143, 143, 143, 143, 142, 142, 142, 142,
   142, 142, 142, 142, 142, 142, 142, 142,
   141, 141, 141, 141, 141, 141, 141, 141,
   141, 141, 141, 140, 140, 140, 140, 140,
   140, 140, 140, 140, 140, 140, 140, 139,
   139, 139, 139, 139, 139, 139, 139, 139,
   139, 139, 139, 139, 138, 138, 138, 138,
   138, 138, 138, 138, 138, 138, 138, 138,
   137, 137, 137, 137, 137, 137, 137, 137,
   137, 137, 137, 137, 137, 136, 136, 136,
   136, 136, 136, 136, 136, 136, 136, 136,
   136, 136, 136, 135, 135, 135, 135, 135,
   135, 135, 135, 135, 135, 135, 135, 135,
   134, 134, 134, 134, 134, 134, 134, 134,
   134, 134, 134, 134, 134, 134, 133, 133,
   133, 133, 133, 133, 133, 133, 133, 133,
   133, 133, 133, 133, 132, 132, 132, 132,
   132, 132, 132, 132, 132, 132, 132, 132,
   132, 132, 131, 131, 131, 131, 131, 131,
   131, 131, 131, 131, 131, 131, 131, 131,
   131, 130, 130, 130, 130, 130, 130, 130,
   130, 130, 130, 130, 130, 130, 130, 130,
   129, 129, 129, 129, 129, 129, 129, 129,
   129, 129, 129, 129, 129, 129, 129, 129,
   128, 128, 128, 128, 128, 128, 128, 128,
   128, 128, 128, 128, 128, 128, 128, 128,
   127, 127, 127, 127, 127, 127, 127, 127,
   127, 127, 127, 127, 127, 127, 127, 127,
   126, 126, 126, 126, 126, 126, 126, 126,
   126, 126, 126, 126, 126, 126, 126, 126,
   125, 125, 125, 125, 125, 125, 125, 125,
   125, 125, 125, 125, 125, 125, 125, 125,
   125, 124, 124, 124, 124, 124, 124, 124,
   124, 124, 124, 124, 124, 124, 124, 124,
   124, 124, 124, 123, 123, 123, 123, 123,
   123, 123, 123, 123, 123, 123, 123, 123,
   123, 123, 123, 123, 122, 122, 122, 122,
   122, 122, 122, 122, 122, 122, 122, 122,
   122, 122, 122, 122, 122, 122, 122, 121,
   121, 121, 121, 121, 121, 121, 121, 121,
   121, 121, 121, 121, 121, 121, 121, 121,
   121, 120, 120, 120, 120, 120, 120, 120,
   120, 120, 120, 120, 120, 120, 120, 120,
   120, 120, 120, 120, 120, 119, 119, 119,
   119, 119, 119, 119, 119, 119, 119, 119,
   119, 119, 119, 119, 119, 119, 119, 119,
   118, 118, 118, 118, 118, 118, 118, 118,
   118, 118, 118, 118, 118, 118, 118, 118,
   118, 118, 118, 118, 117, 117, 117, 117,
   117, 117, 117, 117, 117, 117, 117, 117,
   117, 117, 117, 117, 117, 117, 117, 117,
   117, 116, 116, 116, 116, 116, 116, 116,
   116, 116, 116, 116, 116, 116, 116, 116,
   116, 116, 116, 116, 116, 116, 115, 115,
   115, 115, 115, 115, 115, 115, 115, 115,
   115, 115, 115, 115, 115, 115, 115, 115,
   115, 115, 115, 115, 114, 114, 114, 114,
   114, 114, 114, 114, 114, 114, 114, 114,
   114, 114, 114, 114, 114, 114, 114, 114,
   114, 114, 113, 113, 113, 113, 113, 113,
   113, 113, 113, 113, 113, 113, 113, 113,
   113, 113, 113, 113, 113, 113, 113, 113,
   113, 112, 112, 112, 112, 112, 112, 112,
   112, 112, 112, 112, 112, 112, 112, 112,
   112, 112, 112, 112, 112, 112, 112, 112,
   112, 111, 111, 111, 111, 111, 111, 111,
   111, 111, 111, 111, 111, 111, 111, 111,
   111, 111, 111, 111, 111, 111, 111, 111,
   111, 110, 110, 110, 110, 110, 110, 110,
   110, 110, 110, 110, 110, 110, 110, 110,
   110, 110, 110, 110, 110, 110, 110, 110,
   110, 110, 109, 109, 109, 109, 109, 109,
   109, 109, 109, 109, 109, 109, 109, 109,
   109, 109, 109, 109, 109, 109, 109, 109,
   109, 109, 109, 109, 108, 108, 108, 108,
   108, 108, 108, 108, 108, 108, 108, 108,
   108, 108, 108, 108, 108, 108, 108, 108,
   108, 108, 108, 108, 108, 108, 107, 107,
   107, 107, 107, 107, 107, 107, 107, 107,
   107, 107, 107, 107, 107, 107, 107, 107,
   107, 107, 107, 107, 107, 107, 107, 107,
   107, 106, 106, 106, 106, 106, 106, 106,
   106, 106, 106, 106, 106, 106, 106, 106,
   106, 106, 106, 106, 106, 106, 106, 106,
   106, 106, 106, 106, 106, 105, 105, 105,
   105, 105, 105, 105, 105, 105, 105, 105,
   105, 105, 105, 105, 105, 105, 105, 105,
   105, 105, 105, 105, 105, 105, 105, 105,
   105, 104, 104, 104, 104, 104, 104, 104,
   104, 104, 104, 104, 104, 104, 104, 104,
   104, 104, 104, 104, 104, 104, 104, 104,
   104, 104, 104, 104, 104, 104, 104, 103,
   103, 103, 103, 103, 103, 103, 103, 103,
   103, 103, 103, 103, 103, 103, 103, 103,
   103, 103, 103, 103, 103, 103, 103, 103,
   103, 103, 103, 103, 103, 102, 102, 102,
   102, 102, 102, 102, 102, 102, 102, 102,
   102, 102, 102, 102, 102, 102, 102, 102,
   102, 102, 102, 102, 102, 102, 102, 102,
   102, 102, 102, 102, 101, 101, 101, 101,
   101, 101, 101, 101, 101, 101, 101, 101,
   101, 101, 101, 101, 101, 101, 101, 101,
   101, 101, 101, 101, 101, 101, 101, 101,
   101, 101, 101, 101, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 100, 100, 100,
   100, 100, 100, 100, 100, 99, 99, 99,
   99, 99, 99, 99, 99, 99, 99, 99,
   99, 99, 99, 99, 99, 99, 99, 99,
   99, 99, 99, 99, 99, 99, 99, 99,
   99, 99, 99, 99, 99, 99, 99, 98,
   98, 98, 98, 98, 98, 98, 98, 98,
   98, 98, 98, 98, 98, 98, 98, 98,
   98, 98, 98, 98, 98, 98, 98, 98,
   98, 98, 98, 98, 98, 98, 98, 98,
   98, 98, 97, 97, 97, 97, 97, 97,
   97, 97, 97, 97, 97, 97, 97, 97,
   97, 97, 97, 97, 97, 97, 97, 97,
   97, 97, 97, 97, 97, 97, 97, 97,
   97, 97, 97, 97, 97, 97, 97, 96,
   96, 96, 96, 96, 96, 96, 96, 96,
   96, 96, 96, 96, 96, 96, 96, 96,
   96, 96, 96, 96, 96, 96, 96, 96,
   96, 96, 96, 96, 96, 96, 96, 96,
   96, 96, 96, 96, 95, 95, 95, 95,
   95, 95, 95, 95, 95, 95, 95, 95,
   95, 95, 95, 95, 95, 95, 95, 95,
   95, 95, 95, 95, 95, 95, 95, 95,
   95, 95, 95, 95, 95, 95, 95, 95,
   95, 95, 94, 94, 94, 94, 94, 94,
   94, 94, 94, 94, 94, 94, 94, 94,
   94, 94, 94, 94, 94, 94, 94, 94,
   94, 94, 94, 94, 94, 94, 94, 94,
   94, 94, 94, 94, 94, 94, 94, 94,
   94, 94, 93, 93, 93, 93, 93, 93,
   93, 93, 93, 93, 93, 93, 93, 93,
   93, 93, 93, 93, 93, 93, 93, 93,
   93, 93, 93, 93, 93, 93, 93, 93,
   93, 93, 93, 93, 93, 93, 93, 93,
   93, 93, 93, 92, 92, 92, 92, 92,
   92, 92, 92, 92, 92, 92, 92, 92,
   92, 92, 92, 92, 92, 92, 92, 92,
   92, 92, 92, 92, 92, 92, 92, 92,
   92, 92, 92, 92, 92, 92, 92, 92,
   92, 92, 92, 92, 92, 92, 91, 91,
   91, 91, 91, 91, 91, 91, 91, 91,
   91, 91, 91, 91, 91, 91, 91, 91,
   91, 91, 91, 91, 91, 91, 91, 91,
   91, 91, 91, 91, 91, 91, 91, 91,
   91, 91, 91, 91, 91, 91, 91, 91,
   91, 90, 90, 90, 90, 90, 90, 90,
   90, 90, 90, 90, 90, 90, 90, 90,
   90, 90, 90, 90, 90, 90, 90, 90
};

static const int index_sqrt [Num_different_roots] = {
   2049, 2072, 2119, 2167, 2217, 2269, 2323, 2378,
   2436, 2496, 2558, 2622, 2689, 2758, 2830, 2905,
   2983, 3064, 3149, 3237, 3329, 3424, 3524, 3629,
   3738, 3852, 3971, 4097, 4228, 4365, 4509, 4661,
   4820, 4988, 5164, 5350, 5547, 5754, 5973, 6205,
   6451, 6711, 6988, 7282, 7595, 7929, 8286, 8666,
   9074, 9511, 9981, 10486, 11031, 11619, 12256, 12946,
   13696, 14514, 15407, 16385, 17459, 18642, 19950, 21400,
   23015, 24819, 26844, 29128, 31715
};

static const int value [Num_different_roots] = {
   90, 89, 88, 87, 86, 85, 84, 83,
   82, 81, 80, 79, 78, 77, 76, 75,
   74, 73, 72, 71, 70, 69, 68, 67,
   66, 65, 64, 63, 62, 61, 60, 59,
   58, 57, 56, 55, 54, 53, 52, 51,
   50, 49, 48, 47, 46, 45, 44, 43,
   42, 41, 40, 39, 38, 37, 36, 35,
   34, 33, 32, 31, 30, 29, 28, 27,
   26, 25, 24, 23, 22
};

#define Last_index 31715
#define Last_value 22

int _inv_sqrt( int x ) {

   /*
   if (x <= Strict_size) {
      return strict [x];
   }
   */
   if (x > Max_length) {
      return 0;
   }
   if (x >= Last_index) {
      return Last_value;
   }

//
//  Binary search :
//
	int bottom = 0;
	int top = Num_different_roots - 1;
	int imed;
   while (bottom != top) {
      imed = (bottom + top) / 2;
      if (x < index_sqrt [imed]) {
         top = imed;
      } else if (x < index_sqrt [imed + 1]) {
         break;
      } else {
         bottom = imed;
      }
   }
   return value [imed];
}