Algorithme de stand-wikipedia

Le Algorithme de boooth est un algorithme pour la multiplication de deux nombres en deux affichages de complément. Il a été développé en 1951 par Andrew Donald Booth lorsqu’il a travaillé sur la cristallographie sur le Birkbeck College.

• Est x le nombre de bits du multiplicande et du nombre de bit du multiplicateur.
• Dessiner une grille à trois courants avec
  ${displaystyle x + y + 1}$

  Colonnes. Décrivez les lignes avec A (addition), S (soustraction) et P (produit).

• Notez les premiers bits de chaque ligne comme suit:
  • R: Multiplikand
  • S: Multiplicand nié (en deux complément)
  • P: Zéros
• Les bits Y suivants de chaque ligne doivent être remplis comme suit:
  • R: Zéros
  • S: Zéros
  • P: Multiplicateur
• La dernière colonne est remplie de zéros.
• Faites les deux étapes suivantes y fois:
  1. Sont les deux derniers bits de P
     • 00 ou 11: Ne faites rien
     • 01
       ${displaystyle P=P+A}$

       . Ignorez tout débordement.

     • dix
       ${displaystyle P=P+S}$

       . Ignorez tout débordement.

  2. Poussez le produit arithmétiquement par une position vers la droite.
• À l’avant
  ${displaystyle x + y}$

  Les bits sont maintenant le produit (le dernier bit est ignoré).

On est informé que chaque numéro B peut être représenté comme une différence entre deux nombres C et D:

${DisplayStyle {Mbox {SEI}} b = c-d}$

Ensuite, toute multiplication de B peut être convertie avec un facteur A comme suit:

${displayStyle acdot b = acdot (c-d) = acdot c-acdot d}$

Cette méthode offre des avantages par rapport à la méthode “papier et crayon” pour les nombres qui ont de longues chaînes de bits équivalents dans la présentation binaire. Celles-ci sont “ignorées” dans le processus de stand. Sur cette base, la procédure de stand permet également une multiplication efficace pour les nombres binaires dans le complément bidirectionnel, c’est-à-dire H. L’algorithme a l’avantage que les signes des deux facteurs ne doivent pas être pris en compte.

Exemple [ Modifier | Modifier le texte source ]]

Will mec

${DisplayStyle 30_ {10} = 00011110_ {2}}}$

Multipliez avec un nombre x, la méthode traditionnelle avait besoin de trois ajouts:

${displayStyle 10_ {2} cdot x + 100_ {2} cdot x + 1000_ {2} cdot x + 10000_ {2} cdot x}$

.
La procédure de stand, en revanche, n’en a besoin qu’une:

${displayStyle 100000_ {2} cdot x-10_ {2} cdot x}$

.

La soustraction peut être attendue dans le complément bidirectionnel comme un ajout, la multiplication avec un multiple de 2 ne correspond qu’à un changement dans les endroits vers la gauche (chirurgie de changement). La procédure est donc utilisée pour une multiplication efficace dans les ordinateurs.

L’algorithme de stand offre un moyen efficace de déterminer le codage à utiliser dans un numéro correspondant. Vous marchez de droite à gauche à travers le numéro binaire. La position binaire passe de la dernière à la position actuelle de
0 Après 1, A -1, en passant de 1 à 0 A +1 et aucun changement n’est défini. Dans la première étape, un 0 est pensé au nombre à droite.

Multipliquer

${DisplayStyle 44_ {10} = (0010111) _ {2}}$

et

${DisplayStyle 17_ {10} = (00010001) _ {2}}$

Codage d’un facteur selon le stand [ Modifier | Modifier le texte source ]]

Étape 1	0	d’abord	0	d’abord	d’abord	0	0	0
							0
étape 2	0	d’abord	0	d’abord	d’abord	0	0	0
						0	0
étape 3	0	d’abord	0	d’abord	d’abord	0	0	0
					-d’abord	0	0
Étape 4	0	d’abord	0	d’abord	d’abord	0	0	0
				0	−1	0	0
Étape 5	0	d’abord	0	d’abord	d’abord	0	0	0
			+1	0	−1	0	0
Étape 6	0	d’abord	0	d’abord	d’abord	0	0	0
		-d’abord	+1	0	−1	0	0
Étape 7	0	d’abord	0	d’abord	d’abord	0	0	0
	+1	−1	+1	0	−1	0	0

Officiel: L’opérande à coder au moyen d’un stand

${DisplayStyle y = (y_ {n-1}, points, y_ {0})}$

Si vous ajoutez un autre “lieu”

${displaystyle y _ {- 1}}$

sur cela est défini sur zéro. Les autres endroits

${displayStyle {y ‘} _ {i}, iin gauche {0, points, n-1Right}}$

du nouveau

${DisplayStyle et ‘: = (et’ _ {n-1}, dots et ‘_ {0} et _ {-1})}$

sont calculés comme suit:

${DisplayStyle {y ‘} _ {i} = y_ {i-1} -y_ {i} forall iin {0, dots, n-1}}}}}}$

.

multiplication [ Modifier | Modifier le texte source ]]

									0	0	0	d’abord	0	0	0	d’abord	2. Facteurs
X									0	+1	−1	+1	0	−1	0	0	Codage du 1er facteur
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	pas d’ajout
+		0	0	0	0	0	0	0	0	0	0	0	0	0	0		pas d’ajout
+		d’abord	d’abord	d’abord	d’abord	d’abord	d’abord	d’abord	d’abord	0	d’abord	d’abord	d’abord	d’abord			Complément 2er (2e facteur)
+		0	0	0	0	0	0	0	0	0	0	0	0				pas d’ajout
+		0	0	0	0	0	0	d’abord	0	0	0	d’abord					2. Facteurs
+		d’abord	d’abord	d’abord	d’abord	d’abord	0	d’abord	d’abord	d’abord	d’abord						Complément 2er (2e facteur)
+		0	0	0	0	d’abord	0	0	0	d’abord							2. Facteurs
+		0	0	0	0	0	0	0	0								pas d’ajout
d’abord	0	0	0	0	0	0	d’abord	0	d’abord	d’abord	d’abord	0	d’abord	d’abord	0	0	Résultat sans débordement

Au lieu de se multiplier avec 0100000, 0001000 et 0000100 et en ajoutant les résultats, il est désormais multiplié par 1000000, 0100000, 0010000 et 0000100 et les résultats s’additionnent ou soustraits en conséquence.

Comme vous pouvez le voir en utilisant l’exemple, le nombre d’ajouts peut également augmenter (dans l’exemple de 3 à 4), ce qui n’est pas actuellement souhaitable. Dans la moyenne statistique, car de nombreux ajouts sont nécessaires dans le processus de stand comme sans procédure de stand. Cependant, l’avantage est qu’il n’y a pas de distribution égale des nombres en informatique. Il y a plutôt des chiffres souvent avec de nombreux zéros et, grâce au complément à deux voies en nombre négatif, beaucoup souvent au début. Ce n’est que par ce fait que le processus de stand a des avantages par rapport à la multiplication normale.

L’expansion de la procédure de stand est la procédure de paire de bits, dans laquelle deux endroits sont toujours résumés.