Retenue (arithmétique)

En arithmétique élémentaire, une retenue est un chiffre qui est transféré d’une colonne de chiffres à une autre colonne de chiffres plus significatifs. Il fait partie de l’algorithme standard qui consiste à additionner les nombres en commençant par les chiffres les plus à droite et en progressant vers la gauche. Par exemple, lorsque 6 et 7 sont ajoutés pour faire 13, le « 3 » est écrit dans la même colonne et le « 1 » est transféré en retenue dans la colonne immédiatement à gauche. Lorsqu’elle est utilisée en soustraction, l’opération est appelée emprunt.

La retenue fait aussi quelques apparitions en mathématiques supérieures. En informatique, la retenue est une fonction importante des circuits additionneurs.

Calcul manuel

Exemple : addition de deux nombres entiers, générant deux retenues

Un exemple typique de retenue est l'addition suivante avec papier et crayon : 

  1
  27
+ 59
----
  86

7 + 9 = 16, et le chiffre 1 est la retenue.

Lors d'une soustraction, l'opposé est un emprunt, comme dans 

 −1
  47
− 19
----
  28

Ici, 7 − 9 = −2, on pose (10 − 9) + 7 = 8 et le 10 est obtenu en retirant ("empruntant") 1 du chiffre suivant à gauche. Il existe deux façons courantes d'enseigner cette technique :

  1. Le dix est déplacé depuis le chiffre suivant à gauche, laissant dans cet exemple 3 − 1 dans la colonne des dizaines. Avec cette méthode, le terme "emprunt" est un terme abusif, car le dix n'est jamais "remboursé".
  2. Le dix est copié depuis le chiffre suivant à gauche, puis 'remboursé' en l'ajoutant au nombre à soustraire de la colonne d'où il a été 'emprunté', laissant dans cet exemple 4 − (1 + 1) dans la colonne des dizaines.

Mathématiques supérieures

Le théorème de Kummer stipule que le nombre de retenues impliquées dans l'addition de deux nombres en base est égal à l'exposant de la puissance la plus élevée de divisant un coefficient binomial donné.

Lorsque plusieurs nombres aléatoires à grand nombre de chiffres sont ajoutés, la statistique des chiffres de retenue présente un lien inattendu avec les nombres eulériens et les statistiques de permutation (p, q)-shuffle[1],[2],[3],[4].

En algèbre générale, l'opération de retenue pour des nombres à deux chiffres peut être formalisée en utilisant le langage d'homologie des groupes[5],[6],[7]. Ce point de vue peut être appliqué à des caractérisations alternatives des nombres réels[8],[9].

Calculatrices mécaniques

La retenue représente l’un des défis fondamentaux auxquels sont confrontés les concepteurs et constructeurs de calculatrices mécaniques. Ils rencontrent deux difficultés de base : la première vient du fait qu’une retenue peut nécessiter la modification de plusieurs chiffres : pour ajouter 1 à 999, la machine doit incrémenter 4 chiffres différents. Un autre défi est que la retenue peut « se développer » avant que le chiffre suivant ne termine l’opération d’addition.

La plupart des calculatrices mécaniques implémentent la retenue en exécutant un cycle de retenue séparé après l’addition elle-même. Lors de l’addition, chaque retenue est « signalée » plutôt qu’effectuée, et pendant le cycle de retenue, la machine incrémente les chiffres au-dessus des chiffres « déclenchés ». Cette opération doit être effectuée séquentiellement, en commençant par le chiffre des unités, puis des dizaines, des centaines, et ainsi de suite, car l’ajout de la retenue peut générer une nouvelle retenue dans le chiffre suivant.

Certaines machines, notamment la Pascaline, la deuxième calculatrice connue à avoir été construite, et la plus ancienne encore existante, utilisent une méthode différente : incrémenter le chiffre de 0 à 9, armer un dispositif mécanique pour stocker l’énergie, et l’incrément suivant, qui fait passer le chiffre de 9 à 0, libère cette énergie pour augmenter le chiffre suivant de 1. Pascal utilisait des poids et la gravité dans sa machine. Une autre machine notable utilisant une méthode similaire est le très réussi Comptomètre du XIXe siècle, qui a remplacé les poids par des ressorts.

Certaines machines innovantes utilisent la transmission continue : ajouter 1 à n'importe quel chiffre fait avancer le suivant de 1/10 (ce qui à son tour fait avancer le suivant de 1/100, et ainsi de suite). Certaines calculatrices innovantes primitives, notamment la calculatrice Tchebychev de 1870[10], et un design de Selling[11] de 1886, utilisaient cette méthode, mais aucune ne fut couronnée de succès. Au début des années 1930, la calculatrice Marchant (en) a mis en place la transmission continue avec un grand succès, en commençant par la calculatrice nommée à juste titre « Silent Speed ». Marchant (qui deviendra plus tard SCM Corporation) a continué à l’utiliser et à l’améliorer, et a fabriqué des calculatrices à transmission continue à une vitesse inégalée, jusqu’à la fin des années 1960, jusqu’à la fin de l’ère des calculatrices mécaniques.

