zeleny (02.08.2014 21:29 - 04.08.2014 00:11, просмотров: 9247)
быстрый 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;
}