Computing absolutely normal numbers in nearly linear time
Computing absolutely normal numbers in nearly linear time
复制标题
在近乎线性的时间内计算绝对正规数
DOI：
10.1016/j.ic.2021.104746
复制
发表时间：
2021
影响因子：
1
通讯作者：
Mayordomo, Elvira
中科院分区：
文献类型：
--
作者：
Lutz, Jack H.;Mayordomo, Elvira
一个真实的数x是绝对正规的，如果对每个基B≥ 2，在x的基B展开式中，每两个等长的数字串以相等的渐近频率出现。本文提出了一个显式算法，它生成绝对正规数x的二进制展开，x的第n位出现在n个polylog（n）计算步骤之后。这种速度是通过同时计算和对角化对一个鞅，结合Lempel-Ziv解析算法在所有基地。
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 n polylog (n) computation steps. This speed is achieved by simultaneously computing and diagonalizing against a martingale that incorporates Lempel-Ziv parsing algorithms in all bases.