Trying to understand sage number system for BigInteger

Question

I have the following sage code that runs instantly (less than a second) and I am trying to convert it to Java (using Java's built-in BigInteger library). But I am not successful.

In short, I initialized N as a BigInteger and delta as double and in order to calculate power (BigInteger ^ double) I converted N to BigDecimal (i.e. new BigDecimal(BigInteger)) and then:

I used this approach but it is too slow (extremely slow).
I used this library but I lost too much precision.
I used this library but I got overflow exception.

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

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

Output:

X:32803899270297070621193977210731234596426011189989730481205367370572340252530823123935195892838208219967066426399488721710159859316222019683979411877007525412864

What is the magic? How sage does this? How to convert this code to Java (and be able to get a similar result), there should be some solution.

In this case I am puzzled by the need for precision beyond what you could get by converting the very large integer to a `double` and exponentiating with `pow()`, because exponentiating to a non-integer power will give an irrational number as a result. — Steve, Jun 11 '16 at 05:58
@Steve I tried it (link: http://pastebin.com/raw/BpGn83Sb) but I get infinity. — Node.JS, Jun 11 '16 at 06:20
I played with the arbitrary precision calculator at http://apfloat.appspot.com , and with `16...91 ^ 0.26` I got `6.6e159` -- pretty poor precision, but the correct number of significant digits. Changing the exponent to `0.260` produced `6.61e159`, another significant digit. However, when I tried `16...91 ^ 0.2600` I got `1.305e160` -- one additional significant digit as expected, but a considerably different result. I'm out of time for now, but maybe later I can work out what the answer is _supposed_ to be. — Steve, Jun 11 '16 at 07:01
The precise result (assuming delta=0.26 exactly) is approximately `3.2803899270296656086551107648280231845 E160`. This differs from your value after about the 14th significant digit. So it seems that sage simply does the calculation in double. — Henry, Jun 11 '16 at 07:51
Just curious: while testing approach #1, did you remove all the `Thread.yield();` statements from the code? Without them it might be _just_ slow, not extremely slow... — Roman, Jun 11 '16 at 10:19
@Roman still too slow after removing Thread.yield(); statements. Program never terminates. http://pastebin.com/raw/HdzJR5qi — Node.JS, Jun 11 '16 at 16:52

score 2 · Accepted Answer · answered Jun 12 '16 at 05:22

You can use approach #1 with a workaround. The problem there is that BigFunctions.ln() is not very effective for numbers with large integer part (number of digits to the left of the decimal point). As a workaround I scaled the number so that it contained at most one digit in integer part and compensated that later by adding ln(10) * rescale * delta to the argument of exp().
You should also note that using new BigDecimal(double) constructor leads to loss of precision - read the javadoc for explanation. Instead you should use new BigDecimal(String) (especially if that double comes from some sort of configuration value), or 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);

Output:

32803899270296656086551107648280231830313861082788744611797945239672375099902513857958219091523648839375388564236289659519690404775361188478777234501437677352644

Trying to understand sage number system for BigInteger

1 Answers1