Отправлено KPAH 22 октября 2006 г. 00:40 В ответ на: Алгоритм нахождения корня квадратного. отправлено <font color=gray>TimMatTU</font> 21 октября 2006 г. 10:29

сразу говорю - числа с плавающей точкой. Нормализованные: X = 2^p * m, где m >= 1 и m<2. Таблица строилась по младшему биту порядка (p) и по первым 7 дробным битам m. Hint: наилучшее приближение квадратного корня для диапазона [A;B] с точки зрения относительной погрешности = (A*B)^0.25 , другими словами - корень четвёртой степени из произведения. Младший бит порядка надо учитывать ибо:
sqrt(2^p * m) = 2^k * sqrt(m) при p=2*k и
sqrt(2^p * m) = 2^k * sqrt(2*m) при p=2*k+1
Таким образом, в таблице хранятся приближения для sqrt(m) и sqrt(2*m). Таблица из 256 элементов даёт относительную точность до 9 бит после запятой. Если дополнительно сделаете 1 итерацию Ньютоном - будет 18 бит - < 4e-6. Для меньшей таблицы (а именно для 32 элементов) потребуется уже как минимум 2 итерации ньютона чтобы 1е-5 достичь.