Informatique

Lorsqu’on considère un circuit logique comme un additionneur, le mot retenue est utilisé dans un sens similaire.

Dans la plupart des ordinateurs, la retenue (ou report) du bit le plus significatif d’une opération arithmétique (ou du bit décalé lors d’une opération de décalage) est placé dans un bit de retenue spécial qui peut servir de retenue pour l'arithmétique multiprécision ou être testé pour contrôler l’exécution d’un programme informatique. Le même bit de retenue est aussi généralement utilisé pour indiquer des emprunts en soustraction, bien que le sens du bit soit inversé en raison des effets de l’arithmétique en complément à deux. Normalement, une valeur de bit de retenue à « 1 » signifie qu’une addition a dépassé les capacités de l'ALU, et doit être prise en compte lors de l’ajout de mots de données de longueur supérieure à celle du CPU. Pour les opérations de soustraction, deux conventions (opposées) sont employées : la plupart des processeurs activent (mettent à un) l'indicateur de retenue en emprunt tandis que certains autres (comme le 6502 et le PIC) réinitialisent (mettent à zéro) l’indicateur de retenue en emprunt (et inversement).

Un report peut entraîner un dépassement d'entier.

Références

  1. ↑ (en) John M. Holte, « Carries, Combinatorics, and an Amazing Matrix », The American Mathematical Monthly, vol. 104, no 2,‎ , p. 138–149 (DOI 10.2307/2974981, JSTOR 2974981)
  2. ↑ (en) Persi Diaconis et Jason Fulman, « Carries, shuffling, and symmetric functions », Advances in Applied Mathematics, vol. 43, no 2,‎ , p. 176–196 (DOI 10.1016/j.aam.2009.02.002, arXiv 0902.0179)
  3. ↑ (en) Alexei Borodin, Persi Diaconis et Jason Fulman, « On adding a list of numbers (and other one-dependent determinantal processes) », Bulletin of the American Mathematical Society, vol. 47, no 4,‎ , p. 639–670 (DOI 10.1090/S0273-0979-2010-01306-9, arXiv 0904.3740)
  4. ↑ (en) Fumihiko Nakano et Taizo Sadahiro, « A generalization of carries processes and Eulerian numbers », Advances in Applied Mathematics, vol. 53,‎ , p. 28–43 (DOI 10.1016/j.aam.2013.09.005 Accès libre)
  5. ↑ (en) M. Hegland et W. W. Wheeler, « Linear Bijections and the Fast Fourier Transform », Applicable Algebra in Engineering, Communication and Computing, vol. 8, no 2,‎ , p. 143–163 (DOI 10.1007/s002000050059, S2CID 17603981)
  6. ↑ (en) Daniel C. Isaksen, « A Cohomological Viewpoint on Elementary School Arithmetic », The American Mathematical Monthly, vol. 109, no 9,‎ , p. 796–805 (DOI 10.2307/3072368, JSTOR 3072368, lire en ligne, consulté le )
  7. ↑ (en) Alexandre V. Borovik, Mathematics under the Microscope: Notes on Cognitive Aspects of Mathematical Practice, AMS, , 87–88 p. (ISBN 978-0-8218-4761-9)
  8. ↑ (en) N. Metropolis, Rota Gian-Carlo et S. Tanny, « Significance Arithmetic: The Carrying Algorithm », Journal of Combinatorial Theory, vol. 14, no 3,‎ , p. 386–421 (DOI 10.1016/0097-3165(73)90013-7 Accès libre)
  9. ↑ (en) F. Faltin, N. Metropolis, B. Ross et G.-C. Rota, « The Real Numbers as a Wreath Product », Advances in Mathematics, vol. 16, no 3,‎ , p. 278–304 (DOI 10.1016/0001-8708(75)90115-2 Accès libre)
  10. ↑ (en) Denis Roegel, « Chebyshev's continuous adding machine », sur locomat.loria.fr, (consulté le )
  11. ↑ (en) Martin Ernst, The Calculating Machines, Charles Babbage Institute, , 96 p. (lire en ligne)
  • icône décorative Portail des mathématiques
  • icône décorative Portail de l’informatique
Cet article est issu de Wikipédia. Sauf mention contraire, le texte est disponible sous Creative Commons Attribution-Share Alike 4.0. Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.