Computing Absolutely Normal Numbers in Nearly Linear Time

Abstract 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 n polylog ( n ) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.