java - 在 Java 中编写自定义 BigInt 时如何使用大基数更有效

Question

THIS这很可能是有史以来最长的答案。我试图了解自定义实现，但一开始就陷入困境为什么作者使用 10^9作为基础而不是 10 ？用他自己的话说:

As you think the decimal conversion is most complicated part, let's stay in a decimal based mode. For efficiency, we'll store not real decimal digits, but work in base 1 000 000 000 = 10^9 < 2^30. This fits in a Java int (up to 2^31 or 2^32), and the product of two such digits fits nicely in a Java long.

其次我无法理解这一步:

int decLen = decimal.length(); int bigLen = (decLen-1) /
BASE_DECIMAL_DIGITS + 1;

This strange formula is a Java int way of writing bigLen = ceil(decLen/BASE_DECIMAL_DIGITS). (I hope it is correct, we'll later test it.)

Answer 1

使用我们认为的天然碱基，例如 10 ，导致大量操作。你曾经计算过两个 9 位数字的乘法吗？使用我们通常在学校学习的方法，这将涉及 81 位数字乘法。然而，Java 将使用一条乘法指令。

对于大数字(例如 18 位数字)怎么办？对于我们来说，这将涉及 324 位数字乘法。在这里，实现将使用 2 int s，相当于我们把2位数相乘。这将为 Java 带来 4 个乘法指令。

为什么在Java中不使用更大的基数，来进一步减少操作次数呢？因为乘法。保证两个相乘的结果是 int Java 中的 s 将适合 long ，而 10 亿 (10^9) 是适合 int 的 10 的最大幂。这些操作对于 Java 来说仍然非常简单——只需乘法指令。可以使用更大的数字，例如 20 亿，或 Integer.MAX_VALUE (略高于 20 亿)，但出于人类可读性的目的，该答案选择使用 10 亿。任何大于 Integer.MAX_VALUE 的值需要更大范围的东西，但这就是答案已经在尝试做的事情。

此外，少用int表示中的 s 可节省内存使用量。

代码

int decLen = decimal.length();
int bigLen = (decLen-1) / BASE_DECIMAL_DIGITS + 1;

尝试确定有多少 int内部表示中需要 s 将传入号码存储为 String表示。每个 int 有 9 位十进制数字。我会使用 Math.ceil( (double) decLen / BASE_DECIMAL_POINTS) .