2010-03-05 6 views
14

Я работаю над микроконтроллером без аппаратного умножения и разделения. Мне нужно подготовить алгоритмы программного обеспечения для этих основных операций, которые являются хорошим балансом компактных размеров и эффективности. Мой порт компилятора C будет использовать эти альго, а не сами разработчики C.Где можно найти алгоритмы размножения и разложения?

Мой google-fu пока что в основном шумит по этой теме.

Может ли кто-нибудь указать мне на что-то информативное? Я могу использовать команды add/sub и shift. Алгоритмы, основанные на просмотре таблиц, также могут работать для меня, но я немного беспокоюсь о том, чтобы так много перерабатывать в back-end компилятора ... гм, так сказать.

+0

Это какой-то странный микроконтроллер, что для этого еще нет компилятора C? Вы можете использовать этот компилятор (возможно, хорошую идею) или проверить его исходный код, если он доступен, для подпрограмм. –

+0

Имеет ли этот микроконтроллер имя? – AakashM

+0

Это новое. Это часть исследовательского проекта. – srking

ответ

6

Вот простой алгоритм умножения:

  1. Начнет с крайним правым битом множителя.

  2. Если бит множителя 1, добавить множимое

  3. сдвиг множимого 1

  4. Переход к следующему биту в умножитель и вернуться к шагу 2.

И вот алгоритм деления:

  1. I f делитель больше, чем дивиденд, остановка.

  2. Хотя регистр делителей меньше, чем регистр дивидендов, сдвиг влево.

  3. Сдвиг делитель регистр вправо на 1.

  4. Subtract делители регистр из регистра дивидендов и изменить бит 1 в регистре результата на бит, который соответствует общему числу сдвигов, сделанных в регистр делителя.

  5. Начните с шага 1 с регистром делителя в исходном состоянии.

Конечно, вам нужно поставить чек на деление на 0, но он должен работать.

Эти алгоритмы, конечно, предназначены только для целых чисел.

+0

Что происходит на шаге 3 алгоритма деления, если вы разделите (1 << n) +1 на (1 << x), где n - ширина регистра-1? – jbcreix

+0

@jbcreix, я не уверен, что понимаю, что вы просите. Можете ли вы уточнить? –

+0

, если вы сдвигаете делитель влево, когда размер дивиденда больше, старший бит будет сдвинут с очень большими дивидендами. Итак, когда вы сдвигаетесь вправо, вы получите другое число в случае мощности 2 делителя, 0. – jbcreix

1

Вот алгоритм деления: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html

Я предполагаю, что мы говорим о Интс?

Если аппаратной поддержки нет, вам нужно будет реализовать свое собственное исключение по отдельности.

(Мне не повезло быстро найти алгоритм умножения, но я буду продолжать искать, если кто-то еще его не найдет).

+0

Wikipedia описывает множество алгоритмов умножения - shift & add - самый простой. http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add –

+0

Да целые числа. И спасибо Карлу, я проверю вики. – srking

1

Один простой и довольно эффективный алгоритм умножения для целых чисел - Russian Peasant Multiplication.

Для рационального использования вы можете попробовать двоичный код quote notation, для которого разделение проще обычного.

+0

Я думал, что алгоритм для людей, а не для машин. – Steve314

+1

Алгоритмы не зависят от процессора. – outis

+0

Не обязательно - один алгоритм может работать лучше или хуже других, в зависимости от того, работает ли оно на нем, поддерживает ли основные основные операции. Человеческий мозг поддерживает различные основные операции с ЦП. Мое личное умение 32-битное целочисленное добавление, по крайней мере, в несколько миллиардов раз медленнее, чем x86, например, тогда как у меня есть аппаратно-ускоренные алгоритмы зрения, которые намного превосходят любой текущий ПК. – Steve314

0

Чтобы умножить, добавьте частичные продукты из сдвинутого множителя в аккумулятор, если соответствующий бит в множителе установлен. Множитель Shift и множитель на конце цикла, тестовый множитель & 1, чтобы узнать, нужно ли делать это.

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 

Кстати, я никогда не выяснял, нужно ли было преобразовать все в положительное в начале. Если вы осторожны со сменными операциями, это может быть предотвращено издержки.

0

Микросхемы Microchip PICmicro 16Fxxx не имеют инструкции умножения или деления. Возможно, некоторые из подпрограмм мягкого размножения и мягкого разделения для него могут быть перенесены на ваш MCU.

PIC Microcontroller Basic Math Multiplication Methods

PIC Microcontroller Basic Math Division Methods

Также проверьте "Newton's method" for division. Я думаю, что этот метод дает наименьший исполняемый размер любого алгоритма деления, который я когда-либо видел, хотя объяснение делает его более сложным, чем оно есть на самом деле. Я слышал, что некоторые ранние суперкомпьютеры Cray использовали метод Ньютона для деления.