Où puis-je trouver soft-multiplier et diviser des algorithmes?

Question

Je travaille sur un micro-contrôleur sans multiplier le matériel et diviser. Je dois cuisiner des algorithmes logiciels pour ces opérations de base qui sont un bon équilibre de taille compacte et d'efficacité. Mon C port compilateur utilisera ces algos, pas les développeurs C eux-mêmes.

Mon google-fu est si loin vers le haut tourne essentiellement du bruit sur ce sujet.

Quelqu'un peut-il me montrer quelque chose d'information? Je peux utiliser ajouter / sous et changer les instructions. Table de recherche algos à base peuvent aussi travailler pour moi, mais je suis un peu inquiet de bachotage tant en arrière-plan du compilateur ... euh, pour ainsi dire.

Answer 1

Voici un simple algorithme de multiplication:

1. Commencez par bit du multiplicateur extrême droite.

2. Si le bit dans le multiplicateur est 1, ajouter multiplicande

3. Maj multiplicande par 1

4. Déplacer à bit suivant dans le multiplicateur et revenir à l'étape 2.

Et voici un algorithme de division:

1. Si le diviseur est supérieur à dividende, arrêter.

2. Alors que le registre de diviseur est inférieur à registre de dividende, décalage vers la gauche.

3. registre à décalage à droite du diviseur par 1.

4. Soustraire registre de diviseur de registre de dividende et de changer le bit à 1 dans le registre de résultat dans le bit qui correspond au nombre total de déplacements effectués au registre de diviseur.

5. Recommencer à l'étape 1 avec registre de diviseur en état d'origine.

Bien sûr, vous aurez besoin de mettre un chèque de division par 0, mais il devrait fonctionner.

Ces algorithmes, bien sûr, ne sont que pour les entiers.

Answer 2

Ma référence préférée pour des choses comme celle-ci, disponible sous forme de livre:

http://www.hackersdelight.org/

Vous pouvez également ne pas vous tromper avec TAOCP: http: // www-cs-faculty.stanford.edu/~uno/taocp.html

Answer 3

Voici un algorithme de division: http: // www. prasannatech.net/2009/01/division-without-division-operator_24.html

Je suppose que nous parlons ints?

S'il n'y a pas de support matériel, vous devrez mettre en œuvre votre propre exception de division par zéro.

(je ne l'ai pas eu beaucoup de chance de trouver rapidement un algorithme de multiplication, mais je vais continuer à chercher si quelqu'un d'autre ne trouve pas).

Answer 4

Un simple et algorithme de multiplication pour les entiers assez performant est paysan russe multiplication.

Pour rationals, vous pouvez essayer un binaire citation notation , pour laquelle la division est plus facile que d'habitude.

Answer 5

Il se trouve que j'ai encore un peu ancien code 68000 assembleur pour une longue multiplication et division. le code 68000 est assez propre et simple, devrait donc être facile à traduire pour votre puce.

Le 68000 avait multiplier et diviser des instructions IIRC -. Je pense que ces écrits ont été comme un exercice d'apprentissage

Nous avons décidé de mettre tout le code ici. Ajout de commentaires et, dans le processus, fixe un problème.

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

Par ailleurs - je ne l'ai fait figure savoir s'il était nécessaire de convertir tout en positif au début. Si vous faites attention avec les opérations de changement de vitesse, qui peuvent être en tête évitable.

Answer 6

Pour multiplier, additionner des produits partiels à partir du multiplicande décalé vers un accumulateur ssi le bit correspondant dans le multiplicateur est défini. Maj multiplicande et le multiplicateur à la fin de la boucle, le multiplicateur de test et 1 pour voir si devrait se faire plus.

Answer 7

Les puces de la série Microchip PICmicro 16Fxxx ne possèdent pas de multiplier ou diviser instruction. Peut-être quelques-unes des routines se multiplient doux et divisent les doux car il peut être porté à votre MCU.

PIC Microcontroller mathématiques de base Méthodes multiplications

PIC Microcontroller Division de base mathématiques Méthodes

Consultez également "méthode de Newton" pour la division . Je pense que cette méthode donne la plus petite taille de l'exécutable d'un algorithme de division que j'ai jamais vu, même si l'explication rend le son plus compliqué qu'il ne l'est vraiment. J'entends que certains des premiers supercalculateurs Cray utilisé la méthode de Newton pour la division.