Un algorithme de division est un algorithme qui, étant donné deux entiers N et D (respectivement le numérateur et le dénominateur), calcule leur quotient et/ou leur reste , résu...
Worldlex WikiContenu en francaisLecture gratuite
algorithme qui, étant donné deux entiers N et D (respectivement le numérateur et le dénominateur), calcule leur quotient et/ou leur reste , résultat de la division euclidienne . Certains sont appliqués manuellement, tandis que d'autres sont utilisés dans la conception de circuits numériques et de logiciels.
Les algorithmes de division se répartissent en deux grandes catégories : la division lente et la division rapide. Les algorithmes de division lente produisent un chiffre du quotient final par itération. Parmi les exemples de division lente, on peut citer la division avec restauration , la division avec restauration non performante, la division sans restauration et la division SRT . Les méthodes de division rapide partent d'une approximation précise du quotient final et produisent deux fois plus de chiffres de ce quotient à chaque itération. Les algorithmes de Newton-Raphson et de Goldschmidt appartiennent à cette catégorie.
Des variantes de ces algorithmes permettent d'utiliser des algorithmes de multiplication rapides . Il en résulte que, pour les grands entiers, le temps de calcul nécessaire à une division est le même, à un facteur constant près, que celui nécessaire à une multiplication, quel que soit l'algorithme de multiplication utilisé.
de plus grand commun diviseur présenté dans les Éléments d'Euclide , Livre VII, Proposition 1, trouve le reste de la division de deux entiers positifs en utilisant uniquement des soustractions et des comparaisons :
la division euclidienne ) donne lieu à un algorithme de division complet, applicable aux nombres négatifs et positifs, utilisant des additions, des soustractions et des comparaisons :
algorithme sensible à la valeur de sortie ) et peut servir de spécification exécutable.
tuple[int, int] quotient: int = 0 remainder: int = 0 for _ in range(numerator): remainder += 1 if remainder == denominator: quotient += 1 remainder = 0 return quotient, remainder "
def divide_unsigned2 ( numerator : int , denominator : int ) -> tuple [ int , int ] quotient : int = 0 remainder : int = 0 for _ in range ( numerator ): remainder += 1 if remainder == denominator : quotient += 1 remainder = 0 return quotient , remainder
Notes
Les cas particuliers sont
et .
La variable quotientn'est jamais lue. Ainsi, même si ses affectations
Implémentation alternative sous forme de compteur Une machine à compteurs simple peut être basée sur l'implémentation alternative. Les instructions de la machine à compteurs sont
Z (n) : Remplacez r n par 0.
S (n) : Ajouter 1 à r n .
J (m, n, q) : Si r m = r n , sautez à la qème instruction ; sinon, passez à l'instruction suivante dans le programme.
Le programme de la machine de comptage est
division euclidienne est une forme abrégée de la division euclidienne, adaptée aux diviseurs à un chiffre. La méthode par quotients partiels (ou méthode du pendu ) est une forme moins efficace de la division euclidienne, mais potentiellement plus facile à appréhender. En autorisant la soustraction de multiples supplémentaires à chaque étape, on peut également développer une variante plus flexible de la division euclidienne.division euclidienne , divise N par D , plaçant le quotient dans Q et le reste dans R. Dans le pseudo-code suivant, toutes les valeurs sont traitées comme des entiers non signés.
où:
R j est le j -ième reste partiel de la division (R(0) := N(i) étape incluse)
B est la base (radix, généralement 2 en interne dans les ordinateurs et les calculatrices) .
q n − ( j + 1) est le chiffre du quotient en position n − ( j + 1 ), où les positions des chiffres sont numérotées de 0 (le moins significatif) à n − 1 (le plus significatif).
n représente le nombre de chiffres du quotient
D est le diviseur
Rétablir la division
La division de restauration opère sur des nombres fractionnaires à virgule fixe et dépend de l'hypothèse 0 < D < N .Convertissez le quotient suivant en l'ensemble de chiffres {0,1} :
Commencer:
1. Former le terme positif :
2. Masquer le terme négatif :
3. Soustraire :
registre à décalage pour les deux.)
Division SRT
La division SRT est une méthode de division courante dans de nombreuses implémentations de microprocesseurs . L'algorithme porte le nom de DW Sweeney ( IBM) , James E. Robertson ( Université de l'Illinois ) et KD Tocher ( Imperial College London) . Ils l'ont tous développé indépendamment, à peu près simultanément (publication en février 1957, septembre 1958 et janvier 1958 respectivement).
La division SRT est similaire à la division sans restauration, mais elle utilise une table de consultation basée sur le dividende et le diviseur pour déterminer chaque chiffre du quotient.
La différence la plus significative réside dans l'utilisation d'une représentation redondante pour le quotient. Par exemple, lors de l'implémentation de la division SRT en base 4, chaque chiffre du quotient est choisi parmi cinq possibilités : −2, −1, 0, +1 ou +2. De ce fait, le choix d'un chiffre du quotient n'a pas besoin d'être parfait ; les chiffres suivants peuvent corriger de légères erreurs. (Par exemple, les paires de chiffres du quotient (0, +2) et (1, −2) sont équivalentes, puisque fameux bogue de division en virgule flottante du processeur Intel Pentium d'origine était dû à une table de correspondance mal codée. Les processeurs Pentium utilisaient une table de 2048 cellules, dont 1066 devaient être renseignées ; or, les valeurs de cinq cellules étaient omises par erreur.
méthodes de division rapide
Division Newton-Raphson
La méthode de Newton-Raphson utilise la méthode de Newton pour trouver l' inverse de et multiplier cet inverse par pour trouver le
Les étapes de la division de Newton-Raphson sont :
Calculez une estimation de l'inverse du diviseur .
Calculer des estimations de plus en plus précises de l'inverse. C'est là qu'intervient la méthode de Newton-Raphson.
Calculez le quotient en multipliant le dividende par l'inverse du diviseur : .
Pour appliquer la méthode de Newton afin de trouver l'inverse de , il est nécessaire de trouver une fonction qui s'annule en . La fonction évidente est , mais l'itération de Newton-Raphson est inefficace pour cette fonction, car elle ne peut être calculée sans connaître au préalable l'inverse de (de plus, elle tente de calculer l'inverse exact en une seule étape, au lieu de permettre des améliorations itératives). Une fonction qui fonctionne est , pour laquelle l'itération de Newton-Raphson donne
Du point de vue du calcul, les expressions et ne sont pas équivalentes. Pour obtenir un résultat avec une précision de 2n bits en utilisant la seconde expression, il faut calculer le produit entre et avec une précision double de celle donnée ( n bits). En revanche, le produit entre et ne nécessite qu'une précision de n bits, car les n bits de poids fort (après la virgule binaire) de sont nuls.
Si l'erreur est définie comme , alors :
Cette élévation au carré de l'erreur à chaque itération – la convergence quadratique de la méthode de Newton-Raphson – a pour effet de doubler approximativement le nombre de chiffres exacts du résultat à chaque itération , une propriété qui devient extrêmement précieuse lorsque les nombres en jeu ont un grand nombre de chiffres (par exemple, dans le domaine des grands entiers). Cependant, cela signifie également que la convergence initiale de la méthode peut être relativement lente, surtout si l'estimation initiale est mal choisie.
estimation initiale
Pour le sous-problème du choix d'une estimation initiale , il est pratique d'appliquer un décalage binaire au diviseur D afin de le normaliser de sorte que 0,5 ≤ D ≤ 1. Appliquer le même décalage binaire au numérateur N garantit que le quotient reste constant. Une fois dans cet intervalle, une approximation polynomiale simple permet d'obtenir une estimation initiale.
L' approximation linéaire avec une erreur absolue minimale dans le pire des cas sur l'intervalle est :
Les coefficients de l' approximation linéaire sont déterminés comme suit. La valeur absolue de l'erreur est . Le minimum de la valeur absolue maximale de l'erreur est déterminé par le théorème d'équioscillation de Tchebychev appliqué à . Le minimum local de se produit lorsque , ce qui admet la solution . La fonction en ce minimum doit être de signe opposé à celle aux extrémités, c'est-à-dire . Les deux équations à deux inconnues ont une solution unique et , et l'erreur maximale est . En utilisant cette approximation, la valeur absolue de l'erreur sur la valeur initiale est inférieure à
La meilleure approximation quadratique de dans l'intervalle est
On choisit de rendre l'erreur égale à un polynôme de Tchebychev de première espèce du troisième ordre, mis à l'échelle, et on obtient une valeur absolue de l'erreur inférieure ou égale à 1/99. Cette amélioration est équivalente aux itérations de Newton-Raphson, pour un coût de calcul inférieur à une itération.
Il est possible de générer une approximation polynomiale de degré supérieur à 2, en calculant les coefficients à l'aide de l' algorithme de Remez . En contrepartie, l'estimation initiale nécessite davantage de cycles de calcul, mais on peut espérer réduire le nombre d'itérations de la méthode de Newton-Raphson.
Puisque la convergence de cette méthode est exactement quadratique, il s'ensuit que, à partir d'une erreur initiale , les itérations donneront une réponse précise à
Positions binaires. Les valeurs typiques sont :
Chiffres binaires d'exactitude réciproque
Itérations
0
1
2
3
4
la précision simple IEEE , mais trois itérations sont limites pour la double précision . Une estimation initiale linéaire suivie de quatre itérations est suffisante pour les formats double précision et double précision étendue .
Pseudocode
La formule suivante calcule le quotient de
// peut être précalculé en fonction d'un P fixe X := X + X × (1 - D' × X)
Le terme Y i ε i est nouveau.
En développant ce qui précède, on peut écrire :
avec pour résultat le terme d'erreur
Cette méthode représente les trois moitiés du calcul de l'itération quadratique, mais atteint la même convergence, ce qui la rend légèrement plus efficace. Autrement dit, deux itérations de cette méthode élèvent l'erreur à la puissance neuf pour un coût de calcul équivalent à celui de trois itérations quadratiques, qui ne l'élèvent qu'à la puissance huit.
Le nombre de bits corrects après itérations est
Positions binaires. Les valeurs typiques sont :
Bits de précision réciproque
Itérations
0
1
2
3
Les étapes de la division Goldschmidt sont les suivantes :
Générer une estimation du facteur de multiplication F i .
Multipliez le dividende et le diviseur par F i .
Si le diviseur est suffisamment proche de 1, renvoyez le dividende ; sinon, retournez à l'étape 1.
En supposant que N / D ait été mis à l'échelle de sorte que 0 < D < 1, chaque F i est basé sur D :
En multipliant le dividende et le diviseur par le facteur, on obtient :
Après un nombre suffisant k d'itérations .
La méthode de Goldschmidt est utilisée dans les processeurs AMD Athlon et les modèles ultérieurs. Également connue sous le nom d'algorithme Anderson Earle Goldschmidt Powers (AEGP), elle est implémentée par divers processeurs IBM . Bien qu'elle converge à la même vitesse qu'une implémentation de Newton-Raphson, la méthode de Goldschmidt présente l'avantage de permettre le parallélisme des multiplications au numérateur et au dénominateur.
Théorème du binôme
La méthode de Goldschmidt peut être utilisée avec des facteurs permettant des simplifications grâce au binôme de Newton . Supposons été multiplié par une puissance de deux telle que . Nous choisissons et . Ceci donne
.
Après erreur relative
qui est maximal lorsque , assurant ainsi une précision minimale des chiffres binaires.
méthodes pour les grands entiers
Les méthodes conçues pour une implémentation matérielle ne sont généralement pas adaptées aux entiers comportant des milliers ou des millions de décimales ; or, ces entiers sont fréquents, par exemple, dans les réductions modulaires en cryptographie . Pour ces grands entiers, des algorithmes de division plus efficaces ramènent le problème à un petit nombre de multiplications, lesquelles peuvent être effectuées à l'aide d'un algorithme de multiplication asymptotiquement efficace tel que l' algorithme de Karatsuba , la multiplication de Toom-Cook ou l' algorithme de Schönhage-Strassen . Il en résulte que la complexité de calcul de la division est du même ordre de grandeur (à une constante multiplicative près) que celle de la multiplication. On peut citer comme exemples la réduction à la multiplication par la méthode de Newton décrite précédemment , ainsi que la , la réduction de Barrett et les algorithmes de réduction de Montgomery . La méthode de Newton est particulièrement efficace dans les scénarios où il faut diviser plusieurs fois par le même diviseur, car après l'inversion initiale de Newton, une seule multiplication (tronquée) est nécessaire pour chaque division.inverse . Puisque le dénominateur est constant, son inverse (1/ D ) l'est également. Il est donc possible de calculer la valeur de (1/ D ) une seule fois, à la compilation, et d'effectuer la multiplication N · (1/ D ) à l'exécution plutôt que la division N/D . En arithmétique à virgule flottante, l'utilisation de (1/ D ) ne pose guère de problème , mais en arithmétique entière , l'inverse sera toujours égal à zéro (en supposant | D | > 1).
Il n'est pas nécessaire d'utiliser spécifiquement (1/ D ) ; toute valeur ( X / Y ) qui se réduit à (1/ D ) peut être utilisée. Par exemple, pour une division par 3, les facteurs 1/3, 2/6, 3/9 ou 194/582 peuvent être utilisés. Par conséquent, si Y était une puissance de deux, la division se réduirait à un décalage binaire rapide à droite. Calculer N / D comme ( N · X )/ Y revient à remplacer une division par une multiplication et un décalage. Notez que les parenthèses sont importantes, car N ·( X / Y ) sera égal à zéro.
Cependant, à moins que D ne soit lui-même une puissance de deux, il n'existe pas de X et Y qui satisfassent les conditions ci-dessus. Heureusement, ( N · X )/ Y donne exactement le même résultat que N / D en arithmétique entière, même lorsque ( X / Y ) n'est pas exactement égal à 1/ D , mais suffisamment proche pour que l'erreur introduite par l'approximation se situe dans les bits ignorés par l'opération de décalage. La réduction de Barrett utilise des puissances de 2 pour la valeur de Y afin de simplifier la division par Y en un simple décalage à droite.
À titre d'exemple concret d'arithmétique à virgule fixe , pour les entiers non signés de 32 bits, la division par 3 peut être remplacée par une multiplication par 2863311531/2 33 , une multiplication par 2863311531 ( hexadécimal 0xAAAAAAAB) suivie d'un décalage de 33 bits vers la droite. La valeur de 2863311531 est calculée comme OEIS fournit les séquences de constantes pour la multiplication sous la référence
Dans certains cas, la division par une constante peut être effectuée encore plus rapidement en convertissant la multiplication par une constante en une série de décalages et d'additions ou de soustractions . La division par 10 est particulièrement intéressante, car elle donne le quotient exact, avec le reste si nécessaire.
Erreur d'arrondi
quotient et le reste exacts sont approximés pour respecter les limites de précision de l'ordinateur. L'algorithme de division stipule :
Cet arrondi engendre une petite erreur, susceptible de se propager et de s'accumuler au fil des calculs. Ces erreurs sont particulièrement marquées dans les processus itératifs et lors de la soustraction de valeurs presque égales ; on parle alors de perte de signification . Pour atténuer ces erreurs, on utilise des techniques telles que l'ajout de chiffres de garde ou une précision plus élevée (ou une précision arbitraire ).
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Worldlex Wiki