How to calculate ((Integer)^(double)) % (Integer) in java?

Question

I am trying to calculate the value of (10^5.102103)%24 that is 10 raised to power 5.102103 modulus 24 in Java ?

Which is the best and accurate method to do because

int a;
double b;
int m;

Calculate (a^b)%m

Where a can be very large like upto 10^9

b can be any double or float value which can be large

and m is any Integer

Example ---How you can calculate the value of

(10^10002.3443)%10000007

I know Math.pow(a,b) function works for small a and b only

While BigInteger function Uses only modPow(a,b) where a and b should be integer only(Correct me if i am wrong)

Answer 1

Unfortunately, it's not possible using the normal Java data types to get a correct answer to this. If you use double to store the exponent, you introduce an error, because double won't store most decimal numbers exactly. When you write double b = 10002.3443; the number that is stored in b is actually 10002.34430000000065774656832218170166015625. Even though it looks like 10002.3443 when you print it, that's a trick of the way Java prints numbers - basically it chooses the decimal number with the least number of decimal places that would be represented by that double.

Now this difference looks insignificant. But the difference between 10^10002.3443 and 10^10002.34430000000065774656832218170166015625 is approximately 3.346 x 10^9990, which is a 9991-digit number. Now, what will this difference become when we apply the modulus operator?

(10^10002.34430000000065774656832218170166015625 % 10000007) - (10^10002.3443 % 10000007)
= (10^10002.34430000000065774656832218170166015625 - 10^10002.3443) % 10000007
= (3.346 x 10^9990) % 10000007 (approximately)

Now, it's anybody's guess what that actually comes to. But you've got a better chance of being struck by lightning than of getting the correct answer, if you use double at any point in the calculation.

The other option might be BigDecimal. But the problem is that 10^10002.3443 is irrational - it's not a terminating decimal, so it can't be represented correctly in a BigDecimal.

So Java doesn't have a data type that will allow you to perform the calculation that you want to perform.

You are going to have to invent your own data type, then work out how to do all the bit-crunching to implement exponentiation and modulus. This is a huge project, and I suggest you start out by getting yourself a PhD in mathematics.

(Note: Obviously, I am using ^ to indicate exponentiation and x to indicate multiplication in the above, even though this is not the normal Java convention)

Answer 2

Let's think back to discrete math!

Given y = a ^b (mod m), we know that

y = ((a mod m)^b) mod m

For example, if we have

a = 2, b = 6, m = 5

a raised to the power of b is 64. 64 mod m is 64 % 5 == 4. Let's check our algorithm:

4 == ((a mod m)^b) mod m
4 == ((2 mod 5)^6) mod 5
...
4 == 64 % 5
4 == 4

This doesn't really help us all too much (in its current form), so let's use modular arithmetic at every step to save the day.

int a = 10;
int m = 10000007;
double b = 10002.3443;
int holder = (int) b;
double delta = b - holder; // as close as we're going to get

int total = 1;

for (int i = 0; i < holder; i++) {
    total *= (a % m); // multiply by the modulus
    total %= m;       // take the modulus again
}

total *= (Math.round(Math.pow(a, delta)) % m);
total %= m;