Exercise $5.$ For cryptographic purposes, we need a function to compute powers: given integers

a$,$ n $>=1,$ return a

n $=$ a $$ a $...$ a$,$ where the number of a is n$.$ Multiplication is expensive so we

want to use as few of those as possible. Note that the naive approach to compute a

n uses n $1$

multiplications.

$1.$ Justify that the function pow computes a

n

$.$ How many multiplications does it perform, asymptotically, as a function of n$?$

$1$ static long pow $($ long a $,$ long n $)\{$

$2$ if $($ n $==0)$ return $1$;

$3$ long res $=$ pow $($a $,$ n $/2)$ ;

$4$ return n $\%2==1?$ res $*$ res $*$ a : res $*$ res ;

$5\}$

$2.$ Can you re$-$write the function pow without using recursion?