|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sashka Yackubtchick 2:5054/29.54 15 Nov 2001 04:23:34
To : Yuri Pudovchenko
Subject : Целочисленное деление
--------------------------------------------------------------------------------
14 Nov 01 20:54, Yuri Pudovchenko писАл(а) к Leonid Bessmertny:
LB>> Господа ! Hикто не сталкивался с необходимостью деления двух целых
LB>> чисел нацело с использованием двоичной аpифметики ? Hеобходимо
LB>> pазделить тpехбайтовое число на максимум двухбайтовое. Поделитесь
LB>> алгоpитмом плиз.
YP> Поскольку числа небольшие, то можно воспользоваться стандартными
YP> командами любого языка. Вот если бы кто рассказал как поделить числа не
YP> вмещающиеся в один регистр ... например 2048-битовое на 333-битовое.
Вычитанием.
Допустим максимальный регистр у тебя 32а разряда.
Значит разряды совпадающие по позициям ты вычтешь за 11 итераций +
При вычитании ты руководствуешься следующим
- если в результате вычитания текущих позиций у тебя выставился CF (вычитаемое
больше) ты сначала перед вычитанием следующей позиции уменьшаешь её на 1.
После того как цикл вычитания позиций = равных позициям делителя закончился
ты смотришь не был ли установлен carry при последнем вычитании
если да - то уменьшаешь следующий DWORD делимого на 1.
Если в результате уменьшения опять выставился carry уменьшаешь следующий на
один и так до конца.
Если в старших разрядах делимого не осталось выставленных битов наступает
последняя часть деления - те вычитаешь пока 333 оставшихся бита выражают
число >= делителю.
Когда в этих битах у делимого окажется число < делителя - алгоритм прекращает
работу.
Количество итераций будет частным, ну а последнее число меньшее делителя -
остатком.
Однако 2048 может быть большим числом :) max = 2*2^2047-1.
Это наверно для рассчёта размеров галактик в кубических метрах :)
Если бы я писал процедуру то она принимала бы как аргумент четыре
указателя: адрес 2048 числа адрес 333 числа адрес куда записать целую часть
адрес куда записать остаток.
Hе знаю понятно ли я объяснил.
Всё строится на азбучных истинах деление можно представить как
делимое=частное*делитель+остаток
умножение опять же можно представить на цикл сложений
ну а обратное сложению - вычитание.
Остальная информация для понимания относится к области позиционных систем
исчислений.
Представь что в регистр вмещалась бы лишь одна десятичная позиция
и нужно было вычесть из числа в 9 знаков число из 3х
Мы бы помещали в пару регистров поочередно цифры очередной позиции
и если первая цифра меньше второй то мы вычитали бы не из неё а из
суммы 10+первое число - второе число. При этом мы делали бы заем из старшего
разряда - иначе говоря уменьшали бы старший разряд на 1.
Именно так вычитает компьютер единственая разница что тебе самому нужно будет
уменьшать старший разряд ну и конечно он прибавлят не 10 а число = 2 в степени
колличества разрядов используемого типа данных.
Hапример если ты вычитаешь 01h - 02h результат будет равен FFh
реально произошло вычитание из 256+1 (FF=255 256+1-2=255)
а если из 0000 0001h - 0000 0002h результатом будет FFFF FFFFh
рельно вычитание произошло из 1 0000 0001h - 0000 0002h
При этом установится carry. И уже на твоей совести делать с ним что-либо.
Компьютер лишь сигнализирует о том что был заем с помощью флага.
Пока!
Sashka, The Svin.
--- GoldED/W32 3.00.Beta1+
* Origin: Svin, Perm, Russia (2:5054/29.54)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
