Java: Fast powers with recursion

Raising a number to a huge power one multiplication at a time is too slow. Halve the exponent at each step instead.

What to build

A program that computes B to the power E modulo M with recursion, and counts the calls.

Requirements

  • Write a recursive static long power(long b, long e, long m) as described in the hints, working modulo m at every step.
  • For each line print B^E mod M = R (C calls), where C is the number of calls to power for that line.

Input

Line 1: n. Then n lines B E M.

Output

n lines.

Constraints

1 ≤ n ≤ 50; 0 ≤ B ≤ 10^9; 0 ≤ E ≤ 10^18; 1 ≤ M ≤ 10^9.

Example

Input:

2
2 10 1000
3 0 7

Output:

2^10 mod 1000 = 24 (5 calls)
3^0 mod 7 = 1 (1 calls)

Why it works

Each call halves the exponent, so 10^18 needs only about 61 calls instead of 10^18 multiplications, and taking the remainder after every product keeps each value below 10^18, inside a long.

Examples

Example 1 · Input
2
2 10 1000
3 0 7
Expected output
2^10 mod 1000 = 24 (5 calls)
3^0 mod 7 = 1 (1 calls)
Example 2 · Input
1
5 3 13
Expected output
5^3 mod 13 = 8 (3 calls)

Hints

Hint 1

power(b, e, m): if e is 0 return 1 % m; otherwise compute half = power(b, e / 2, m), square it, and multiply by b once more when e is odd.

Hint 2

Count calls in a static field that the method adds 1 to each time it starts.

Solution

Show one correct solution (try it yourself first)
import java.util.Scanner;

public class Main {
    static int calls = 0;

    static long power(long b, long e, long m) {
        calls++;
        if (e == 0) return 1 % m;
        long half = power(b, e / 2, m);
        long result = half * half % m;
        if (e % 2 == 1) result = result * (b % m) % m;
        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; i++) {
            long b = in.nextLong(), e = in.nextLong(), m = in.nextLong();
            calls = 0;
            long r = power(b, e, m);
            System.out.println(b + "^" + e + " mod " + m + " = " + r + " (" + calls + " calls)");
        }
    }
}

Lesson: Methods →