OR>> Кому-то продолжение этой темы (про "без восстановления остатка") OR>> интересно? А то влом писать, если никому не надо
AC> Интересно. Если бы кое-кто не забил на FAQ, то оно бы самое оно именно AC> туда... Ok. Длинновато получилось, на всяк случай двумя письмами. Для FAQ, конечно, неплохо бы с картинками блок-схем, а тут простой текст.
======= Алгоритм деления без восстановления остатка.
Сначала немного бо "обычном" алгоритме, который на самом деле "с восстановлением остатка". В нём делитель вычитается из остатка, если заметили, что вычли много -- восстанавливается остаток. Разные вариации реализации этого алгоритма
- инкремент младшей части делимого, если вычитание было правильным или же вдвигание единички/нолика из переноса при сдвиге
- вычитание и потом, если надо, восстановление или же сравнение и вычитание
- это просто процессоро-зависимая оптимизация. Например, если процессор не имеет отдельных команд для простого сравнивания многобайтных слов, как AVR при помощи cp/cpc, то выгоднее вычесть при помощи sub/sbc и глянуть на перенос. А если ещё и перенос "как бы кривой" (при вычитании устанавливается при _отсутствии_ заёма, а при наличии - сбрасывается, угадайте с трёх раз о ком я :-), то после вычитания перенос сразу вдвигается в результат без инвертирования, а потом восстановление остатка делается по проверке младшего бита результата и спецкоманды многобайтного сравнения в этом месте даром не нужны. Ну ладно, это я отвлёкся на тему "всё в этом мире не просто так".
Суть алгоритма от этого не меняется "если перевычли -- ой, исправляемся, добавляем вычтенное назад, попробуем вычесть в 2 раза меньше".
У алгоритма без восстановления остатка подход другой - "ах, вычли лишего? хорошо, посмотрим сколько именно лишнего".
Итак: Вычитаем делитель из остатка. Если результат положителен, то всё "как обычно", интереса не представляет -- пишем единичку в младший бит результата и идём дальше.
А вот если результат отрицателен, то мы пишем нуль в младший бит результата и идём по другому пути. НЕ ДОБАВЛЯЕМ делитель к остатку. Берём и _добавляем_ _половину_ вычтенного. Т.е. сдвигаем группу (остаток,делимое) и прибавляем делитель к остатку. Вместо
2*((rem-divs) + divs) - divs ; восст.остатка, сдвиг, вычитаниепроводим операцию
2*(rem-divs)+divs ; сдвиг, сложениеТ.е. _делаем_вид_, что мы ничего не вычитали на предыдущем шаге, а сейчас вычли, а не добавили. Опять смотрим на знак остатка. Если остаток до сих пор отрицателен, то и на этом шаге вычитать не пришлось бы, пишем 0 в младший бит результата и продолжаем сдвигать/прибавлять. А вот если остаток стал неотрицательным, то тогда в "обычном" алгоритме в этом месте вычитание было бы нужным, пишем 1 в младший бит результата и опять идём на ветвь вычитания.
Таким образом имеем как бы два цикла -- вычитания и прибавления делителя -- с перекрёстными связями между ними. Суммарное число проходов равно разрядности делителя, но в каждом теле есть только одна операция -- сложения либо вычитания, и, соответственно, одна экономится (если она выполнялась бы в "обычном" алгоритме). Статистический выигрыш -
0.5 * число_проходов * цена_сложения_остатка_с_делимым.Но, как я уже говорил, есть недостаток -- всегда надо знать знак регистра остатка. Можно расширить его разрядность то добавляются операции по сдвигу и добавлению/вычитанию дополнительного байта, весь выигрыш пропадает. Для расширения достаточно бы 1 бита, но... чтобы он обрабатывался в одном цикле с остальными битами остатка, что легко реализовать в аппаратуре, но невозможно программно в готовом процессоре. Поэтому алгоритм подходит для деления на числа, на 1 бит меньшие, чем имеющиеся регистры для остатка. Например, u16/u15, u32/u15, u32/u31. Можно попытаться сохранять информацию о знаке в структуре программы, но дополнительные проверки/переходы, опять таки, скушают весь или большую часть выиграша.
Вот как выглядит этот алгоритм для AVR в варианте u16/u15
.macro shift_acc add dvd_l,dvd_l rol dvd_h rol rem_l rol rem_h .endm .macro sub_divs sub rem_l,divs_l sbc rem_h,divs_h .endm .macro add_divs add rem_l,divs_l adc rem_h,divs_h .endm
u16_15: ; 26w 3 + (10..12)*16 + (3..5) = 166..200 ldi cnt,16 clr rem_h clr rem_l lminus: shift_acc sub_divs brmi toplus tominus: inc dvd_l dec cnt brne lminus ret lplus: shift_acc add_divs brpl tominus toplus: dec cnt brne lplus ; если мы до самого конца в ситуации "ещё тогда вычли много", ; то для получения правильного остатка надо ещё раз прибавить ; если остаток не нужен (хотя бы для округления результата), ; то add_divs тоже не нужен. add_divs ret
Вот так это же выглядит при разворачивании цикла. u16_15: u16_15: ; 9+32*7+20 = 253w ; 9+(16..18)*7+(13..15) = 134..150cy clr rem_h clr rem_l
shift_acc ; 4 sub_divs ; 2 brmi 2f ; nextplus
.rept 7 ;--------------
1: inc dvd_l ; shift_acc ; sub_divs ; =7 brpl 3f ; nextminus rjmp 4f ; nextplus 2: shift_acc ; add_divs ; =6 brmi 4f ; nextplus ;-------------- 3: inc dvd_l ; shift_acc ; sub_divs ; =7 brpl 1f ; nextminus rjmp 2f ; nextplus 4: shift_acc ; add_divs ; =6 brmi 2f ; nextplus .endr 1: inc dvd_l ; shift_acc ; sub_divs ; =7 brmi 4f ; nextplus 3: inc dvd_l ret 2: shift_acc ; add_divs ; =6 brpl 3b ; nextminus 4: add_divs retМаленькое объяснение - as (ассемблер из пакета gcc) поддерживает локальные метки в виде одной цифры, в командах перехода указывается - переход идёт вперёд (f-orward - br 1f) или назад (b-ackward - br 1b) до ближайшей. Поэтому тут получается так, что rjmp 2f осуществляет переход на следующую "реализацию" тела в команде .rept либо за пределы блока повторения.
Как я уже говорил, алгоритм без восстановления остатка даёт выигрыш тем больше, чем больше разница в разрядности процессора и делителя/остатка. Деление u32/u31 (в макросы добавить работу с бОльшим числом регистров и число проходов цикла увеличить до 32) выполняется 520..586 циклов (552..554 при выравнивании ветвей, показано ниже для u20/u10), тогда как "обычный" алгоритм u32/u32 -
584..680 циклов.========= продолжение следует.
Wbr,