L'arithmétique multiprécision désigne l'ensemble des techniques mises en œuvre pour manipuler dans un programme informatique des nombres (entiers, rationnels, ou flottants principalement) de taille arbitraire. Il s'agit d'une branche de l'arithmétique des ordinateurs.
On oppose l'arithmétique multi-précision à l'arithmétique en simple ou double précision, comme celle spécifiée par le standard IEEE 754 pour les nombres flottants. En effet, l'arithmétique simple ou double précision ne s'occupe que des nombres de 32 ou 64 bits, pour lesquels les opérations de base sont fournies par le processeur, alors que l'arithmétique multiprécision s'occupe des opérations sur des quantités de taille (nombre de chiffres) quelconque, pour lesquelles la seule limite est celle de la mémoire disponible.
De nombreux algorithmes ont été développés pour effectuer efficacement les opérations usuelles sur des nombres comportant un très grand nombre de chiffres ; nous en donnons quelques-uns, ainsi que leurs complexités, qui s'expriment en fonction de n, le nombre de chiffres des quantités manipulées.
L'addition de deux nombres à n chiffres peut se faire en O(n) opérations avec une méthode naïve. Ce coût est asymptotiquement négligeable par rapport aux autres coûts, et est donc fréquemment négligé.
Algorithme de multiplication
Les algorithmes de multiplication rapide de grands entiers sont au cœur de ce domaine. En effet, de nombreuses opérations plus complexes, à commencer par la division, utilisent la multiplication d'entiers comme brique de base, et l'efficacité des algorithmes utilisés repose de façon essentielle sur celle de la multiplication sous-jacente. On note le coût de la multiplication de deux nombres à n chiffres.
Plusieurs méthodes améliorent la complexité de cette opération par rapport à la méthode de base ("poser une multiplication"). Les plus avancées sont l'algorithme de Schönhage-Strassen, qui donne , et l'algorithme de Fürer, qui donne .
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
We introduce formal verification as an approach for developing highly reliable systems. Formal verification finds proofs that computer systems work under all relevant scenarios. We will learn how to u
Introduction aux phénomènes propagatifs dans les circuits hydrauliques, calculs de coups de béliers, comportement transitoire d'aménagements hydroélectriques, simulation numériques 1D du comportement
Mettre en pratique les bases de la programmation vues au semestre précédent. Développer un logiciel structuré. Méthode de debug d'un logiciel. Introduction à la programmation scientifique. Introductio
Situational awareness strategies are essential for the reliable and secure operation of the electric power grid which represents critical infrastructure in modern society. With the rise of converter-interfaced renewable generation and the consequent shift ...
vignette|Le vol 501 d'Ariane 5 en 1996 s'est soldé par sa destruction en raison d'un dépassement d'entier. Un dépassement d'entier (integer overflow) est, en informatique, une condition qui se produit lorsqu'une opération mathématique produit une valeur numérique supérieure à celle représentable dans l'espace de stockage disponible. Par exemple, l'ajout d'une unité au plus grand nombre pouvant être représenté entraîne un dépassement d'entier. Le dépassement d'entier porte le numéro CWE-190 dans la nomenclature Common Weakness Enumeration.
En mathématiques, un nombre réel est un nombre qui peut être représenté par une partie entière et une liste finie ou infinie de décimales. Cette définition s'applique donc aux nombres rationnels, dont les décimales se répètent de façon périodique à partir d'un certain rang, mais aussi à d'autres nombres dits irrationnels, tels que la racine carrée de 2, π et e.
En informatique, une représentation d'un nombre en virgule fixe est un type de donnée correspondant à un nombre qui possède (en base deux ou en base dix) un nombre fixe de chiffres après la virgule. Les nombres en virgule fixe sont utiles pour représenter des quantités fractionnaires dans un format utilisant le complément à deux quand le processeur de l'ordinateur n'a aucune unité de calcul en virgule flottante ou quand une virgule fixe permet d'augmenter la vitesse d'exécution ou d'améliorer l'exactitude des calculs.
Explore la modélisation, la stabilité et le développement historique des turbines hydrauliques, en mettant l'accent sur les critères de sélection des turbines Francis.
We prove a sharp quantitative version of the Faber–Krahn inequality for the short-time Fourier transform (STFT). To do so, we consider a deficit which measures by how much the STFT of a function fails to be optimally concentrated on an arbitrary set of pos ...
We initiate the study of certain families of L-functions attached to characters of subgroups of higher-rank tori, and of their average at the central point. In particular, we evaluate the average of the values L( 2 1 , chi a )L( 21 , chi b ) for arbitrary ...