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.)
You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. You may not use the material for commercial purposes. If you remix, transform, or build upon the material, you may not distribute the modified material.
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: Article (PostPrint)
Área (Departamento): Área Lenguajes y Sistemas Inf. (Dpto. Informát.Ingenie.Sistms.)
You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. You may not use the material for commercial purposes. If you remix, transform, or build upon the material, you may not distribute the modified material. Exportado de SIDERAL (2023-05-18-14:42:52)
Permalink:
Visitas y descargas
Este artículo se encuentra en las siguientes colecciones:
Articles > Artículos por área > Lenguajes y Sistemas Informáticos
Record created 2022-04-25, last modified 2023-05-19