Computing absolutely normal numbers in nearly linear time
Jack H. Lutz, Elvira Mayordomo · Information and Computation · 2021
A real number x is absolutely normal if, for every base b≥2, every two equally long strings of digits appear with equal asymptotic frequency in the base-b expansion of x. This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number x, with the nth bit of x appearing after npolylog(n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.