112083 20230519145449.0 doi 10.1016/j.ic.2021.104746 sideral 124622 ART-2021-124622 eng Lutz, Jack H Computing absolutely normal numbers in nearly linear time 2021 Access copy available to the general public Unrestricted 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. info:eu-repo/grantAgreement/ES/MEC/PID2019-104358RB-I00 info:eu-repo/grantAgreement/ES/MEC/TIN2011-27479-C04-01 info:eu-repo/grantAgreement/ES/MEC/TIN2016-80347-R info:eu-repo/semantics/openAccess by-nc-nd http://creativecommons.org/licenses/by-nc-nd/3.0/es/ 1.24 2021 MATHEMATICS, APPLIED 162 / 267 = 0.607 2021 Q3 T2 COMPUTER SCIENCE, THEORY & METHODS 73 / 111 = 0.658 2021 Q3 T2 0.543 2021 Computational Theory and Mathematics 2021 Q2 Theoretical Computer Science 2021 Q2 Computer Science Applications 2021 Q2 2.2 2021 info:eu-repo/semantics/article info:eu-repo/semantics/acceptedVersion Mayordomo, Elvira Universidad de Zaragoza (orcid)0000-0002-9109-5337 5007 570 Universidad de Zaragoza Dpto. Informát.Ingenie.Sistms. Área Lenguajes y Sistemas Inf. 281 (2021), 104746 [12 pp.] Inf. comput. INFORMATION AND COMPUTATION 0890-5401 425304 http://zaguan.unizar.es/record/112083/files/texto_completo.pdf Postprint 2004421 http://zaguan.unizar.es/record/112083/files/texto_completo.jpg?subformat=icon icon Postprint oai:zaguan.unizar.es:112083 articulos driver 2023-05-18-14:42:52 ARTICLE