20-CS-122-001 Computer Science II Spring 2012
Raise x to the power y

Virtual functions, classes, inheritance, lists, queues, stacks, applications

Given: two integers x and y.
Find: xy.

Algorithm:
    Let S be a stack, initially empty
    Repeat the following until y ≤ 1:
       If y is even then push 0 onto S;
       otherwise push 1 onto S.
    Set p = x
    Repeat the following until S is empty:
       Set p = p*p.
       Pop S to q.
       If q equals 1 then set p = p*x.
    Output p