三进制隐藏的效率,以及建立在它之上的游戏,是否悄然成了一台更优雅的机器。
本文以英文撰写和编辑。此中文版本由机器翻译生成;凡涉及准确性之处,以英文原文为准。 阅读英文原文 →
3927 是在三个维度中、用另一种算术重建的 2048。棋盘是一个 3×3×3 立方体,共二十七个格子,你可以沿六个方向中的任意一个推动整个立方体。当三个数值相同的方块相撞时,它们不会翻倍,而是变为三倍。3 变成 9,9 变成 27,然后继续:81、243、729。游戏的名字本身就数出了前三个方块——3·9·27——而整个设计从头到尾都是三:每条轴三个格子,三个方块一次合并,增长倍数为三。4
它的前身则固执地坚守二进制。经典的 2048 使用 2 的幂——2、4、8、16……——并成对合并方块。二是抛硬币的数字,是晶体管的数字,是比特的数字。于是,好奇的玩家自然会问:把二换成三只是图个新鲜,还是三一直隐藏着真正的优势?事实证明,数学对此有自己的看法,而且态度出奇地坚定。
设想你必须造一台存储数字的机器。每一个数位都要花费一些东西——一个齿轮、一根导线、一只电子管——而这份花费随进制增长,因为一个 b 进制数位需要 b 个可区分的状态。但更大的进制也意味着,表示任意给定的数字所需的数位更少。这里存在一种张力,它有一个名字:进制经济性(radix economy)。
形式化地说,用 b 进制表示数 N 的经济性,等于进制乘以位数:E(b,N) = b ⌊log_b N + 1⌋。1 大进制换来的是短小的数字,但每一位都很昂贵;小进制每一位都很便宜,但数字会铺得很长。在这两个极端之间存在一个最佳点,而它并不在我们大多数技术最终落脚的地方。
| 进制 | b ÷ ln b | 与最优值相比 |
|---|---|---|
| 2 | 2.885 | +6.2% |
| 3 | 2.731 | +0.5% |
| e ≈ 2.718 | 2.718 | 最优值 |
| 10 | 4.343 | +59.8% |
当 N 很大时,经济性近似于 (b ÷ ln b) · ln N,因此一个进制的效率完全取决于因子 b ÷ ln b。用一点微积分求它的最小值,得到的答案既精确又奇特:所有进制中最经济的是 e,约为 2.71828。1 当然,你不可能造出每位有 2.718 个状态的计算机。但你可以问:哪个整数最接近这个理想值?胜出者——同时击败了二和十——是三。
这个差距并非纸上谈兵。三进制与理论最优值的差距不到百分之零点五,而二进制要多付百分之六的附加成本,十进制更是要多付沉重的百分之六十。有一个具体的方法可以感受这一点:要写出从 0 到 999,999 的每一个数,二进制需要 20 位,十进制需要 6 位,而三进制只需要 13 位——13×3 的总和比 20×2 更小。1 三确实用更少的结构装下了更多的计数。
人们请大自然说出最有效率的计数方式,它回答了一个无理数。最接近这个答案的整数,是三。
这不仅仅是教科书里的奇谈。1958 年,在莫斯科国立大学,由 Nikolay Brusentsov 和数学家 Sergei Sobolev 领导的团队建造了 Setun,这是有史以来最著名的三进制计算机。3 当西方全力投入比特时,Setun 以三进制位(trit)计数,而且采用了一种格外优美的方案:平衡三进制,它的三个数位值不是 0、1、2,而是 −1、0、+1。2
这种对称性立刻带来了回报。一个数自带符号——不需要单独的符号位,也不需要二进制补码那样的周折——要对任何数值取反,只需把每一位翻转即可。舍入与截断变成了同一种运算。Donald Knuth 称它“也许是所有数制中最漂亮的一种”。2 由于缺少晶体管,Brusentsov 用成对的铁氧体磁芯巧妙地造出了三个稳定状态;Setun 总共制造了大约五十台,大多被送往苏联各地的大学用于数学教学。3 这台机器能用,造价低廉,而且不声不响地领先于同时代的机器。
到了这里,一位谨慎的作者必须克制住自己。进制经济性是一个在特定成本假设下关于存储和处理数字的论断,而且连数学家也指出,这些假设只是近似的——更完整的核算往往会重新证明二进制的合理性,这也正是世界运行在二进制之上的原因。1 合并谜题不是存储器;没有人会在喝咖啡的间隙去最小化电子管的数量。所以,3927 在任何实质性的工程意义上都谈不上“更有效率”,说它是,就是在耍花招。
然而,这款游戏确实继承了某种真实的东西。以三倍增长,能用更少、更有分量的步数达到很大的数字;每一次合并都做了更多的功,而 3×3×3 立方体是能让三方合成在每个方向上都施展得开的最小棋盘。4 这个设计并不是偶然撞上了三,而是落在了计数数学自电子计算诞生之初就默默偏爱的那个整数上——也正是 Setun 的工程师们有意选择的那个数。二是我们默认沿用的数字;如果由效率而不是抛硬币来做最终裁决,三才是我们会选择的数字。方块恰好拼出 3、9、27,不过是宇宙早已讲过的一个小玩笑。
Game facts, the 3×3×3 board, six shift directions, three-tile ×3 merge, and the 3·9·27 naming, are measured from the game's design documents. Mathematical and historical claims are drawn from the references below.