A polynomial-time algorithm for computing absolutely normal numbers

作者：Becher Veronica^*; Ariel Heiber Pablo; Slaman Theodore A

来源：Information and Computation, 2013, 232: 1-9.

DOI：10.1016/j.ic.2013.08.013

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-11