为什么说三进制是效率最高的进制？

“有人说，三进制被证明是理论上效率最高的进制。” 在一次计算机导论课中，老师将此问题作为课后作业留了下来。为什么有这种说法？一起来看看吧！

为什么在理论上三进制是最高效率的进制？

Tip

这里的内容来自知乎大佬 @白云龙的这篇回答。

B站 up 主 @差评君的这个视频中对这篇回答进行了动画形式的展现。

首先，让我们来约定一下 “进制的效率”：

$进制的效率 = \frac{表达的信息量}{表达这些信息所需的资源}$

比如我们需要表达十进制下 0~999 这 1000 个数字，这就是我们 $表达的信息量$ ，我们选择用写有数字的牌子来表示它们。

在十进制下，0~999 我们至少需要三位，每位上我们都需要 0~9 十个数字的牌子，所以三位一共是 30 个数字牌子；
在二进制下，0~999 是 0~1111100111，我们至少需要十位，每位是 0 或 1，所以一共是 20 个数字牌子；
在三进制下，0~999 是 0~1101000，至少七位，每位是 0、1 或 2，所以一共是 21 个数字牌子；
在四进制下，0~999 是 0~33213，需要 20 个数字牌子；
在五进制下，0~999 是 0~12444，需要 25 个数字牌子；
...

这些数字牌子的个数就是 $表达这些信息所需的资源$ 。到目前为止，似乎二进制和四进制的效率最高。

但这样理解并不完全准确。因为实际上，对于某些进制而言，对应数量的数字牌子其实不止能表达这么多信息。比如在二进制情况下，20 个数字牌子表达的数字总量应该是 $2^{10} = 1024$ 个；在三进制的情况下，21个数字牌子表达的数字总量却是 $3^7 = 2187$ 个；在四进制的情况下，20 个数字牌子表达的数字总量是 $4^5 = 1024$ 个...

也就是说，虽然对于上边十进制而言，它那 30 个牌子表达的信息量确实就是 0~999 这 1000 个数字的信息，或者我们说 1000 种状态信息，但对于下边的比如二进制、三进制、四进制，对应的 20 个、21个、20个牌子其实表达了超过 1000 种状态，我们用这些牌子是有浪费的。

这么来算，我们大致可以得到，十进制的效率是 $\frac{1000}{30} \approx 33.3333$ ，二进制的效率是 $\frac{1024}{20} = 51.2$ ，三进制的效率是 $\frac{2187}{21} \approx 104.1429$ ，四进制的效率是 $\frac{1024}{20} = 51.2$ ...

从这个例子我们已经大概能看到三进制的效率了，那么怎么证明这件事儿呢？

回顾上边的思考过程，我们的数字牌子个数是怎么被算出来的呢？我们大概可以总结出：

$数字牌子的个数 = 进制数 \times 所需的位数$

而为了满足上边的表达 1000 个状态的要求，所以我们要求：

$进制数^{所需的位数} \geq 1000$

也就是说：

$所需的位数 = 向上取整（log_{进制数}1000）$

因为进制数必须是整数，所以我们必须加上 $向上取整$ ，但就是因为这个向上取整，我们浪费了很多的资源，所以我们先假设 $进制数$ 是个实数。

那么现在对上面 $数字牌子的个数$ 的式子改成 $表达这些信息所需的资源$ ，这样这个式子就成了下边这样：

$表达这些信息所需的资源 = 进制数 \times log_{进制数}表达的信息量$

记 $表达这些所需的资源$ 为 $R$ ， $进制数$ 为 $N$ ， $表达的信息量$ 为 $I$ ：

$R = N \times log_NI$

记效率为 $E$ ，那么：

$E = \frac{I}{R} = \frac{I}{Nlog_NI} = \frac{I}{lnI}\times\frac{lnN}{N}$

求导：

$\frac{dE}{dN} = \frac{I}{lnI}\times\frac{1-lnN}{N^2}$

分析单调性，我们知道，当 $N = e$ 时，效率 $E$ 最大。

所以也就是，e 进制 理论上才是效率最高的进制。

但是，e 进制是个啥呢？试试 e 附近的 2 和 3，得到 $E(2) \approx 0.3466\times\frac{I}{lnI}$ ， $E(3)\approx 0.3662\times\frac{I}{lnI}$ ，所以，三进制是理论上效率最高的进制。

为什么没用三进制？

在上边的两个引用里，知乎大佬 @白云龙和 b 站 up 主 @差评君都给出了一些答案。@白云龙大佬的说法是，在实际的实现过程中，实现二进制的 “牌子” 和实现三进制的 “牌子” 的成本不一样，可能二进制的 01 牌子就便宜好用，但三进制的牌子就是又贵又难用，最后所需的资源还要乘上每个牌子的单价，加上这层因素后，二进制比三进制更经济。这其实也就是 @差评君所言的，二进制只需高低电平来区分 01，但三进制需要实现三种电流状态就比较复杂。

但其实我觉得，这样的问题并不是什么太大的问题，就像 SLC、MLC、TLC 一样。既然我们都可以在同样的电子数的情况下分别实现 2、4、8种状态的区别，那多实现一个除了 01 以外的第三个状态似乎也类似？(我瞎说的哦，别当真，大佬轻喷...)。主要是，二进制计算机确实已经走到了这样一个瓶颈期，我们的芯片制程来到了十几纳米甚至几纳米、我们的光刻机使用的光已经来到了极紫外光的情况下，想要进一步提升二进制计算机的一丁点性能所消耗的成本是极其庞大的。但是，三进制却是一条新的路，也许就是一条出路。

如果我们把视角从全人类缩到我们中国，在这个光刻机远远落后于欧美的情况下，或许三进制，真的就是我们中国的出路。

为什么说三进制是效率最高的进制？

为什么在理论上三进制是最高效率的进制？

为什么没用三进制？

参考资料