Реферат: Длинная арифметика

- 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), — если больше.