Где я могу найти алгоритмы мягкого умножения и деления?

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

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

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

3. Сдвиг множителя на 1

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

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

1. Если делитель больше делимого, остановитесь.

2. Пока регистр делителя меньше регистра делимого, сдвиг влево.

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

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

5. Начните с шага 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

Я полагаю, мы говорим о целых числах?

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

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

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

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

Оказывается, у меня остался какой-то старый ассемблерный код 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

Основные математические методы деления микроконтроллера PIC

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