Division 64/32 bits sur un processeur avec division 32/16 bits

Mon processeur, un petit microcontrôleur 16 bits sans FPU et integer math n'a que 16/16 de division et 32/16 de division qui prennent tous les deux 18 cycles. En ce moment j'utilise une routine logicielle très lente (~7500 cycles) pour faire la division 64/32. Y a-t-il un moyen d'utiliser ces moteurs de division pour calculer une division 64/32? Similaire à comment je suis déjà en utilisant le multiplicateur 16x16 et adder pour calculer 32x32 multiplies? J'utilise C mais peut travailler avec n'importe quelle explication générale sur la façon dont il peut être fait... J'espère cibler moins de 200 cycles (si c'est possible.)

19
demandé sur Thomas O 2011-01-23 04:52:29

4 réponses

Voir Hacker "Plaisir", groupe de mots de la division (pages 140-145).

le concept de base (retourner à Knuth) est de penser à votre problème en termes de base-65536. Alors vous avez un problème de division à 4 chiffres par 2 chiffres, avec une division à 2/1 chiffres comme primitive.

Le code C est ici: http://www.hackersdelight.org/hdcodetxt/divmnu.c.txt

11
répondu payne 2012-12-28 21:37:23

ma copie de Knuth (L'Art De La Programmation informatique) est au travail, donc je ne peux pas la vérifier avant lundi, mais ce serait ma première source. Il a toute une section sur l'arithmétique.

edit: votre post sur " la division 16/16 et la division 32/16 qui toutes deux prennent 18 cycles."-- les dsPICs ont une opération de soustraction conditionnelle dans l'assemblage. Envisagez d'utiliser ceci comme votre primitive computationnelle.

notez aussi que si X = XH * 2 32 + XL et D = DH * 2 16 + DL, alors si vous êtes à la recherche pour

(Q, R) = X / D où X = Q * D + R

OÙ Q = QH * 2 16 + QL, R= RH * 2 16 + RL, then

XH * 2 32 + XL = DH * QH * 2 32 + (DL * QH + DH * QL) * 2 16 + (DL * QL) + RH * 2 16 + RL

ceci suggère (en regardant les termes qui sont les 32 bits élevés) d'utiliser la procédure suivante, semblable à long division:

  1. (QH, R0) = XH / (DH+1) -> XH = QH * (DH+1) + R0 [32/16 divide]
  2. R1 = X - (QH * 2 16) * D [nécessite une multiplication 16*32, un décalage-gauche par 16, et une soustraction 64 bits]
  3. calculer R1' = R1-D * 2 16
  4. alors que R1' >= 0, ajuster QH vers le haut par 1, Mettre R1 = R1', et passer à l'étape 3
  5. (QL, R2) = (R1 >> 16) / (DH+1) -> R1 = QL * (DH+1) + R2 [32/16 diviser]
  6. R3 = R1 - (QL * D) [nécessite une multiplication de 16*32 et une soustraction de 48 bits]
  7. calculer R3' = R3-D
  8. alors que R3 '> = 0, ajuster QL vers le haut par 1, Mettre R3 = R3', et passer à l'étape 7

votre quotient 32 bits est la paire (QH, QL), et le reste 32 bits est R3.

(Ce qui suppose que le quotient n'est pas plus grand que 32-bit, vous devez savoir à l'avance, et peut facilement vérifier à l'avance.)

4
répondu Jason S 2011-01-23 15:32:48

point de départ:: D. Knuth, The Art of Computer Programming Vol.2, Section 4.3.1, Algorithme D

mais je suppose que vous pourriez avoir besoin d'optimiser l'algorithme.

1
répondu bestsss 2011-01-23 04:14:35

Vous pouvez regarder Booth's Algorithm (http://www.scribd.com/doc/3132888/Booths-Algorithm-Multiplication-Division).

La partie que vous voulez est d'environ 1/2 bas de la page.

je n'ai pas regardé ce depuis mon VLSI classe, mais, cela peut être votre meilleur pari, si possible, vous pouvez le faire dans une assemblée, afin d'optimiser autant que possible, si vous appelez souvent.

implique essentiellement le déplacement et l'addition ou la soustraction.

1
répondu James Black 2011-01-23 04:23:06