Given Am n 1 if n 0 2n if m 0 Am 1 Am n 1 otherwise Wri

Given A(m, n) = {1 if n = 0, 2n if m = 0, A(m - 1, A(m, n - 1)) otherwise. Write a program to compute A(2, 5). Let p = 64630798987286520142228435996l937038113215496061434545237. Find the last 6 digits of x = 143^p. The number x is quite large, but last 6 digits of x are only 6 digits long. Try to speed up your program as fast as possible without concerning memory\' space. Output should include the running time of your program and results for A(2, 5) and the last 6 digits of x.

Solution

public class Evaluate
{
   public static void main(String []args)
   {
       System.out.println(\"Value of A(2,5): \"+A(2,5));
       long p=6443079898728652014222843599619370381113215496061434545237;
       long startTime = System.currentTimeMillis();
       System.out.println(\"last 5 digits of 143^p: \",lastFiveDigits(143,p));
       long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println(\"Elapsed time: \"+elapsedTime);
   }
  
   static int A(int m, int n)
{
   if(n==0)
       return 1;
   else if(m==0)
       return 2*n;
   else
       return A(m-1,A(n,m-1));
}

static lastFiveDigits(int num, long p)
{
    String msg=\"\"+Math.pow(num,p);
    return msg.substring(msg.length-5,msg.length);
}

}