Computing absolutely normal numbers in nearly linear time

Lutz, Jack H ; Mayordomo, Elvira (Universidad de Zaragoza)

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

Idioma: Inglés

DOI: 10.1016/j.ic.2021.104746

Año: 2021

Publicado en: INFORMATION AND COMPUTATION 281 (2021), 104746 [12 pp.]
ISSN: 0890-5401

Factor impacto JCR: 1.24 (2021)

Categ. JCR: MATHEMATICS, APPLIED rank: 162 / 267 = 0.607 (2021) - Q3 - T2
Categ. JCR: COMPUTER SCIENCE, THEORY & METHODS rank: 73 / 111 = 0.658 (2021) - Q3 - T2

Factor impacto CITESCORE: 2.2 - Mathematics (Q2) - Computer Science (Q3)

Factor impacto SCIMAGO: 0.543 - Computational Theory and Mathematics (Q2) - Theoretical Computer Science (Q2) - Computer Science Applications (Q2)

Financiación: info:eu-repo/grantAgreement/ES/MEC/PID2019-104358RB-I00
Financiación: info:eu-repo/grantAgreement/ES/MEC/TIN2011-27479-C04-01
Financiación: info:eu-repo/grantAgreement/ES/MEC/TIN2016-80347-R

Tipo y forma: Article (PostPrint)

Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)