Re: Деление длинных чисел методом Ньютона

From

Nick Kovaliov ()

To

Илья Кантор

Date

2002-10-30T11:25:29Z

Area

RU.ALGORITHMS

From: "Nick Kovaliov" <Nick@urm.ru>

    ИК> Как организовать вычисление A/B,
    ИК> если работаешь с неотрицательными
    ИК> числами без десятичной точки ?
Догадываюсь, что длинными целыми :)

В смысле как организовывать ?
Основных способа два -
один столбиком, другой методом Ньютона.

Второй не пробовал, но его (имхо) проще сделать эффективным
на языках высокого уровня, если быстро работает умножение.

    ИК> Сначала, вроде, нужно найти обратное к B методом Ньютона.
    ИК> С какой точностью это нужно делать, если длина A=n, Длина B=m ?

Допустим, в вычислении обратного ты ошибся на один битик (мдалший).
Тогда, умножая на ещё сколько-то битовое число (n-битовое),
ты рискуешь в худшем случае усилить ошибку на n бит.
То есть точность должна быть n + m, ну и +1, так, на всякий случай :)
Ежели ты можешь ошибиться только на полбита (округлённое значение),
то точности достаточно n/2 + m + 1.

    ИК> Сам метод Ньютона делает итерации R <- R+(1-BR)*R.
    ИК> С какой точностью выполнять каждую операцию ?
А вот с этим сложнее ...
(Я так догадываюсь, представление чисел типа FixedPoint ?)
Тут нужно прикидывать, сколько максимум бит в R+(1-BR)*R.
В роли "1" выступает длинное целое 2^(какое-то n).
Получается или довольно много бит, или как-то делать floating point ...
Но с floating point вычисления не такие простые ...
И погрешность учесть сложнее ...

А в Кнуте ещё описана не квадратическая, а кубическая итерация ...

Имхо слишком много накладных расходов,
которыя я лично не знаю, как избежать,
и поэтому проще просто столбиком :)

До встречи, всего наилучшего !


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)