pow for LargeInteger

Question

LargeInteger doesn't seem to have a pow function, or if it does, it cannot process pow(0) though BigInteger can.

I have tried to construct my own, but memory seems to spike badly, and there may be an infinite loop as it runs endlessly:

public static LargeInteger liPow(LargeInteger base, int exponent){
    if(exponent == 0){
        return LargeInteger.valueOf(1);
    }
    else if(exponent == 1){
        return base;
    }
    else{
        for(int i=1; i<exponent; i++){
            base = base.times(base);
        }
        return base;
    }
}

How can a pow method be developed for LargeInteger?

Your not actually computing `pow()`, but some larger function `base^(2^exp)`. — Sirko, Jan 22 '14 at 19:23
@Mysticial Thank you Mystiicial! I will definitely look into that! — , Jan 22 '14 at 19:24
Dammit. I deleted my comment just as you responded. Here it is again: use this algorithm: http://en.wikipedia.org/wiki/Exponentiation_by_squaring — Mysticial, Jan 22 '14 at 19:24
@DavidWallace This is pscience's library. If it's as good as advertised, maybe it won't take a full second to sign ed25519 with java! ;)) — , Jan 22 '14 at 19:27
@DavidWallace Which is why I deleted it in the first place. I thought the OP was trying to sequentially multiply up. — Mysticial, Jan 22 '14 at 19:27

score 4 · Answer 1 · answered Jan 22 '14 at 19:23

Each time through your for loop, you are effectively squaring the result with this line:

base = base.times(base);

You would wind up with base to the power of (2 to the exponent power), not base to the power of exponent.

Start with 1 and multiply in the base each loop.

LargeInteger result = LargeInteger.valueOf(1);
for(int i = 0; i < exponent; i++){
    result = result.times(base);
}
return result;

For optimization, you can try modifying the algorithm to use exponentiation-by-squaring.

Thank you rgettman! I will try to use this after I'm sure `pow` only complains for <= 0. — , Jan 22 '14 at 19:28

score 2 · Accepted Answer · answered Jan 22 '14 at 19:25

2

LargeInteger, being descended from Number does actually have a pow function.

answered Jan 22 '14 at 19:25

Sinkingpoint

7,449
2
29
45

Thank you Quirlom! I've noticed that it doesn't complain when the argument isn't `0`. So I should just check for that instead? Thank you so much in advance! – Jan 22 '14 at 19:27
From the [source](http://grepcode.com/file/repo1.maven.org/maven2/org.jscience/jscience/4.3.1/org/jscience/mathematics/number/Number.java#Number.pow%28int%29) it seems like they throw an exception if the exponent is <= 0 thus I would check if the exponent is 0 and return 1. – Sinkingpoint Jan 22 '14 at 19:28
Thank you again Quirlon! I will look further back in the class "chain" for answers next time now that I know what that is if I at least don't know what it's called. ;)) – Jan 22 '14 at 19:31

pow for LargeInteger

2 Answers2