Frougny
Le Jeudi 6 Décembre 2001 à 14h30
au LRI,
Salle 101
(LIAFA et Université Paris 8)
Calculs en ligne en base non entière
Résumé/Abstract :
L'arithmétique en ligne est un mode de calcul ou les opérandes
et les résultats circulent séquentiellement en commençant
par les poids forts (c'est-à-dire de la gauche vers la droite).
Cette technique permet de pipeliner additions/soustractions et multiplications
avec les divisions.
C'est aussi particulièrement intéressant pour le traitement des
nombres réels, dont la représentation est infinie à droite.
On sait que pour réaliser les opérations arithmétiques en
ligne, il est nécessaire d'utiliser une représentation des nombres
qui est redondante.
Dans cet exposé nous considérons le cas où la base
est un nombre réel, en général non entier. Tout nombre
réel est représentable au moyen d'un algorithme glouton en base
,
et les chiffres sont alors éléments de
A =
{0,1,...,[]}.
Nous étudions la conversion d'un alphabet de chiffres D vers
A,
ce qui généralise l'addition et la multiplication par un entier
fixe. Nous donnons un algorithme en ligne qui réalise cette conversion.
Quand est un nombre de Pisot (par exemple le nombre d'or),
la conversion est réalisable par un automate fini en ligne.
Nous donnons aussi un algorithme en ligne qui réalise la multiplication
de deux réels représentés en base .