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

* 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

Littérature citée [27 références]

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00374066
Contributeur : Laurent Imbert <>
Soumis le : mardi 3 juin 2014 - 15:25:06
Dernière modification le : mardi 11 décembre 2018 - 17:16:02
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

### 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〉

### Métriques

Consultations de la notice

## 214

Téléchargements de fichiers