Arithmétique multiprécision | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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 .

À propos de ce résultat

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.

Publications associées (4)

Concepts associés (65)

Cours associés (11)

Séances de cours associées (140)

Covariance Estimation for Random Surfaces beyond Separability

Tomas Masák

This thesis focuses on non-parametric covariance estimation for random surfaces, i.e.~functional data on a two-dimensional domain. Non-parametric covariance estimation lies at the heart of functional

EPFL2022

Defect of characters of the symmetric group

Following the work of B. Kulshammer, J. B. Olsson and G. R. Robinson on generalized blocks of the symmetric groups, we give a definition for the l-defect of characters of the symmetric group G(n), whe

De Gruyter2009

In an article of 2003, Kulshammer, Olsson, and Robinson defined l-blocks for the symmetric groups, where l is an arbitrary integer, and proved that they satisfy an analogue of the Nakayama Conjecture.

Taylor & Francis2008

Dépassement d'entier

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.

Nombre réel

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.

Arithmétique multiprécision

CS-208: Computer architecture I

The course introduces the students to the basic notions of computer architecture and, in particular, to the choices of the Instruction Set Architecture and to the memory hierarchy of modern systems.

CS-550: Formal verification

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

EE-431: Advanced VLSI design

In this project-based course, students collect hands-on experience with designing full-custom digital VLSI circuits in dynamic logic. They learn to carry out the design and optimization on transistor

Nombres de points flottants : représentation et erreurs

Introduit la représentation des nombres en virgule flottante, les erreurs d'arrondi et leur impact sur les calculs numériques.

Transients hydrauliques des turbines: modélisation hydroacoustique

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.

Arithmétique de l'ordinateur: Opérations de points flottants

Couvre les bases de l'arithmétique informatique, en se concentrant sur les nombres de points flottants et leurs opérations.