Computing absolutely normal numbers in nearly linear time

A real number is if, for every base , every two equally long strings of digits appear with equal asymptotic frequency in the base- expansion of . This paper presents an explicit algorithm that generates the binary expansion of an absolutely normal number , with the th bit of appearing after computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.