A polynomial-time algorithm for computing absolutely normal numbers (Q386000)

The authors provide an algorithm that computes an absolutely normal number (i.e., a real number whose digits in its infinite expansion with respect to each base are distributed uniformly) so that the first \(n\) digits in its binary expansion are obtained in time polynomial in \(n\); in fact, just above quadratic. Their algorithm (an efficient variant of Turing's approach on absolutely normal numbers) uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the cost of slowness of convergence to normality (an interesting question is whether the trade-off between rate of computation and rate of convergence to normality is an inherent aspect of any such computation).