Computing absolutely normal numbers in nearly linear time

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...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2021-12, Vol.281, p.104746, Article 104746
Main Authors: Lutz, Jack H., Mayordomo, Elvira
Format: Article
Language:English
Subjects:
Algorithms
Computational complexity
Lempel-Ziv parsing
Martingales
Normal numbers
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2021.104746