A polynomial-time algorithm for computing absolutely normal numbers

We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sac...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Becher, V., Heiber, P.A., Slaman, T.A.
Formato: JOUR
Materias:
Binary expansions
Combinatorial tools
Control divergences
Normal numbers
Polynomial-time algorithms
Speed of convergence
Time polynomials
Number theory
Algorithms
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_08905401_v232_n_p1_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_08905401_v232_n_p1_Becher
record_format dspace
spelling todo:paper_08905401_v232_n_p1_Becher2023-10-03T15:41:14Z A polynomial-time algorithm for computing absolutely normal numbers Becher, V. Heiber, P.A. Slaman, T.A. Binary expansions Combinatorial tools Control divergences Normal numbers Polynomial-time algorithms Speed of convergence Time polynomials Number theory Algorithms We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sacrifice of speed of convergence to normality. © 2013 Elsevier Inc. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Heiber, P.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_08905401_v232_n_p1_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic Binary expansions
Combinatorial tools
Control divergences
Normal numbers
Polynomial-time algorithms
Speed of convergence
Time polynomials
Number theory
Algorithms
spellingShingle Binary expansions
Combinatorial tools
Control divergences
Normal numbers
Polynomial-time algorithms
Speed of convergence
Time polynomials
Number theory
Algorithms
Becher, V.
Heiber, P.A.
Slaman, T.A.
A polynomial-time algorithm for computing absolutely normal numbers
topic_facet Binary expansions
Combinatorial tools
Control divergences
Normal numbers
Polynomial-time algorithms
Speed of convergence
Time polynomials
Number theory
Algorithms
description We give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sacrifice of speed of convergence to normality. © 2013 Elsevier Inc.
format JOUR
author Becher, V.
Heiber, P.A.
Slaman, T.A.
author_facet Becher, V.
Heiber, P.A.
Slaman, T.A.
author_sort Becher, V.
title A polynomial-time algorithm for computing absolutely normal numbers
title_short A polynomial-time algorithm for computing absolutely normal numbers
title_full A polynomial-time algorithm for computing absolutely normal numbers
title_fullStr A polynomial-time algorithm for computing absolutely normal numbers
title_full_unstemmed A polynomial-time algorithm for computing absolutely normal numbers
title_sort polynomial-time algorithm for computing absolutely normal numbers
url http://hdl.handle.net/20.500.12110/paper_08905401_v232_n_p1_Becher
work_keys_str_mv AT becherv apolynomialtimealgorithmforcomputingabsolutelynormalnumbers
AT heiberpa apolynomialtimealgorithmforcomputingabsolutelynormalnumbers
AT slamanta apolynomialtimealgorithmforcomputingabsolutelynormalnumbers
AT becherv polynomialtimealgorithmforcomputingabsolutelynormalnumbers
AT heiberpa polynomialtimealgorithmforcomputingabsolutelynormalnumbers
AT slamanta polynomialtimealgorithmforcomputingabsolutelynormalnumbers
_version_ 1807320005242519552

Ejemplares similares