Comment la division se produit-elle dans nos ordinateurs?

Comment la division se produit-elle à l'intérieur des ordinateurs numériques? Quel est l'algorithme pour cela?

J'ai cherché dur dans google mais je n'ai pas obtenu de résultats satisfaisants. Veuillez fournir un algorithme / organigramme très clair pour l'algorithme de division avec un exemple d'illustration.

Les algorithmes de division dans les conceptions numériques peuvent être divisés en deux catégories principales. Division lente et division rapide.

Je vous suggère de lire comment fonctionne l'addition et la soustraction binaires si vous n'êtes pas encore familier avec ces concepts.

Division lente

Les méthodes lentes les plus simples fonctionnent toutes de la manière suivante: Soustrayez le dénominateur du numérateur. Faites-le récursivement avec le résultat de chaque soustraction jusqu'à ce que le reste soit inférieur au dénominateur. La quantité d'itérations est le quotient entier, et la quantité restante est le reste.

Exemple:

7/3:

1. $$7-3=4$$
2. $$4-3=1$$
3. $$1 < 3$$

Ainsi, la réponse est 2 avec un reste de 1. Pour rendre cette réponse un peu plus pertinente, voici quelques informations. La soustraction binaire via l'addition du négatif est effectuée par exemple: 7 - 3 = 7 + (-3). Ceci est accompli en utilisant son complément à deux. Chaque nombre binaire est ajouté à l'aide d'une série d'additionneurs complets:

Où chaque additionneur complet 1 bit est implémenté comme suit:

Division rapide

Bien que la méthode de division plus lente soit facile à comprendre, elle nécessite des itérations répétitives. Il existe différents algorithmes "rapides", mais ils reposent tous sur une estimation.

Considérez la méthode Goldschmidt:

Cette méthode fonctionne comme suit:

1. Multipliez N et D par une fraction F de telle sorte que D approche 1.
2. Lorsque D approche 1, N approche Q

Cette méthode utilise la multiplication binaire via l'ajout itératif, qui est également utilisé dans les processeurs AMD modernes.

Le matériel pour la division en virgule flottante fait partie d'une unité logique qui effectue également la multiplication; un module matériel multiplicateur est disponible. Les nombres à virgule flottante, disons A et B, sont divisés (formant A / B) par

1. décomposer les nombres à virgule flottante en exposants de signe (+1 ou -1), de mantisse ("a" et "b" et (type entier binaire)
2. le signe du résultat est (+1) si les deux signes sont identiques, sinon (-1)
3. les exposants sont soustraits (exposant de B soustrait de l'exposant de A) pour former l'exposant du résultat

4. les mantisses (les chiffres binaires des nombres) sont un nombre binaire à virgule fixe compris entre 1/2 et 1; cela signifie que le premier chiffre après le point binaire est '1', suivi de zéros et de uns ... comme première étape, une table de recherche trouve la réciproque précise à six bits (il n'y a que 32 possibilités, c'est une petite table)

5. $${a \over b} = {{a * reciprocal(b)}\over b * reciprocal(b)}$$

6. $$d == 1 +\epsilon$$ $$d * (2-d) = ( 1+ \epsilon) \times (1-\epsilon) = 1 - \epsilon ^2$$
7. Le numérateur, maintenant que le dénominateur est exactement «1», est la mantisse du résultat, et peut être combiné avec le signe et l'exposant précédemment calculés.
8. La virgule flottante IEEE autorise certaines exceptions (nombres dénormalisés, NAN; celles-ci doivent être gérées par d'autres opérations logiques.

Fait intéressant, l'ancien bogue de division Pentium (très intéressant en 1994) a été causé par une erreur d'impression qui a rendu les valeurs de table réciproque erronées pour l'étape (4). Un premier article, "Une méthode de division utilisant un multiplicateur parallèle", Domenico Ferrari, IEEE Trans. Électron. Comput. EC-16 / 224-228 (1967), décrit la méthode, de même que "The IBM System / 360 Model 91: Floating-Point Execution Unit" IBM J. Res. Dev. 11 : 34 à 53 (1967).

Il existe des méthodes de division très différentes selon les nombres à traiter. Pour les entiers, la méthode shift-and-subtract donnée par d'autres fonctionnera bien. Pour les nombres à virgule flottante, cependant, il peut être plus rapide de calculer d'abord l'inverse du dénominateur, puis de multiplier ce nombre par votre numérateur.

Le calcul de l'inverse du dénominateur n'est pas si mal; cela se fait en affinant les approximations successives. Soit g votre estimation pour 1 / d. Pour une estimation améliorée, utilisez g '= g (2-gd). Cela converge quadratique, vous doublez donc les chiffres de précision à chaque amélioration.

Exemple: calculer l'inverse de 3,5.

Votre estimation initiale est de 0,3. Vous calculez 0,3 * 3,5 = 1,15. Votre estimation ajustée est de 0,3 * (2 - 1,15) = 0,285. Déjà assez proche! Répétez le processus et vous obtenez 0,2857125, et un troisième essai obtient 0,2857142857.

Il existe des raccourcis. En virgule flottante, vous pouvez extraire des puissances de dix ou des puissances de deux, selon la base numérique de votre machine. Et, pour la vitesse au détriment d'une plus grande utilisation de la mémoire, vous pouvez utiliser une table pré-calculée pour les nombres dans la plage de 1 à b (où b est votre base numérique) pour obtenir une estimation qui est immédiatement proche de la réciproque requise et enregistrer une ou deux étapes de raffinement.

Gardez à l'esprit que, comme pour la multiplication et l'embarras de Kolmogorov en 1960 par son élève Anatoly Karatsuba, vous ne savez jamais quand une méthode plus rapide ou meilleure sera trouvée. N'abandonnez jamais votre curiosité.

Les ordinateurs ne font pas d'ajout itératif pour multiplier les nombres - ce serait vraiment lent. Au lieu de cela, il existe des algorithmes de multiplication rapide. Consultez: http://en.wikipedia.org/wiki/Karatsuba_algorithm