【科普】三进制计算如何胜过二进制

luyuanhong

【科普】三进制计算如何胜过二进制

原创 Stephen Ornes 梧桐阅览 2024 年 08 月 10 日 21:00 湖北

中文翻译编辑校对：酉木木

长期探索但鲜有采纳，三进制计算可能最终在网络安全领域找到其应用之地。



三，正如 1970 年代的 Schoolhouse Rock 告诉孩子们的，是一个神奇的数字。三只小猪；金发姑娘的三张床、三个碗和三只熊；三部《星球大战》三部曲。至少需要三条腿，凳子才能自己站立，至少需要三个点来定义一个三角形。

数字 3 也暗示了一种不同的计数方式。我们熟悉的十进制系统使用从 0 到 9 的 10 个字符表示数值。二进制，我们的计算机通用语言，仅使用 0 和 1 这两个数字来表示数值。

但数学家们长期以来一直在探索三进制的计数方式。例如，考虑三进制，或称为三元制，它使用三个数字。标准惯例是使用数字 0 、1 和 2 。



三进制记数的一个显著特点是它极其高效。两个二进制位可以表示四个数字。两个“三进制位”（每个有三种不同的状态）允许你表示九个不同的数字。需要 42 位二进制位的数字，只需要 27 个三进制位。

如果三状态系统如此高效，你可能会想象四状态或五状态系统会更加高效。但你需要的数字越多，所需的空间就越大。事实证明，三进制是所有可能的整数基数中表示大数最经济的。

要了解为什么，考虑一个重要的度量标准，它计算一个系统存储数据所需的空间。你从数字系统的基数开始，这被称为基数，然后将其乘以表示该基数中某个大数所需的位数。例如，十进制中的 100,000 需要六个数字。它的“基数经济性”因此是 10×6=60 。在二进制中，同一个数字需要 17 位，所以它的基数经济性是 2×17=34 。而在三进制中，它需要 11 位，所以它的基数经济性是 3×11=33 。对于大数来说，三进制的基数经济性比任何其他整数基数都要低。（令人惊讶的是，如果你允许基数是任何实数，而不仅仅是整数，那么最有效的计算基数是无理数 e 。）

除了数值效率外，三进制还提供了计算上的优势。它提出了一种减少回答多于两个可能答案问题所需的查询次数的方法。二进制逻辑系统只能回答“是”或“否”。所以如果你正在比较两个数字 x 和 y ，以找出哪个更大，你可能会首先问计算机“x 小于 y 吗？”如果答案是不，你需要第二个查询：“x 等于 y 吗？”如果答案是肯定的，那么它们相等；如果答案是否定的，那么 y 小于 x 。

使用三进制逻辑的系统可以给出三种答案之一。因此，它只需要一个查询：“x 小于、等于还是大于 y ？”

尽管具有自然优势，三进制计算从未起飞，尽管许多数学家对其效率感到惊叹。1840 年，一位名叫托马斯·福勒的英国印刷商、发明家、银行家和自学成才的数学家发明了一台三进制计算机来计算税收和利息的加权值。“在那之后，多年来几乎没有什么进展，”北亚利桑那大学的应用物理学家伯特兰·坎布说。

1950 年，在数字时代的黎明，一份关于当时计算技术的长篇报告建议了三进制的计算优势。1958 年秋季，访问苏联的访客报告说那里的工程师一直在开发一种名为 Setun 的三进制计算机——基于三进制逻辑和硬件的首台现代计算机。苏联科学家建造了数十台 Setun 计算机。

为什么三进制计算没有流行起来？主要原因是传统。尽管苏联科学家正在制造三进制设备，但世界其他地区专注于开发基于开关电路的硬件和软件——这是二进制计算的基础。二进制更容易实现。

但过去几年带来了一些进展。工程师们提出了在基于二进制的硬件上构建三进制逻辑系统的方法。在美军的支持下，坎布一直在开发使用三进制计算的网络安全系统。在 2018 年和 2019 年发表的论文中，他和他的合作者详细描述了一个可以取代现有公钥基础设施的基于三进制的系统，这包括加密或解密网络通信所需的数字密钥。他说，从比特切换到三进制位，显著降低了错误率，因为三进制状态更好地管理不稳定的信息。

Schoolhouse Rock ! 被证明是有先见之明的。“过去、现在和未来，”卡通人物唱道。“你得到三作为一个神奇的数字。”

RELATED:

What Is Analog Computing ?

Complexity Theory's 50-Year Journey to the Limits of Knowledge

Cryptography's Future Will Be Quantum-Safe. Here's How It Will Work.

梧桐阅览