prime
prime

Reputation: 15594

BigInteger power of a BigDecimal in Java

I tried to get the power of a double value where the exponent is very large (Java BigInteger can contain it (the exponent), for example: 10^30)

That is, I want to find something like 1.75^(10^30) or 1.23^(34234534534222).if the output is too large modify it by getting the modulus by a prime like 10^9+7.

If I want to find a power of an Integer I can use BigInteger.modPow() method which take BigInteger arguments:

( BigInteger modPow(BigInteger exponent, BigInteger m) )

As far as i can go this is what i got in Java

new BigDecimal("1.5").pow(1000); // .pow() can get only integers as a parameter , but i want to pass a big number like a BigInteger 

I cannot find an equivalent for that (BigInteger.modPow()) in java for BigDecimal , or i'm missing that.

Are there any ways to do that - Calculate a large power of a floating point number (a Decimal)?

Example of input and output :

Input : num // or 1.5 or any decimal number. can be an integer also.

exponent : exp // big integer or a Long value

output : num^exp // num to ther power exp

i.e like calculating 1.23^(34234534534222)

if the output is too large modify it by getting the modulus by a prime like 10^9+7

Upvotes: 3

Views: 3445

Answers (2)

Marco13
Marco13

Reputation: 54719

There are several caveats. As Gábor Bakos pointed out, the resulting value would most likely contain too many digits to even be represented as a BigDecimal.

Additionally, these number of digits grows quickly, so computing something like 2.034234534534222 is completely out of scope in terms of storage (and, as I assume, in terms of required time).

You mentioned that the value may be computed modulo a large prime when it becomes "too large". Although you did not say what exactly this means, this won't necessarily help you here, because using modulo will not truncate the decimal places. You'll somehow have to limit the precision in which the computation takes place.

However, the most simple implementation using exponentiation by squaring could roughly look like this:

import java.math.BigDecimal;
import java.math.BigInteger;

public class BigDecimalPow {
    public static void main(String[] args) {
        BigDecimal b = new BigDecimal(1.5);
        BigInteger e = new BigInteger("325322");
        BigDecimal result = pow(b, e);
        System.out.println("Done "+result.scale());
        System.out.println(result);
    }


    /**
     * Computes d to the power of e
     * @param b The value
     * @param e The exponent
     * @return The power
     */
    private static BigDecimal pow(BigDecimal b, BigInteger e) {
        BigDecimal result = BigDecimal.ONE;
        BigDecimal p = b;
        int skipped = 0;
        while (e.compareTo(BigInteger.ZERO) > 0) {
            if (e.and(BigInteger.ONE).equals(BigInteger.ONE)) {
                if (skipped > 0) {

                    if (skipped > 29) {
                        p = pow(p, BigInteger.ONE.shiftLeft(skipped));
                    } else {
                        p = p.pow(1 << skipped);
                    }
                    skipped = 0;
                }
                result = result.multiply(p);
            }
            skipped++;
            e = e.shiftRight(1);
            System.out.println(e);
        }
        return result;
    }

}

Note: The implementation above is really simple. There most likely is a solution that is more efficient for some cases, or uses the modulo operation to support "larger" numbers. But you simply can not represent (potentially) 34234534534222 decimal places unless you have 34 terabytes of RAM and a JVM with long addressing, so I doubt that there will be a solution that satisfies the requirements that you stated until now - but would upvote+bounty anyone who proved me wrong...

Upvotes: 0

Narmer
Narmer

Reputation: 1454

There is a Math.BigDecimal implementation of core mathematical functions which has:

static java.math.BigDecimal powRound(java.math.BigDecimal x, java.math.BigInteger n) 
          Raise to an integer power and round.

which seems exactly what you need. The fact that there is an external library for it denotes that there is no core implementation of a method like this in java.Math.

As a side note I can say that if your input is considerably small in terms of decimal places (thus no irrational) just like 1.5 you can transform it in 15/10 and do

(15^BigInteger)/(10^BigInteger)

with the modPow(BigInteger exponent, BigInteger m) of BigInteger. This obviously raises the complexity and the numbers to calculate.

Upvotes: 1

Related Questions