Где я могу найти мягким - умножают и делят алгоритмы?
Я работаю над микроконтроллером без аппаратных средств, умножаются и делятся. Я должен приготовить алгоритмы программного обеспечения для этих основных операций, которые являются хорошим балансом компактного размера и эффективности. Мой порт компилятора C будет использовать эти алгоритмы, не сами разработчики C.
Мой google-fu до сих пор поднимает главным образом шум по этой теме.
Кто-либо может указать на меня на что-то информативное? Я могу использовать add/sub и команды сдвига. Основанные на поиске по таблице алгоритмы могли бы также работать на меня, но я немного волнуюсь по поводу зубрежки так в бэкенд компилятора... гм, так сказать.
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?
Если нет аппаратной поддержки, вам придется реализовать собственное исключение деления на ноль.
(Мне не очень повезло быстро найти алгоритм умножения, но я продолжу искать, если кто-то другой его не найдет).
Одним из простых и достаточно эффективных алгоритмов умножения целых чисел является Russian Peasant Multiplication .
Для рационального использования вы можете попробовать двоичную нотацию кавычек , для которой деление проще, чем обычно.
Для умножения добавьте частичные продукты от сдвинутого множителя в аккумулятор, если соответствующий бит в множителе установлен. Сдвиг множителя и множимого в конце цикла, проверка множителя и 1, чтобы узнать, нужно ли выполнять сложение.
Оказывается, у меня все еще есть какой-то старый ассемблерный код 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
Кстати - я так и не понял, нужно ли конвертировать все в позитив на старте. Если вы будете осторожны с операциями смены, это может быть предотвратимым накладными расходами.
Микросхемы Microchip PICmicro серии 16Fxxx не имеют инструкции умножения или деления. Возможно, некоторые из процедур мягкого умножения и мягкого деления для них могут быть перенесены на ваш MCU.
Микроконтроллер PIC Основные математические методы умножения
Микроконтроллер PIC Основные математические методы деления
Также посмотрите "метод Ньютона" для деления. Я думаю, что этот метод дает наименьший размер исполняемого файла среди всех алгоритмов деления, которые я когда-либо видел, хотя в объяснении он звучит сложнее, чем есть на самом деле. Я слышал, что некоторые ранние суперкомпьютеры Cray использовали метод Ньютона для деления.