episciences.org_450_20230320173412061
20230320173412061
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
03
01
2009
Vol. 11 no. 1
Analysis of Algorithms
Diophantine Approximation, Ostrowski Numeration and the DoubleBase Number System
Valerie
Berthe
Laurent
Imbert
Analysis of Algorithms
A partition of $x > 0$ of the form $x = \sum_i 2^{a_i}3^{b_i}$ with distinct parts is called a doublebase 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 doublebase expansions when only a few iterations of our algorithm are performed.
03
01
2009
450
https://hal.science/lirmm00374066v1
10.46298/dmtcs.450
https://dmtcs.episciences.org/450

https://dmtcs.episciences.org/450/pdf

https://dmtcs.episciences.org/450/pdf