|
Страница 1 из 2
Для вычисления квадратного корня в этом примере использован метод Ньютона. Рассмотрены машинно-зависимый и машинно-независимый варианты. Перед применением алгоритма Ньютона область определения исходного числа сужается до [0.5,2] (во втором варианте до [1,16]). Второй вариант машинно-независим, но работает дольше. Вообще, это не самый быстрый вариант, но один из самых быстрых. Основная проблема заключается в том, что нет универсального машинного представления чисел с плавающей точкой, поэтому разделение числа на мантиссу и двоичную экспоненту как составляющих его компьютерного представления нельзя записать единым образом. Имено поэтому подключено описание математической библиотеки, из которой, впрочем, используются только frexp() и ldexp(). Конкретная реализация этих функций очень проста, но машинно-зависима. При разделении числа на мантиссу и экспоненту, мантисса оказывается в пределах [0.5,1). Если при этом экспонента нечетная, мантисса умножается на 2, тем самым область определения становится [0.5,2). К мантиссе применяется алгоритм Ньютона с начальным приближением 1. Окончательный результат получается с помощью применения ldexp() с половинным значением экспоненты. Для машинно-независимого варианта выделение экспоненты заменяется серией последовательных делений исходного значения на 16, пока аргумент не станет определяться на интервале [1,16]. Если исходный аргумент был меньше 1, то перед серией делений обращаем его. Алгоритм Ньютона применяется с начальным приближением 2. Окончательный результат получается серией последовательных умножений на 4 и дальнейшим обращением, если аргумент обращался. Сам алгоритм Ньютона для вычисления a=Sqroot(x) представляет быстро сходящуюся (при хорошем начальном приближении) серию итераций: ai+1=0.5*(ai+x/ai), где i -- номер итерации. |