Темы курсовых работ по «Технология программирования (Python)»
Что можно сказать относительно деления?
жүктеу/скачать 0,69 Mb.
|
| Что можно сказать относительно деления?
При вычислении предложенных рядов наряду с умножением используется деление чисел высокой точности. К счастью, при помощи алгоритма умножения удается выполнять деление почти так же быстро, как умножение. Для нахождения частного нужно приблизительно угадать число, обратное к делителю, скорректировать его, чтобы обратное стало точным, и затем умножить на делимое. Уточнение обратного осуществляется по методу Ньютона. Даны два числа [m, u] и [n, v]; мы считаем, что u ≥ v (хотя это предположение несущественно) и что n-й бит v равен 1 (т. е. у v нет старших нулей). Чем больше разница размеров и и v, тем более точным будет частное; разницу можно увеличить, умножая и на степень двойки. Отметим, что алгоритм деления будет неоднократно вызывать алгоритм умножения. Для нескольких первых из этих умножений можно воспользоваться обычной операцией умножения коротких чисел. Кроме того, все умножения и деления на степень двойки суть фактически сдвиги влево и вправо. 1. (Выбор размера обратного.) Найти наименьшее j, такое, что 2j ≥ max (m, 2n). Присвоить к значение 2j−1. 2. (Нормализация v.) Присвоить [k, v] значение 2k−n [n, v]. На этом шаге мы сдвигаем v влево, чтобы оно заняло k битов, причем левый бит был бы равен 1. Присвоить [2, а] значение [2, 2]. 3. (Вычисление последовательных приближений к 1/v.) Выполнить шаг 4 для i = 1, 2, …, j − 1. 4. (Вычисление приближения из 2i битов.) Присвоить [2i+1, d] значение 23·2i [2i−1 + 1, a] − [2i−1 + 1, a]2 ([k, v]/2k−2i) Деление в скобках (фактически сдвиг вправо) должно выполнятъся до умножения; идея состоит в том, чтобы ускорить умножение, отбросив лишние биты v, ненужные в данном приближения. Хотя кажется, что результат d может содержать больше 2i+1 битов, этого никогда не произойдет. Затем присвоить [2i + 1, а] значение [2i+1, d]/2i−1. 5. (Улучшение окончательной оценки.) Присвоить [3k, d] значение 22k[k + 1, а] − [k + 1, а]2·[k, v]. Затем присвоить [k + 1, а] значение ([Зk, d] + 22k−2)/22k−1. 6. (Окончательное деление.) Выдать в качестве результата ([k + 1, a] · [m, u] + 2k+n−2)/22+k−1. жүктеу/скачать 0,69 Mb. Достарыңызбен бөлісу:
|