Java/src/main/java/com/others/FastPower.java at Development · ailvcheng/Java · GitHub

36 lines (33 loc) · 1.02 KB

package com.others;

import java.math.BigInteger;

/**

* We may calculate power with loops, but what if the index is too large ?

* FastPower aims to calculate quickly in this circumstances with time complexity O(log k),

* where k is the index.

public class FastPower {

public static BigInteger calculate(BigInteger n, BigInteger k, BigInteger mod) {

BigInteger ans = BigInteger.ONE;

while (!k.equals(BigInteger.ZERO)) {

int odd = k.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO);

if (odd > 0) {

ans = ans.multiply(n).mod(mod);

}

k = k.divide(BigInteger.valueOf(2));

n = n.multiply(n).mod(mod);

}

return ans.mod(mod);

}

public static long calculate(long n, long k, long mod) {

long ans = 1;

while (k != 0) {

if (k % 2 == 1) {

ans = (ans * n) % mod;

}

k >>= 1;

n = (n * n) % mod;

}

return ans % mod;

}

Expand file tree