|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergei Zubkov 2:5020/118.59 24 Feb 2002 04:16:27
To : Ilia Kantor
Subject : Re: большие числа
--------------------------------------------------------------------------------
On Sat, 23 Feb 02 04:16:46 +0300, Ilia Kantor wrote to Andrey Lipsky:
AL>> Подскажите, плз, как оpганизовать деление больших(длинных) чисел.
IK> While Up - l > Down Do
IK> Begin
IK> Mul(В, (Up + Down) Div 2, С);
Здесь он находит цифру частного путём умножения очередного приближения к
ней на весь делитель, который может быть тоже очень большим числом. Кнут
это делает, используя только первые три цифры делителя.
Чтобы не быть голословным.. Кнут, деление в столбик, без особых
комментариев
Даны два неотрицательных целых числа: U=U1U2...Um+n и V=V1V2...Vn,
представленных в системе счисления по основанию b.
Предполагается что V1!=0 и n>1
Hаходим частное Q=Q0Q1...Qm и остаток R=R1R2...Rn
1. Hормализация:
d <- floor( b / ( V1 + 1 ))
U0U1U2...Um+n <- U1U2...Um+n * d
2. Hачало цикла деления Uj...Uj+n на R:
j <- 0
3. Вычисление очередной цифры ответа q':
Если Uj==V1, то q' <- b - 1
иначе q' <- floor( (Uj * b + Uj+1) / V1 )
Если V2*q' > (Uj * b + Uj+1 - q'*V1) * b + Uj+2,
то q' <- q' - 1 и повторить эту проверку
(гарантировано что после этих операций мы получаем либо очередную цифру
ответа, либо цифру, на единицу большую)
4. Вычитание
UjUj+1...Uj+n <- UjUj+1...Uj+n - q' * V1V2...Vn
(возможным займом из Uj-1 пренебречь)
5. Qj <- q'
Если результат шага 4 был меньше нуля, то шаг 6, иначе шаг 7
6. Компенсация в случае если в 3. мы получили слишком большое q'
Qj <- Qj - 1
UjUj+1...Uj+n <- UjUj+1...Uj+n + V1V2...Vn
(возможным переносом в Uj-1 пренебречь)
7. Цикл
j <- j + 1
Если j<=m, то шаг 3
8. Денормализация
Q=Q1Q2...Qm уже содержит ответ
R1R2...Rn <- Um+1...Um+n / d
--Cubbi
--- vim-5.5/tin-1.7.2/inn-1.7.2/ifmail-2.14os
* Origin: Gummadoon BBS (out cold) (2:5020/118.59@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
