29

所以，不久前我读到一个类似这样的笑话：

“永远不要以二进制计算 pi - 因为它无限地进行并且是随机的，理论上它包含每个有限位字符串。因此，您将拥有所有现有的受版权保护的材料并承担一些严重的罚款。”

这显然是为了幽默，但它让我思考。如果每个有限位字符串都存在于 pi 的二进制表示中，是否可以将其用作传输数据的方法？

例如，假设我想传输一个可以解释为 jpeg 图像的位串。我不会直接发送信息，而是在 pi 的数字内找到它的位置，并简单地发送 pi 的数字内的第一位的位置，以及字符串的长度。

这对我来说似乎很简单，但这里明显的问题是即使在前几万亿位数字中找到这个字符串的概率也非常小。因此，最终可能需要花费大量时间才能找到。

我的想法是，可以有几台机器专门用于在 pi 中搜索大文件，然后创建它们所有起始位置的索引。因此，每次计算只需要发生一次，然后该信息可以从那时起非常快速地传输。

所以你怎么看？这是完全可行的，还是这些计算会花费太多时间？

谢谢阅读！如果我忽略了任何发布指南，我深表歉意，这是我在这个论坛上的第一个问题。

编辑：

感谢您的快速回复，伙计们！我认为我的推理有误，很高兴知道为什么！

4

5 回答 5

48

扩展我的评论。这里有一个非常重要的概念，叫做信息熵。

在完全公开的情况下，我是目前 Pi 数字 10 万亿位 (10^13) 的世界纪录保持者。

我有大约 10,000 份每个人的社会安全号码。

然而，这并不意味着我可以侵入每个人的账户并窃取他们的身份。因为我不知道每个人的SSN从哪里开始。对于典型的 9 位 SSN，Pi 中将出现该 SSN 的第一个数字的长度约为 9 位。换句话说，关于 SSN 的信息保存在地址中，而不是 Pi 本身中。

例如，如果某人拥有 SSN：938-93-3556

它从 Pi 中的偏移量597,507,393开始。这个数字597,507,393大约与 SSN 本身一样长。换句话说，我们没有通过使用 Pi 获得任何收益。
（我不确定它是否出现了更早的偏移量，但随着偏移量的减小，概率会呈指数下降。）

概括地说，即使你有无限位数的 Pi（理论上它包含所有可能的信息），保存数据 XXX 的地址也将（极有可能）与 XXX 本身一样大。

换句话说，信息不是保存在 Pi 本身的数字中，而是保存在信息开始的地址中。

于 2012-07-06T18:55:36.027 回答
23

因为我们都在Lounge<C++>中感到无聊，所以我继续执行搜索以找出特定长度的“消息”的平均偏移量。

我下载了 100 万位 Pi并查找了所有固定长度的子序列（例如 00..99）。根据消息长度，您将获得以下输出：

 Digits    Avg.Offset    Unfound

 1            8.1        0
 2          107.07       0
 3          989.874      0
 4         9940.46       0
 5        99959.4        8 <-- note

请注意，在 pi searched的位数的 10% 处，我们已经开始遇到未找到的模式。

还要注意，正如信息熵定律所预测的那样，平均偏移量大致与消息的长度成正比。

原始输出和时间：

跑步

for a in 10 100 1000 10000 100000; do \make -B CFLAGS=-DNUMRANGE=$a && time ./test; done

节目

g++ -DNUMRANGE=10 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
81 cumulative, 8.1 average

real    0m0.008s
user    0m0.008s
sys 0m0.004s
g++ -DNUMRANGE=100 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
10707 cumulative, 107.07 average

real    0m0.004s

g++ -DNUMRANGE=1000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
989874 cumulative, 989.874 average

real    0m0.010s

g++ -DNUMRANGE=10000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
0 unfound
9.94046e+07 cumulative, 9940.46 average

real    0m0.081s

g++ -DNUMRANGE=100000 -std=c++0x -g -O3 -fopenmp -march=native test.cpp -o test && ./test
8 unfound
9.99594e+09 cumulative, 99959.4 average

real    0m7.387s

完整代码、makefile 和 pi 数字：https ://gist.github.com/3062541

于 2012-07-06T20:33:40.667 回答
5

不，不可能在随机序列中有效地找到任意序列——这源于“随机”的定义。（如果有办法预测序列发生的位置，它就不是随机的。）

至于索引所有位置，那么，你得到了什么？您实际上是在说“跳到起点 0...”，然后您必须说“...然后以 π 计算下一个 JPEG 大小的位...”（没有胜利，因为您必须使用向上能量进行计算）或“......然后在 mega-π 索引中查找下一个 JPEG 大小的数据块。” （在这种情况下，您可以加载 JPEG 文件。）

你不能赢，也不能收支平衡（而且，就其价值而言，你不能退出游戏）。

更新：@Mysticial 的回答比我的好。他的观点

例如，如果某人拥有 SSN：938-93-3556

它从 Pi 中的偏移量 597,507,393 开始。这个数字 597,507,393 大约与 SSN 本身一样长。换句话说，我们没有通过使用 Pi 获得任何收益。

优雅地抓住了根本问题。

于 2012-07-06T18:49:29.350 回答
5

这种说法是错误的。Pi 是无限的，它的下一个数字是不可预测的，但这并不意味着每个可能的字符串都在那里。

例如，假设我创建了一个类似于 pi 的函数，但任何时候都有 20 个二进制零序列，计算接下来的 20 位，并用它替换零。

这个序列也是无限的，不可预测的——但我们可以肯定地知道它永远不会包含 20 个二进制零的序列。

没有办法证明 PI 包含所有可能的位序列。

这也可能有助于回答： http ://www.youtube.com/watch?v=8PUJvAlD64k

于 2012-07-06T18:50:41.270 回答
1

因为它是无限进行的并且是随机的，理论上它包含了每一个有限位串

Pi 无限继续，但绝对不是随机的 - 即。它的数字可以由一个O(log n)大小的程序计算（因此，有限前缀可以由比前缀小得多的程序生成），这意味着 Pi 前缀的 Kolmogorov 复杂度渐近小于它们的大小。因此，尚未证明它包含每个有限字符串（我不知道）。

于 2012-07-06T18:49:43.223 回答