关于Java的BigInteger的toString的问题

lymgl2op  于 2022-09-18  发布在  Java
关注(0)|答案(1)|浏览(273)

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]

这似乎是正确的

e3bfsja2

e3bfsja21#

该守则的目的是什么

其目的是找到具有radix^x形式的BigInteger v,其将BigInteger u分成两部分,两部分具有大致相同长度的字符串表示。“完美”值可能是10^x,其中u.sqrt()介于0.5 * 10^x5 * 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_TWOMath.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()会在几个地方出现故障:*
  • 对于值64-127(位长=7),使用Math.floor()会导致n=1和u=100,因此无法拆分值64-99
  • 对于值8'192-16'383(位长=14),使用Math.floor()会导致in=2和u=10'000,因此无法拆分值8'192-9'999
  • 对于值67'108'864-134'217'727(位长=27),使用Math.floor()会导致in=3和u=100'000'000,因此无法拆分值67'108864-99'999'999
  • 对于值9'007'199'254'740'992-18'014'398'509'481'983(位长=54),使用Math.floor()会导致in=3,u=10'000'000'000000'000,因此无法拆分值9'2007'199'254'740992-9'999'999'999999'999

对于这些范围(以及存在较大位长值的其他范围),拆分后需要特殊处理:如果上半部分是BigInteger。然后进行一些特殊处理。但任何一种特殊处理都会使算法更复杂、更容易出错和更慢。

  • 对于其他范围,使用Math.floor()并没有比使用Math.round()提供更好的结果:*
  • 对于值16'384-99'999(位长度从15到17),使用Math.floor()会导致in=2和u=10'000,因此这些值被分为1位和4位。

对这些值使用Math.round()会导致n=1和u=100,因此这些值被分为3位数和2位数,在我看来,这两位数似乎更平均。

  • 对于值100'000-262'143(位长度从17到18),使用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()计算:

  • 在第一步中,659'876被拆分为65和9'877
  • 递归1:65-是一个特例,需要额外的工作才能将其拆分为6和5
  • 递归2:9'876-是一个特例,需要额外的工作才能将其拆分为98和76
  • 递归2.1:98-是一个特例,需要额外的工作才能将其拆分为9和7
  • 递归2.2:76-是一个特例,需要额外的工作才能将其拆分为7和6

(将单个数字值附加到StringBuilder的最后一个递归步骤已被省略)。
使用Math.round()计算:

  • 在第一步中,659'876被拆分为65和9'877
  • 递归1:65分为6和5
  • 递归2:9'876分为98和76
  • 递归2.1:98分为9和7
  • 递归2.2:76分为7和6
    使用16'383的示例

你的一条评论声称16'383不能用数学处理。round(),所以让我们再举一个例子。
使用Math.floor()计算:

  • 在第一步中,16'383分为1和6'383
  • 递归1:1被附加到StringBuilder
  • 递归2:6'383分为63和84
  • 递归2.1:63分为6和3
  • 递归2.2:83-是一个特例,需要额外的工作才能将其拆分为8和3

(将单个数字值附加到StringBuilder的最后一个递归步骤大部分被省略)。
使用Math.round()计算:

  • 在第一步中,16’383被分为163和83
  • 递归1:163被分为16和3
  • 递归1.1:16分为1和6
  • 递归2:83分为8和3

如您所见,即使使用Math.round(),将16'384转换为十进制字符串也没有问题。

结论

使用Math.floor()并不适用于所有情况

相关问题