为什么BigInteger实现使用符号-大小法而不是二进制补码？

Question

任意精度有符号整数几乎总是使用符号-幅度表示法实现：

• (Java) OpenJDK中的BigInteger
• (Python) CPython中内置int类型的Bigint实现
• (C) GMP中的mpz_t，GNU多精度算术库
• (C++) 由Matt McCutchen编写的bigint库中的BigInteger
• (Rust) num-bigint库中的BigInt

明显偏爱符号-幅度与固定宽度有符号整数类型中近乎普遍的二进制补码偏好形成对比。问题是，为什么BigIntegers如此明显地偏爱符号-幅度？（如果您不同意前提条件，我欢迎反例。）请注意，BigInteger API通常指定“似乎是二进制补码”的语义（例如Java, Python），对于位运算很重要。这提供了与这些操作的通常含义一致性。这并不决定实际内部表示（只是一个实现细节），但如果其他条件相等，这应该是使用二进制补码的一个优点。浮点数使用符号-幅度，而不像int使用二进制补码。然而，浮点数的行为和算法与整数算术明显不同，因此浮点数并不能真正作为指导性先例。Bignums更类似于ints。

我们知道为什么二进制补码在数学上起作用并具有优势的“教科书”原因。在我看来，这些原因同样适用于整数和BigIntegers。那么，这是否真的如此？当然，硬件定点整数和软件任意精度整数的设计约束存在巨大差异。从这个意义上说，看到设计者在这些不同领域中做出不同的权衡并不奇怪。那么，对于任意精度整数，符号-大小和二进制补码之间的权衡是什么？例如，这可以是某些重要算法的性能或简单性方面。我希望你的回答能阐明BigInteger算术所涉及的设计考虑，并帮助我从新的角度重新审视我对二进制补码的了解。（明确一点：当我说任意精度整数的二进制补码时，我的意思是使用一个字数组表示，其位模式组合在一起是所需数字的二进制补码表示形式，可能还需要满足“非必要的前导0”（对于非负数）或“非必要的前导1”（对于负数）的额外要求。）

- echinodermata

---

我修复了Python的链接；你之前提供的链接指向专门且有限的bigint实现，仅用于浮点数和字符串之间的转换，并与Python的int类型无关。 - Mark Dickinson

Answer 1

二进制补码使得相同长度的数字的加减法更简单，但乘除法更加复杂。对于硬件实现，可能会有时间惩罚，但并不总是如此。查看X86“常春藤桥”指令表，只有在128位有符号被除数除以64位有符号除数的情况下，二进制补码才会花费更多时间。因此，这主要是软件基础数学问题。

大整数库可以使用更复杂但更快速的表示方法来表示大数。以下是一些示例文章链接：

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

https://cp-algorithms.com/algebra/big-integer.html

http://www.apfloat.org/ntt.html

更复杂的方法通常对于相当大的数字更快，对于中等大小的数字，简单的实现将更快。

- rcgldr

---

由于具有不同长度的位串表示值（我认为对于不同长度的数字，加法并不那么简单），因此二进制补码的优点可能也不太适用。 - Bernhard Barker

此外，在补码中，我们不必对符号-幅度数进行符号扩展。 - Rudy Velthuis

就此而言，链接中提到的更复杂的表示通常只用于特殊目的。例如，一个不进行除法运算，另一个在加减法方面存在很大问题。大多数使用二进制基数（2^32或2^64）或十进制基数（例如10^9或10^19）。 - Rudy Velthuis

由于浮点数算法和整数算法的行为和算法显著不同。实际上，最终它们并不是不同的。FP（或多或少）被移位直到指数匹配，然后算术运算相同。只需进行额外的舍入和移位步骤。 - Rudy Velthuis

@RudyVelthuis - 关于复杂度，我在考虑处理50位数字和100,000位数字的方法。对于基于FP的实现，我的印象是元素范围被限制为整数值，以便中间计算是精确的。通常使用除法算法来避免使用实际的除法指令。 - rcgldr

Answer 2

我自己构建了一些大数库，我同意rcgldr的答案（+1），二进制补码在高级运算中会带来问题，而不仅仅是*,/。

除此之外，一些大数库不使用2的幂作为基数，对于这种情况使用二进制补码也是一种技巧。不使用2的幂的原因是我们在以10为基础进行计算，所以我们期望输入和结果都是以10为基础的。在2进制（或2的幂）和10进制之间转换的时间复杂度通常是~O(n^2)，对于非常大的数字，它们的计算量通常比操作本身还要大。因此，这些库使用最大的10的幂，以适应所使用的ALU字长...例如，在32位系统中，这个值为1 000 000 000。这会稍微浪费一些空间，但可以简化数字和字符串表示之间的输入和输出转换，时间复杂度为O(n)，其中n是使用的数字或单词的数量...

同时，二进制补码使得对于许多底层操作（例如NTT乘法）所需的模算术变得更加复杂。

处理和恢复二进制补码需要O(n)，而单独处理符号只需要O(1)，这是我认为的主要原因。

- Spektre

---

十进制和二进制之间的转换可以比O(n^2)更快。 可以参考Richard P. Brent和Paul Zimmermann的"Modern Computer Arithmetic", 1.7.2 Subquadratic algorithms或者我的BigInteger实现(https://github.com/rvelthuis/DelphiBigNumbers/blob/master/Source/Velthuis.BigIntegers.pas)，进行了解。 - Rudy Velthuis