Java的BigInteger的toString使用递归算法，
toString(BigInteger u, StringBuilder sb,
int radix, int digits)它将u划分为基数、基数^2、基数^4、基数^8（基本上是基数^2^n）的范围，
int b = u.bitLength();
int n = (int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
LOG_TWO - 1.0);然后决定u属于哪个范围，并使用divide和mainder合并结果（这是一种递归算法）
BigInteger v = getRadixConversionCache(radix, n);
BigInteger[] results;
results = u.divideAndRemainder(v);
int expectedDigits = 1 << n;
// Now recursively build the two halves of each number.
toString(results[0], sb, radix, digits - expectedDigits);
toString(results[1], sb, radix, expectedDigits);让我困惑的是，为什么它使用
Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
LOG_TWO - 1.0)我认为它应该使用地板，而不是-1.0
Math.floor(Math.log(b * LOG_TWO / logCache[radix]) /
LOG_TWO)为了找到合适的基数^2^n进行除法，我还从2到1024进行测试（2^1到2^10）
[2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]如果使用
Math.round(Math.log(b * LOG_TWO / logCache[radix]) /
LOG_TWO - 1.0)然后它变成
[-3, -2, -1, -1, 0, 0, 0, 0, 0, 1]这似乎是错误的，但使用
Math.floor(Math.log(b * LOG_TWO / logCache[radix]) /
LOG_TWO)结果是
[-2, -1, -1, 0, 0, 0, 1, 1, 1, 1]这似乎是正确的
1条答案
按热度按时间e3bfsja21#
该守则的目的是什么
其目的是找到具有
radix^x形式的BigInteger v，其将BigInteger u分成两部分，两部分具有大致相同长度的字符串表示。“完美”值可能是10^x，其中u.sqrt()介于0.5 * 10^x和5 * 10^x之间（对于基数10）。然而，这样的计算将是非常低效的。（也许因子0.5和5并不理想-也许它们应该是0.316和3.16，因此1000到100000之间的值选择100-但由于没有使用这种方法，精确值并不重要。）
相反，代码通过使用序列基数^1、基数^2、基数^4中的一个值来近似“完美”值，因为这些基数^2（2^x）值很容易计算，并且仍然给出足够好的结果。
让我们看看对于位长度为1024（长度为308到309个字符的字符串表示）的
BigInteger，该计算是如何工作的。表达式
(int) Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0)是两个计算，它们被封装到一个表达式中：b * LOG_TWO / logCache[radix]计算将BigInteger值表示为基数radix中的字符串的近似位数请注意，
logCache[radix]用Math.log(radix)初始化，LOG_TWO为Math.log(2)，因此完整表达式为b * Math.log(2) / Math.log(radix)对于1024的
bitlength，计算结果为308.2547（四舍五入为4位）。我们将此中间结果命名为
num_digits(int) Math.round(Math.log(num_digits) / Math.log(2) - 1.0)。对于308.2547的num_digits，这给出了7。因此，在我们的示例中，代码将选择
10^(2^7)（即10^128）作为除数来分割原始数字。为什么使用
Math.round(x-1)而不是Math.floor(x)bitlength来证明这一点。实际上，这种计算从来不会用这么小的值进行*它为
n提供了更好的值。以位长度为14为例（
BigInteger值介于8192和16383之间）。使用
Math.round(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO - 1.0)得到n=1，这意味着代码将选择10^(2^1)（100）来拆分BigInteger。使用
Math.floor(Math.log(b * LOG_TWO / logCache[radix]) / LOG_TWO)得到n=2，这意味着代码将选择10^(2^2)（10000）来拆分BigInteger-但对于BigInteger值8192，这意味着您根本不会拆分它。Math.floor()会在几个地方出现故障：*Math.floor()会导致n=1和u=100，因此无法拆分值64-99Math.floor()会导致in=2和u=10'000，因此无法拆分值8'192-9'999Math.floor()会导致in=3和u=100'000'000，因此无法拆分值67'108864-99'999'999Math.floor()会导致in=3，u=10'000'000'000000'000，因此无法拆分值9'2007'199'254'740992-9'999'999'999999'999对于这些范围（以及存在较大位长值的其他范围），拆分后需要特殊处理：如果上半部分是BigInteger。然后进行一些特殊处理。但任何一种特殊处理都会使算法更复杂、更容易出错和更慢。
Math.floor()并没有比使用Math.round()提供更好的结果：*Math.floor()会导致in=2和u=10'000，因此这些值被分为1位和4位。对这些值使用
Math.round()会导致n=1和u=100，因此这些值被分为3位数和2位数，在我看来，这两位数似乎更平均。Math.floor()会导致in=2和u=10'000，因此这些值被分为2位和4位。对这些值使用Math.round()会导致n=1和u=100，因此这些值被分为4位数和2位数。对于这个范围，两种方法都处于相同的水平-无论哪种方法，您都有一个需要进一步拆分的4位数。
为什么特例处理会出现这样的问题
让我们尝试将数字659'876转换为十进制字符串。
两种方法（使用Math.floor（）和使用Math）。round（））同意在第一步中使用n=2和u=10000。
使用Math.floor（）计算：
（将单个数字值附加到StringBuilder的最后一个递归步骤已被省略）。
使用Math.round（）计算：
使用16'383的示例
你的一条评论声称16'383不能用数学处理。round（），所以让我们再举一个例子。
使用Math.floor（）计算：
（将单个数字值附加到StringBuilder的最后一个递归步骤大部分被省略）。
使用Math.round（）计算：
如您所见，即使使用
Math.round()，将16'384转换为十进制字符串也没有问题。结论
使用
Math.floor()并不适用于所有情况