Java

Q1. Write two different programs to compute x" mod m (x,n and m are integers > 0). Note that you are not allowed to use "pow" function from library. The modular operator in both C and Python is "%". (a). powmodl(x, n, m) It computes x" mod m by repeated multiplications, i.e. using iteration. [5 marks] (b). powmod2(x, n, m) It computes x" mod m by using the following inductive definition: [5 marks] x mod m 1 x"mod m = (x x mod m)"/2 mod m if n is even x"mod m = (x.xn-mod m) mod m if n is odd Discuss which the above program is more efficient using big-O notation. If you are not sure about which one is more efficient, test your code on computer, using the following data. Present the timing result to support your conclusion For x 29, m 773, use n- 100,000,000, 500,000,000 and 1,000,000,000 [3 marks] *** Q2. The Fibonacci numbers are the numbers in the sequence 1, 1, 2, 3, 5, 8, 13, 21. where each number after the first two is computed by adding the preceding two numbers. Write two different programs fibl(n) and fib2(n) to compute the n-th Fibonacci number. (a). fibl(n) computes the n-th Fibonacci number using iteration (i.e. loop). [5 marks] (b). fib2(n) computes the n-th Fibonacci number using induction (i.e. recursion) [5 marks] Same as the previous question, you need to discuss which the above program is more efficient using big-O notation. If you are not so sure, test your code on computer, using the following data. Present your timing results to support your conclusion. n - 44, 45, and 46 [3 marks) Appendix - Test Data and the Answers 29 100000000 mod 773 - 349, 29 500000000 mod 773 - 16, 29 1000000000 mod 773 = 256 fib(44) = 701408733, fib(45) - 1134903170, fib(46) - 1836311903