000112083 001__ 112083 000112083 005__ 20230519145449.0 000112083 0247_ $$2doi$$a10.1016/j.ic.2021.104746 000112083 0248_ $$2sideral$$a124622 000112083 037__ $$aART-2021-124622 000112083 041__ $$aeng 000112083 100__ $$aLutz, Jack H 000112083 245__ $$aComputing absolutely normal numbers in nearly linear time 000112083 260__ $$c2021 000112083 5060_ $$aAccess copy available to the general public$$fUnrestricted 000112083 5203_ $$aA 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. 000112083 536__ $$9info:eu-repo/grantAgreement/ES/MEC/PID2019-104358RB-I00$$9info:eu-repo/grantAgreement/ES/MEC/TIN2011-27479-C04-01$$9info:eu-repo/grantAgreement/ES/MEC/TIN2016-80347-R 000112083 540__ $$9info:eu-repo/semantics/openAccess$$aby-nc-nd$$uhttp://creativecommons.org/licenses/by-nc-nd/3.0/es/ 000112083 590__ $$a1.24$$b2021 000112083 592__ $$a0.543$$b2021 000112083 594__ $$a2.2$$b2021 000112083 591__ $$aMATHEMATICS, APPLIED$$b162 / 267 = 0.607$$c2021$$dQ3$$eT2 000112083 593__ $$aComputational Theory and Mathematics$$c2021$$dQ2 000112083 591__ $$aCOMPUTER SCIENCE, THEORY & METHODS$$b73 / 111 = 0.658$$c2021$$dQ3$$eT2 000112083 593__ $$aTheoretical Computer Science$$c2021$$dQ2 000112083 593__ $$aComputer Science Applications$$c2021$$dQ2 000112083 655_4 $$ainfo:eu-repo/semantics/article$$vinfo:eu-repo/semantics/acceptedVersion 000112083 700__ $$0(orcid)0000-0002-9109-5337$$aMayordomo, Elvira$$uUniversidad de Zaragoza 000112083 7102_ $$15007$$2570$$aUniversidad de Zaragoza$$bDpto. Informát.Ingenie.Sistms.$$cÁrea Lenguajes y Sistemas Inf. 000112083 773__ $$g281 (2021), 104746 [12 pp.]$$pInf. comput.$$tINFORMATION AND COMPUTATION$$x0890-5401 000112083 8564_ $$s425304$$uhttps://zaguan.unizar.es/record/112083/files/texto_completo.pdf$$yPostprint 000112083 8564_ $$s2004421$$uhttps://zaguan.unizar.es/record/112083/files/texto_completo.jpg?subformat=icon$$xicon$$yPostprint 000112083 909CO $$ooai:zaguan.unizar.es:112083$$particulos$$pdriver 000112083 951__ $$a2023-05-18-14:42:52 000112083 980__ $$aARTICLE