Микроконтроллеры

быстрый 16-битный sqrt никто не встречал ? таблично реально сделать ? про побитный сдвиг/проверку знаю, нужно еще быстрее. собсно найдено такое: делением (из аппноты ИАР): u8 sqrt16_div( u16 x ){ u16 a, b=x; a = x = 0x3f; x = b/x; a = x = (x+a)>>1; x = b/x; a = x = (x+a)>>1; x = b/x; x = (x+a)>>1; return(x); } сдвиг (из аппноты Микрочипа): u8 sqrt16_shift( u16 x ){ u8 bit=((u8)(x >> 8)) ? 0x80 : 0x08, result=0; while (bit){ u8 guess = result | bit; if ((u16)guess * guess <= x) result = guess; bit >>= 1; } return result; } сдвиг №2: u8 sqrt16_shift2( u16 n ){ u8 c,g; if ((u8)(n >> 8)) c = g = 0x80; else c = g = 8; for (;;) { if ((u16)g*g > n) g ^= c; c >>= 1; if (c == 0) return g; g |= c; } } Dijkstra: #define sqrt_dijkstra_iter(N) \ try = root + (1 << (N)); \ if (n >= try << (N)){ \ n -= try << (N); \ root |= 2 << (N); \ } u8 sqrt16_dijkstra( u16 n ){ u16 root=0, try; sqrt_dijkstra_iter(7); sqrt_dijkstra_iter(6); sqrt_dijkstra_iter(5); sqrt_dijkstra_iter(4); sqrt_dijkstra_iter(3); sqrt_dijkstra_iter(2); sqrt_dijkstra_iter(1); sqrt_dijkstra_iter(0); return root >> 1; } табличный приближенный 1(найден на просторах Stackoverflow): const u16 sqrt16_tab11[33] = {0,1,1,2,2,4,5,8,11,16,22,32,45,64,90,128,181,256,362,512,724,1024,1448,2048,2896,4096,5792,8192,11585,16384,23170,32768,46340}; const u16 sqrt16_tab12[32] = {32768,33276,33776,34269,34755,35235,35708,36174,36635,37090,37540,37984,38423,38858,39287,39712,40132,40548,40960,41367,41771,42170,42566,42959,43347,43733,44115,44493,44869,45241,45611,45977}; u8 sqrt16_tab1(u16 x){ u8 cnt=0; u16 t=x; while (t){ cnt++; t >>= 1; } if (6 >= cnt) t = (x << (6-cnt)); else t = (x >> (cnt-6)); return ((u32)sqrt16_tab11[cnt] * sqrt16_tab12[t & 31])>>15; } табличный 2: const u16 sqrt16_tab21[] = { 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1024, 1089, 1156, 1225, 1296, 1369, 1444, 1521, 1600, 1681, 1764, 1849, 1936, 2025, 2116, 2209, 2304, 2401, 2500, 2601, 2704, 2809, 2916, 3025, 3136, 3249, 3364, 3481, 3600, 3721, 3844, 3969, 4096, 4225, 4356, 4489, 4624, 4761, 4900, 5041, 5184, 5329, 5476, 5625, 5776, 5929, 6084, 6241, 6400, 6561, 6724, 6889, 7056, 7225, 7396, 7569, 7744, 7921, 8100, 8281, 8464, 8649, 8836, 9025, 9216, 9409, 9604, 9801, 10000, 10201, 10404, 10609, 10816, 11025, 11236, 11449, 11664, 11881, 12100, 12321, 12544, 12769, 12996, 13225, 13456, 13689, 13924, 14161, 14400, 14641, 14884, 15129, 15376, 15625, 15876, 16129, 16384, 16641, 16900, 17161, 17424, 17689, 17956, 18225, 18496, 18769, 19044, 19321, 19600, 19881, 20164, 20449, 20736, 21025, 21316, 21609, 21904, 22201, 22500, 22801, 23104, 23409, 23716, 24025, 24336, 24649, 24964, 25281, 25600, 25921, 26244, 26569, 26896, 27225, 27556, 27889, 28224, 28561, 28900, 29241, 29584, 29929, 30276, 30625, 30976, 31329, 31684, 32041, 32400, 32761, 33124, 33489, 33856, 34225, 34596, 34969, 35344, 35721, 36100, 36481, 36864, 37249, 37636, 38025, 38416, 38809, 39204, 39601, 40000, 40401, 40804, 41209, 41616, 42025, 42436, 42849, 43264, 43681, 44100, 44521, 44944, 45369, 45796, 46225, 46656, 47089, 47524, 47961, 48400, 48841, 49284, 49729, 50176, 50625, 51076, 51529, 51984, 52441, 52900, 53361, 53824, 54289, 54756, 55225, 55696, 56169, 56644, 57121, 57600, 58081, 58564, 59049, 59536, 60025, 60516, 61009, 61504, 62001, 62500, 63001, 63504, 64009, 64516, 65025 }; u8 sqrt16_tab2(u16 x) { const u16 *p = sqrt16_tab21; if (p[128] <= x) p += 128; if (p[ 64] <= x) p += 64; if (p[ 32] <= x) p += 32; if (p[ 16] <= x) p += 16; if (p[ 8] <= x) p += 8; if (p[ 4] <= x) p += 4; if (p[ 2] <= x) p += 2; if (p[ 1] <= x) p += 1; return p - sqrt16_tab21; }