|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nick Kovaliov 2:5020/400 30 Oct 2002 12:25:29
To : €«мп Љ в®а
Subject : Re: Деление длинных чисел методом Hьютона
--------------------------------------------------------------------------------
ИК> Как организовать вычисление A/B,
ИК> если работаешь с неотрицательными
ИК> числами без десятичной точки ?
Догадываюсь, что длинными целыми :)
В смысле как организовывать ?
Основных способа два -
один столбиком, другой методом Hьютона.
Второй не пробовал, но его (имхо) проще сделать эффективным
на языках высокого уровня, если быстро работает умножение.
ИК> Сначала, вроде, нужно найти обратное к B методом Hьютона.
ИК> С какой точностью это нужно делать, если длина A=n, Длина B=m ?
Допустим, в вычислении обратного ты ошибся на один битик (мдалший).
Тогда, умножая на ещё сколько-то битовое число (n-битовое),
ты рискуешь в худшем случае усилить ошибку на n бит.
То есть точность должна быть n + m, ну и +1, так, на всякий случай :)
Ежели ты можешь ошибиться только на полбита (округлённое значение),
то точности достаточно n/2 + m + 1.
ИК> Сам метод Hьютона делает итерации R <- R+(1-BR)*R.
ИК> С какой точностью выполнять каждую операцию ?
А вот с этим сложнее ...
(Я так догадываюсь, представление чисел типа FixedPoint ?)
Тут нужно прикидывать, сколько максимум бит в R+(1-BR)*R.
В роли "1" выступает длинное целое 2^(какое-то n).
Получается или довольно много бит, или как-то делать floating point ...
Hо с floating point вычисления не такие простые ...
И погрешность учесть сложнее ...
А в Кнуте ещё описана не квадратическая, а кубическая итерация ...
Имхо слишком много накладных расходов,
которыя я лично не знаю, как избежать,
и поэтому проще просто столбиком :)
До встречи, всего наилучшего !
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Деление длинных чисел методом Hьютона 