Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:A polynomial-time algorithm for computing absolutely normal numbers
Autor:Becher, V.; Heiber, P.A.; Slaman, T.A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
CONICET, Argentina
Department of Mathematics, University of California Berkeley, United States
Palabras clave:Binary expansions; Combinatorial tools; Control divergences; Normal numbers; Polynomial-time algorithms; Speed of convergence; Time polynomials; Number theory; Algorithms
Año:2013
Volumen:232
Página de inicio:1
Página de fin:9
DOI: http://dx.doi.org/10.1016/j.ic.2013.08.013
Título revista:Information and Computation
Título revista abreviado:Inf Comput
ISSN:08905401
CODEN:INFCE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_08905401_v232_n_p1_Becher

Referencias:

  • Verónica Becher, Martin Epszteyn, Pablo Ariel Heiber, Theodore A. Slaman, Efficiently computing an absolutely normal number, preprint, 2013; Becher, V., Figueira, S., An example of a computable absolutely normal number (2002) Theoretical Computer Science, 270 (1-2), pp. 947-958. , DOI 10.1016/S0304-3975(01)00170-0, PII S0304397501001700
  • Becher, V., Figueira, S., Picchi, R., Turing's unpublished algorithm for normal numbers (2007) Theoretical Computer Science, 377 (1-3), pp. 126-138. , DOI 10.1016/j.tcs.2007.02.022, PII S0304397507001132
  • Borel, É., Les probabilités dÊenombrables et leurs applications arithmétiques (1909) Suppl. Rend. Circ. Mat. Palermo, 27, pp. 247-271
  • Bugeaud, Y., Distribution Modulo One and Diophantine Approximation (2012) Cambridge Tracts in Mathematics, 193 VOL.. , Cambridge University Press
  • Santiago Figuiera, André Nies, Feasible analysis and randomness, preprint, 2013; Hardy, G.H., Wright, E.M., (2008) An Introduction to the Theory of Numbers, , sixth ed. Oxford University Press Oxford
  • Elvira Mayordomo, Construction of an absolutely normal real number in polynomial time, preprint, 2013; Schmidt, W.M., Über die Normalität von Zahlen zu verschiedenen Basen (1961) Acta Arith., 7, pp. 299-309
  • Sierpiński, W., Démonstration élémentaire du théorème de M. Borel sur les nombres absolument normaux et détermination effective dÊun tel nombre (1917) Bull. Soc. Math. Fr., 45, pp. 127-132
  • Turing, A., A note on normal numbers (1992) Collected Works of A.M. Turing: Pure Mathematics, pp. 117-119. , J.L. Britton, North-Holland Amsterdam with notes of the editor on pp. 263-265

Citas:

---------- APA ----------
Becher, V., Heiber, P.A. & Slaman, T.A. (2013) . A polynomial-time algorithm for computing absolutely normal numbers. Information and Computation, 232, 1-9.
http://dx.doi.org/10.1016/j.ic.2013.08.013
---------- CHICAGO ----------
Becher, V., Heiber, P.A., Slaman, T.A. "A polynomial-time algorithm for computing absolutely normal numbers" . Information and Computation 232 (2013) : 1-9.
http://dx.doi.org/10.1016/j.ic.2013.08.013
---------- MLA ----------
Becher, V., Heiber, P.A., Slaman, T.A. "A polynomial-time algorithm for computing absolutely normal numbers" . Information and Computation, vol. 232, 2013, pp. 1-9.
http://dx.doi.org/10.1016/j.ic.2013.08.013
---------- VANCOUVER ----------
Becher, V., Heiber, P.A., Slaman, T.A. A polynomial-time algorithm for computing absolutely normal numbers. Inf Comput. 2013;232:1-9.
http://dx.doi.org/10.1016/j.ic.2013.08.013