Dove posso trovare soft-moltiplicano e algoritmi divide?

Question

sto lavorando su un micro-controllore senza hardware moltiplicare e dividere. Ho bisogno di cucinare algoritmi software per le operazioni di base che sono un buon equilibrio di dimensioni e di efficienza compatte. La mia porta C compilatore impiegherà questi algos, non gli sviluppatori C stessi.

Il mio google-fu è finora svolta per lo più rumore su questo argomento.

Qualcuno mi può puntare a qualcosa informativo? Posso utilizzare add / sub e le istruzioni di spostamento. algos basate Tabella di ricerca potrebbe anche lavoro per me, ma io sono un po 'preoccupato per stipare tanto nel back-end del compilatore ... ehm, per così dire.

Answer 1

Ecco un algoritmo di moltiplicazione semplice:

1. Inizia con bit più a destra del moltiplicatore.

2. Se il bit di moltiplicatore è 1, aggiungere moltiplicando

3. Maiusc moltiplicando per 1

4. Sposta in bit successivo a moltiplicatore e tornare al punto 2.

Ed ecco un algoritmo di divisione:

1. Se divisore è più grande di dividendo, stop.

2. Mentre registro divisore è inferiore al registro dei dividendi, spostamento a sinistra.

3. Maiusc divisore registrati a destra di 1.

4. Sottrarre divisore registro dal registro dividendo e modificare il bit a 1 nel registro risultato al bit corrispondente al numero totale di spostamenti fatte al registro divisore.

5. ripartire dal Punto 1 con divisore registro in stato originale.

Naturalmente avrete bisogno di mettere in un assegno di divisione per 0, ma dovrebbe funzionare.

Questi algoritmi, naturalmente, sono solo per i numeri interi.

Answer 2

Il mio preferito di riferimento per cose come questa, disponibili in forma di libro:

http://www.hackersdelight.org/

Inoltre non si può andare male con TAOCP: http: // www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 3

Ecco un algoritmo di divisione: http: // www. prasannatech.net/2009/01/division-without-division-operator_24.html

presumo che stiamo parlando di int?

Se non c'è alcun supporto hardware, dovrete implementare la propria eccezione di divisione per zero.

(non ho avuto molta fortuna in fretta a trovare un algoritmo di moltiplicazione, ma io continuo a guardare se qualcun altro non trova uno).

Answer 4

Un semplice e algoritmi di moltiplicazione abbastanza performante per gli interi è russo contadino Moltiplicazione .

Per razionali, si potrebbe provare un binario citazione notazione , per il quale la divisione è più facile che al solito.

Answer 5

Si scopre che ho ancora qualche vecchio codice 68000 assembler per lungo moltiplicazione e divisione lunga. 68000 codice è abbastanza semplice e pulito, così dovrebbe essere facile da tradurre per il chip.

Il 68000 ha avuto moltiplicano e istruzioni dividere IIRC -. Penso che questi sono stati scritti come un esercizio di apprendimento

Ha deciso di appena messo il codice qui. Aggiunta commenti e, nel processo, risolto un 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

Tra l'altro - non ho mai fatto capire se è stato necessario per convertire tutto al positivo alla partenza. Se si sta attenti con le operazioni di scorrimento, che può essere in testa evitabile.

Answer 6

Per moltiplicare, aggiungere prodotti parziali dal spostato multiplicand ad un accumulatore se e solo se il bit corrispondente nel moltiplicatore è impostato. Spostamento multiplicand e moltiplicatore a fine ciclo, test moltiplicatore e 1 per vedere se oltre dovrebbe essere fatto.

Answer 7

I chip della serie Microchip PICmicro 16Fxxx non hanno una moltiplicazione o istruzione divisione. Forse alcuni dei morbida si moltiplicano e le routine di dividere morbide per esso può essere portato sul vostro MCU.

microcontrollori PIC Basic Math Metodi di moltiplicazione

microcontrollori PIC Basic Math Divisione Metodi

Anche il check-out "il metodo di Newton" per la divisione . Credo che il metodo dà la più piccola dimensione eseguibile di qualsiasi algoritmo di divisione che abbia mai visto, anche se la spiegazione fa sembrare più complicato di quanto non sia in realtà. Ho sentito che alcuni supercomputer Cray prime utilizzate il metodo di Newton per la divisione.