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: Artículo (PostPrint)
Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)
Debe reconocer adecuadamente la autoría, proporcionar un enlace a la licencia e indicar si se han realizado cambios. Puede hacerlo de cualquier manera razonable, pero no de una manera que sugiera que tiene el apoyo del licenciador o lo recibe por el uso que hace. No puede utilizar el material para una finalidad comercial. Si remezcla, transforma o crea a partir del material, no puede difundir el material modificado.
Exportado de SIDERAL (2023-05-18-14:42:52)
Visitas y descargas
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: Artículo (PostPrint)
Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)
Debe reconocer adecuadamente la autoría, proporcionar un enlace a la licencia e indicar si se han realizado cambios. Puede hacerlo de cualquier manera razonable, pero no de una manera que sugiera que tiene el apoyo del licenciador o lo recibe por el uso que hace. No puede utilizar el material para una finalidad comercial. Si remezcla, transforma o crea a partir del material, no puede difundir el material modificado.Exportado de SIDERAL (2023-05-18-14:42:52)
Enlace permanente:
Visitas y descargas
Este artículo se encuentra en las siguientes colecciones:
Artículos
Registro creado el 2022-04-25, última modificación el 2023-05-19