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()
并不适用于所有情况