试图了解 BigInteger 的圣人数字系统

Question

我有以下 sage 代码可以立即运行（不到一秒），我正在尝试将其转换为 Java（使用 Java 的内置 BigInteger图书馆）。但是我没有成功。

简而言之，我将 N 初始化为 BigInteger 并将 delta 初始化为 double 并为了计算幂（BigInteger ^ double) 我将 N 转换为 BigDecimal（即 new BigDecimal(BigInteger)) 然后：

我使用了this方法，但是它太慢了（非常慢）。
我使用了 this 库，但我失去了太多的精度。
我使用了 this 库，但出现溢出异常。

N = 16260595201356777876687102055392856230368799478725437225418970788404092751540966827614883675066492383688147288741223234174448378892794567789551235835087027626536919406320142455677084743499141155821894102610573207343199194327005172833989486958434982393556326206485954223151805798621294965926069728816780985683043030371485847746616146554612001066554175545753760388987584593091716701780398711910886679925612838955858736102229719042291682456480437908426849734556856917891628730543729446245974891735371991588505429152639045721840213451875487038496578525189542369448895368117152818687795094021869963915318643663536132393791
delta = 0.26
X = 2*floor(N^delta) # in sage, ^ operator means exponentiation
                     # similar to ** operator in python

print("X:" + str(x))

输出：

X:32803899270297070621193977210731234596426011189989730481205367370572340252530823123935195892838208219967066426399488721710159859316222019683979411877007525412864

魔法是什么？圣人如何做到这一点？如何将这段代码转换为Java（并且能够得到类似的结果），应该有一些解决办法。

Answer 1

您可以使用方法 1 和解决方法。问题是 BigFunctions.ln() 对于整数部分较大的数字（小数点左侧的位数）不是很有效。作为一种解决方法，我缩放了数字，使其在整数部分中最多包含一位数字，然后通过将 ln(10) * rescale * delta 添加到 exp().
的参数中进行补偿。您还应该注意，使用 new BigDecimal(double) 构造函数会导致精度损失 - 请阅读 javadoc 进行解释。相反，您应该使用 new BigDecimal(String)（特别是如果该双精度值来自某种配置值）或 BigDecimal.valueOf(double).

BigInteger N = new BigInteger("16260595201356777876687102055392856230368799478725437225418970788404092751540966827614883675066492383688147288741223234174448378892794567789551235835087027626536919406320142455677084743499141155821894102610573207343199194327005172833989486958434982393556326206485954223151805798621294965926069728816780985683043030371485847746616146554612001066554175545753760388987584593091716701780398711910886679925612838955858736102229719042291682456480437908426849734556856917891628730543729446245974891735371991588505429152639045721840213451875487038496578525189542369448895368117152818687795094021869963915318643663536132393791");
double delta = 0.26;

// this scale is sufficient to get the exact integer part
// it is roughly equal to the number of digits in the result's integer part
final int SCALE = 170;
BigDecimal x = new BigDecimal(N);
BigDecimal y = BigDecimal.valueOf(delta);

int maxIntDigits = 1;
int intDigits = x.precision() - x.scale();
int rescale = Math.max(intDigits - maxIntDigits, 0);
BigDecimal rescaledX = x.scaleByPowerOfTen(-rescale);

BigDecimal z = BigFunctions.exp(
        BigFunctions.ln(rescaledX, SCALE)
                .add(BigFunctions.ln(BigDecimal.TEN, SCALE).multiply(BigDecimal.valueOf(rescale)))
                .multiply(y),
        SCALE)
        .setScale(0, BigDecimal.ROUND_FLOOR)
        .multiply(BigDecimal.valueOf(2));

System.out.println(z);

输出：

32803899270296656086551107648280231830313861082788744611797945239672375099902513857958219091523648839375388564236289659519690404775361188478777234501437677352644

试图了解 BigInteger 的圣人数字系统

Trying to understand sage number system for BigInteger

java

biginteger

sage