Реферат: Длинная арифметика
- 73859998
--------
4890649 (Остаток)
Что мы делали? На каждом этапе в уме подбирали цифру (1, 3, 5 и т.д.), такую, что произведение этой цифры на делитель дает число меньшее, но наиболее близкое к числу... Какому? Это трудно сказать словами, но из примера ясно. Зачем нам это делать в уме, пусть делает компьютер. Однако упростим пример, оставим его для тестирования окончательной логики процедуры, тем более что и числа "длинные". Пусть число А будет меньше В*10, тогда в результате (целой части деления) будет одна цифра. Например, А равно 564, а В — 63 и простая десятичная система счисления. Попробуем подобрать цифру результата, но не методом прямого перебора, а методом деления отрезка пополам. Пусть Down — верхняя граница интервала изменения подбираемой цифры, Up — нижняя граница интервала, Ost равен делимому.
|
Down |
Up |
С = В * ( (Down + Up) Div 2) |
Ost = 564 |
|
0 |
10 |
315 = 63 * ( (0 + 10) Div 2) |
C < Ost |
|
5 |
10 |
441 = 63 * ( (5 + 10) Div 2) |
C < Ost |
|
7 |
10 |
504 = 63 * ( (7 + 10) Div 2) |
C < Ost |
|
8 |
10 |
567 = 63 * ( (8 + 10) Div 2) |
C > Ost |
|
8 |
9 |
504 = 63 * ( (8 + 9) Div 2) |
C < Ost |
Итак, результат — целая часть частного — равен (Up + Down) Div 2, остаток от деления — разность между значениями Ost и С. Нижнюю границу (Down) изменяем, если результат (С) меньше остатка, верхнюю (Up), — если больше.