Где я могу найти алгоритмы мягкого умножения и деления?
Я работаю над микроконтроллером без аппаратного умножения и деления. Мне нужно подготовить программные алгоритмы для этих основных операций, которые представляют собой хороший баланс компактного размера и эффективности. Мой порт компилятора C будет использовать эти алгоритмы, а не сами разработчики C.
Мой гугл-фу пока что в основном шумит по этой теме.
Кто-нибудь может указать мне на что-то информативное? Я могу использовать инструкции add / sub и shift. Алгоритмы, основанные на поиске таблиц, могут также работать для меня, но я немного беспокоюсь о том, чтобы так сильно втиснуться в серверную часть компилятора... ну, так сказать.
7 ответов
Вот простой алгоритм умножения:
Начните с самого правого бита множителя.
Если бит в множителе равен 1, добавить множитель
Сдвиг умножить на 1
Перейти к следующему биту в множителе и вернуться к шагу 2.
А вот и алгоритм деления:
Если делитель больше, чем дивиденд, остановитесь.
Пока регистр делителя меньше, чем регистр дивидендов, сдвиг влево.
Регистр делителя сдвига вправо на 1.
Вычтите регистр делителя из регистра дивидендов и измените бит на 1 в регистре результатов в бите, который соответствует общему количеству сдвигов, выполненных в регистре делителей.
Начните снова с шага 1 с регистра делителя в исходном состоянии.
Конечно, вам нужно поставить чек для деления на 0, но это должно сработать.
Эти алгоритмы, конечно, только для целых чисел.
Мой любимый справочник для таких вещей, доступный в виде книги:
http://www.hackersdelight.org/
Также вы не ошибетесь с TAoCP: http://www-cs-faculty.stanford.edu/~uno/taocp.html
Вот алгоритм деления: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html
Я полагаю, мы говорим о Ints?
Если аппаратная поддержка отсутствует, вам придется реализовать собственное исключение деления на ноль.
(Мне не повезло быстро найти алгоритм умножения, но я буду продолжать искать, если кто-то еще не найдет его).
Одним простым и достаточно производительным алгоритмом умножения для целых чисел является умножение русского крестьянина.
Для рациональных, вы можете попробовать двоичную кавычку, для которой деление легче, чем обычно.
Оказывается, у меня все еще есть старый код ассемблера 68000 для длинного умножения и длинного деления. Код 68000 довольно чистый и простой, поэтому его легко перевести на ваш чип.
У 68000 были инструкции умножения и деления IIRC - я думаю, что они были написаны как учебное упражнение.
Решил просто поставить код здесь. Добавлены комментарии и в процессе исправлена проблема.
;
; Purpose : division of longword by longword to give longword
; : all values signed.
; Requires : d0.L == Value to divide
; : d1.L == Value to divide by
; Changes : d0.L == Remainder
; : d2.L == Result
; : corrupts d1, d3, d4
;
section text
ldiv: move #0,d3 ; Convert d0 -ve to +ve - d3 records original sign
tst.l d0
bpl.s lib5a
neg.l d0
not d3
lib5a: tst.l d1 ; Convert d1 -ve to +ve - d3 records result sign
bpl.s lib5b
neg.l d1
not d3
lib5b: tst.l d1 ; Detect division by zero (not really handled well)
bne.s lib3a
rts
lib3a: moveq.l #0,d2 ; Init working result d2
moveq.l #1,d4 ; Init d4
lib3b: cmp.l d0,d1 ; while d0 < d1 {
bhi.s lib3c
asl.l #1,d1 ; double d1 and d4
asl.l #1,d4
bra.s lib3b ; }
lib3c: asr.l #1,d1 ; halve d1 and d4
asr.l #1,d4
bcs.s lib3d ; stop when d4 reaches zero
cmp.l d0,d1 ; do subtraction if appropriate
bhi.s lib3c
or.l d4,d2 ; update result
sub.l d1,d0
bne.s lib3c
lib3d: ; fix the result and remainder signs
; and.l #$7fffffff,d2 ; don't know why this is here
tst d3
beq.s lib3e
neg.l d2
neg.l d0
lib3e: rts
;
; Purpose : Multiply long by long to give long
; Requires : D0.L == Input 1
; : D1.L == Input 2
; Changes : D2.L == Result
; : D3.L is corrupted
;
lmul: move #0,d3 ; d0 -ve to +ve, original sign in d3
tst.l d0
bpl.s lib4c
neg.l d0
not d3
lib4c: tst.l d1 ; d1 -ve to +ve, result sign in d3
bpl.s lib4d
neg.l d1
not d3
lib4d: moveq.l #0,d2 ; init d2 as working result
lib4a: asr.l #1,d0 ; shift d0 right
bcs.s lib4b ; if a bit fell off, update result
asl.l #1,d1 ; either way, shift left d1
tst.l d0
bne.s lib4a ; if d0 non-zero, continue
tst.l d3 ; basically done - apply sign?
beq.s lib4e ; was broken! now fixed
neg.l d2
lib4e: rts
lib4b: add.l d1,d2 ; main loop body - update result
asl.l #1,d1
bra.s lib4a
Кстати - я так и не понял, нужно ли было конвертировать все в позитив с самого начала. Если вы осторожны с операциями сдвига, это может быть предотвращено накладными расходами.
Чтобы умножить, добавьте частичные произведения из сдвинутого умножителя в накопитель, если соответствующий бит в умножителе установлен. Сдвиньте множитель и множитель в конце цикла, проверьте множитель и 1, чтобы узнать, нужно ли добавлять.
Микросхемы серии Microchip PICmicro 16Fxxx не имеют инструкции умножения или деления. Возможно, некоторые из программ мягкого умножения и мягкого деления могут быть перенесены на ваш MCU.
PIC Microcontroller Основные математические методы умножения
PIC Microcontroller Основные методы математического деления
Также проверьте "метод Ньютона" для разделения. Я думаю, что этот метод дает наименьший размер исполняемого файла из всех алгоритмов деления, которые я когда-либо видел, хотя объяснение делает его более сложным, чем на самом деле. Я слышал, что некоторые ранние суперкомпьютеры Cray использовали метод Ньютона для деления.