Program #4

Implement the following mathematical methods using recursion. You can make these static methods in class Assign4, and provide a test program, in which the parameters are fifty digits each.

In your implementation, the parameters are of type java.math.BigInteger. Both mathematical methods that I am asking you to implement are in the Java library, so you can use the Java library to check your answers. However, you should only be using the following BigInteger methods: mod, add, equals, compareTo, multiply, shiftRight.

  1. Greatest Common Divisior: the greatest common divisor of m and n, written gcd(m,n) is the largest integer that divides both. We assume that both m and n are positive. If either m or n is 1, then the greatest common divisor is 1. For instance, 
    gcd(1,10) = 1
gcd(5,15) = 5
gcd(10,10) = 10
gcd(10,15) = 5
gcd(24,50) = 2
gcd(100,81) = 1
    Note that if m is larger than n, gcd(m,n)=gcd(n,m%n).
  2. Power: Raise a number to a non-negative power. To compute pow(x,n) note that if n is even (but not zero), then you can compute pow(x*x,n/2), and if n is odd, then you can compute pow(x,n-1)*x.