Onde posso encontrar algoritmos suaves multiplicados e divididos?

Question

Estou trabalhando em um microcontrolador sem hardware multiplicar e dividir. Preciso preparar algoritmos de software para essas operações básicas que são um bom equilíbrio de tamanho e eficiência compactos. Meu porto de compilador C empregará esses algos, não os próprios desenvolvedores do C.

Meu Google-Fu está até agora, aparecendo principalmente ruído neste tópico.

Alguém pode me indicar algo informativo? Eu posso usar instruções de add/sub e turno. Algos baseados em pesquisa de mesa também podem funcionar para mim, mas estou um pouco preocupado em amontoar tanto o back-end do compilador ... hum, por assim dizer.

Answer 1

Aqui está um algoritmo de multiplicação simples:

1. Comece com o bit de multiplicador mais à direita.

2. Se o bit no multiplicador for 1, adicione multiplicando

3. Mudança multiplicando por 1

4. Mova para o próximo bit no multiplicador e volte para a etapa 2.

E aqui está um algoritmo de divisão:

1. Se o divisor for maior que o dividendo, pare.

2. Enquanto o Divisor Register é menor que o registro de dividendos, mude para a esquerda.

3. Shift Divisor Register bem em 1.

4. Subtraia o registro do divisor do registro de dividendos e altere o bit para 1 no registro de resultado no bit que corresponde ao número total de turnos feitos para o registro do divisor.

5. Comece de novo na etapa 1 com o Divisor Register no estado original.

É claro que você precisará fazer um cheque para dividir por 0, mas deve funcionar.

Esses algoritmos, é claro, são apenas para inteiros.

Answer 2

Minha referência favorita para coisas como esta, disponível em forma de livro:

http://www.hackersdelight.org/

Além disso, você não pode errar com o TAOCP: http://www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 3

Aqui está um algoritmo de divisão: http://www.prasannatech.net/2009/01/division-without-division-operator_24.html

Presumo que estamos falando de INTs?

Se não houver suporte de hardware, você precisará implementar sua própria exceção dividida por zero.

(Não tive muita sorte em encontrar um algoritmo de multiplicação, mas continuarei procurando se alguém não encontrar um).

Answer 4

Um algoritmo de multiplicação simples e razoavelmente de desempenho para inteiros é Multiplicação camponesa russa.

Para racionais, você pode tentar um binário notação de cotação, para qual divisão é mais fácil do que o habitual.

Answer 5

Acontece que ainda tenho algum código de montagem 68000 antigo para longa multiplicação e divisão longa. O código 68000 é bastante limpo e simples, por isso deve ser fácil de traduzir para o seu chip.

O 68000 havia multiplicar e dividir instruções IIRC - acho que elas foram escritas como um exercício de aprendizado.

Decidiu apenas colocar o código aqui. Adicionado comentários e, no processo, corrigiu um problema.

;
; 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

A propósito - eu nunca descobri se era necessário converter tudo em positivo no início. Se você tomar cuidado com as operações de turno, isso pode ser evitável sobrecarga.

Answer 6

Para multiplicar, adicione produtos parciais do multiplicando deslocado a um acumulador se o bit correspondente no multiplicador está definido. Mudar multiplicando e multiplicador no final do loop, testando multiplicador e 1 para verificar se a adição deve ser feita.

Answer 7

Os chips da série Microchip Picmicro 16FXXX não possuem uma instrução multiplique ou divida. Talvez algumas das rotinas macias de multiplicação e divisão suaves possam ser portadas para o seu MCU.

Microcontrolador PIC Métodos de Multiplicação Matemática

Microcontrolador PIC Métodos de divisão de matemática básica

Verifique também "Método de Newton" para a divisão. Eu acho que esse método fornece o menor tamanho executável de qualquer algoritmo de divisão que eu já vi, embora a explicação pareça mais complicada do que realmente é. Ouvi dizer que alguns supercomputadores do Cray primitivos usaram o método de Newton para a divisão.