java binary exponentiation
/** * Calculate a^n in O(logn) time, instead of O(n) time with naive approach. **/ public static long powerRecursive(int base, int exponent){ if(exponent == 0) return 1; return (exponent % 2 == 0) ? powerRecursive(base, exponent / 2) * powerRecursive(base, exponent / 2) : base * powerRecursive(base, (exponent - 1) / 2) * powerRecursive(base, (exponent - 1) / 2); }