##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Computing x^n
Given a number and a non-negative integer , compute . For example, and . You could multiply by itself times. That takes multiplications.
But there is a recursive approach that uses far fewer operations. Notice that . Can you see what and have in common? Squaring halves the remaining exponent each step, so the answer arrives in multiplications.