Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System

Valerie Berthe 1 Laurent Imbert 2, 1, *
* Auteur correspondant
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A partition of $x > 0$ of the form $x = \sum_i 2^{a_i}3^{b_i}$ with distinct parts is called a double-base expansion of $x$. Such a representation can be obtained using a greedy approach, assuming one can efficiently compute the largest \mbox{$\{2,3\}$-integer}, i.e., a number of the form $2^a3^b$, less than or equal to $x$. In order to solve this problem, we propose an algorithm based on continued fractions in the vein of the Ostrowski number system, we prove its correctness and we analyse its complexity. In a second part, we present some experimental results on the length of double-base expansions when only a few iterations of our algorithm are performed.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.153-172
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00374066
Contributeur : Laurent Imbert <>
Soumis le : mardi 3 juin 2014 - 15:25:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : mercredi 3 septembre 2014 - 10:35:45

Fichier

1011-4184-2-PB.pdf
Accord explicite pour ce dépôt

Identifiants

  • HAL Id : lirmm-00374066, version 1

Collections

Citation

Valerie Berthe, Laurent Imbert. Diophantine Approximation, Ostrowski Numeration and the Double-Base Number System. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, 11 (1), pp.153-172. 〈lirmm-00374066〉

Partager

Métriques

Consultations de la notice

184

Téléchargements de fichiers

295