EXPONENTIATION

INCREMENTAL

function exp(int a, int p) returns int  
   if  $p ~ \leq ~0~~\rightarrow$   return  1 
   |  $p ~\gt ~0~ ~\rightarrow$  
      val  :=  a 
      for $i \in [1..p-1] ~~ \rightarrow$  
         val  :=  val*a  
      rof  
   fi 
   return val  
end exp 

EXPONENTIATION

DIVIDE-AND-CONQUER

function exp(int a, int p) returns int  
   if  $p ~ \leq ~0~~\rightarrow$   return  1 
   |  $p ~\gt ~0~ ~\rightarrow$  
      val  :=  exp(a, p/2) 
      if p is even     $\rightarrow$  
         return  val*val  
      |  p is odd     $\rightarrow$  
         return  val*val*a  
      fi 
   fi 
end exp