Коллеги, добрый день.
Потребовалось сделать быстрое (не втупую вычитаниями, разумеется) деление на 10, много думал, пробовал разное.
Потом читал интернеты и вумные книжки (например, Генри С. Уоррен мл. "Алгоритмические трюки для программистов", 2-е издание), пробовал всякие разложения в ряд, умножение на "0,8" и деление сдвигами на 8, "магические" множители и т.п. - всё не то, либо слишком сложно/медленно, либо недостаточная точность (с рядами).
Спустя пару-тройку дней нашёл в сети следующий код:
Код:
DIV10:
; Вх: [HL]
; Вых: [HL]
XRA A
LXI B,100Ah
LOOP:
DAD H
RAL
CMP C
JC SKIP
SUB C
INR L
SKIP:
DCR B
JNZ LOOP
RET
Чёрт возьми! Он работает моментально (всего 16 оборотов предельно короткого цикла), малый объём, красив во всех смыслах... В общем, 99% людей порадовались бы, использовали и забыли.
Но я трудный) Мне надо понять КАК он работает, и как такое вообще смогли придумать люди?!
Второй день ломаю голову! Пробовал скармливать разные тестовые числа, смотреть отладчиком их преобразование на каждой итерации алгоритма - не могу ничего понять((
Насколько вижу, происходит следующее. Весь исходник побитно прокручивается влево, в результате чего последовательно выталкиваются все биты в аккумулятор. Параллельно, с другого конца той же пары HL, теми же сдвигами накапливается результат. В результирующие биты пишется "0" когда вытолкнутое содержимое в аккумуляторе меньше 10, а когда больше 10, то пишется "1" и из аккумулятора вычитается 10. И так все 16 бит.
На протяжении всего цикла в причинных регистрах творится полнейшая ахинея, и ровно после последней итерации получается точный ответ. Идеально точный!
- "Холмс, но как?!" (С)
Сообщение от SfS
Ответить с цитированием
Марсианский код (деление на 10)
