A polynomial-time algorithm for computing absolutely normal numbers

We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sacrifice of speed of convergence to normality.

Authors

• Verónica Becher
• Pablo Ariel Heiber
• Theodore A. Slaman

Keywords

No keywords are indexed for this paper.