Dove posso trovare soft-moltiplicano e algoritmi divide?
-
24-09-2019 - |
Domanda
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.
Soluzione
Ecco un algoritmo di moltiplicazione semplice:
-
Inizia con bit più a destra del moltiplicatore.
-
Se il bit di moltiplicatore è 1, aggiungere moltiplicando
-
Maiusc moltiplicando per 1
-
Sposta in bit successivo a moltiplicatore e tornare al punto 2.
Ed ecco un algoritmo di divisione:
-
Se divisore è più grande di dividendo, stop.
-
Mentre registro divisore è inferiore al registro dei dividendi, spostamento a sinistra.
-
Maiusc divisore registrati a destra di 1.
-
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.
-
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.
Altri suggerimenti
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
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).
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.
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.
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.
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.