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.
- 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).
- 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.