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
Descripción
Sumario: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.

Ejemplares similares