Knuth的基本算法的这一说法至今仍然适用吗？

Question

从某种意义上说，10！(十阶乘)表示实际计算的事物和不计算的事物之间的近似分界线。

这是来自Knuth的TAOCP基本算法书(1973)。这仍然是一个有效的陈述，还是计算能力使它过时了？

Answer 1

这还是合理的。

10 =3 628 880。在那之后的每一步都至少上升了一个数量级。

(fact 10)
3628800

(fact 11)
39916800 -- about 40 million

(fact 12)
479001600 -- almost 500 million

(fact 13.0)
6227020800.0 -- over 6 billion

很快，你就会谈到国会的开支数字。

Answer 2

幸运的是，这位优秀的教授还在我们身边，最好的办法就是给他写信，征求他的意见。

尽管如此，我认为绝对值并不像阶乘所代表的函数那么重要。不管Knuth当时是否意识到了这一点，他用这一说法建立的模型对于回顾过去几十年的实际计算和接下来的计算非常有效。

1973年，我们的生成、存储、传输和处理数据的能力受到了限制，足以制造10种数据！一个合理的“远缘”的数字来拍摄。我怀疑Knuth (或其他人)是否能够预测到自那以后我们所享受的几乎所有事物的指数改善，但因式分解与实际数字吻合得很好。

我亲眼目睹了这一点:十年前，我做了一个项目，当时我们正在开发方法来存储和处理大约5000万张唱片，同时思考我们应该如何做一个数量级的记录。十年后，我正在做一个类似的项目。我的目标数字发生了变化，这一切都是以因素的方式进行的：

                      2002           2012
Small Test .......  9! / 362K ... 10! / 3.6M
Large Test ....... 10! / 3.6M ... 11! /  40M
Capacity Goal .... 11! /  40M ... 12! / 479M
Capacity Dream ... 12! / 479M ... 13! / 6.3B

做这两个项目的小组都比那些人有更全面的数字，但是因式算式并不是很远。世界上的谷歌和Facebook都有资源来做我目前项目中梦寐以求的事情，但从我所处的位置来看，十年或更短的时间内，13!似乎并不遥不可及。

1992年我并没有考虑到大量的数据，但事后看来，我可能只看了一个因子就能看完所有的数据。