The Functions and methods must be in a seperate module/file then the test driver program. Do NOT use any non-standard libiraies. Use C++ for the coding language.

Fast Exponetiation:

Implement a function/method that conducts the fast exponetiation algorithm from section 6.3.1 (see attached image below). (Don't need to specify registers)

The test driver program should call your function with at lease the following values: (3, 5), (4.25, 151), (-7.7, 140), (-7.7, 141), (12,0), (-2, 1)

For each (a,b) pair print the value from your function and the absolute difference of your value from the power(a,b) function with C++ language.

Section 6.3.1

6.3.1 Fast Exponentiation Exponentiating The most straightforward way to compute the bth power of a number a is to multi- ply a by itself b-1 times. But the solution can be found in considerably fewer mul tiplications by using a technique called Fast Exponentiation. The register machine program below defines the fast exponentiation algorithm. The letters x, y, z,r de note registers that hold numbers. An assignment statement has the form "z :-a and has the effect of setting the number in register z to be the number a Fast Exponentiation Program Given inputs a E R,b e N, initialize registers x, y.z to a, 1,b respectively, and repeat the following sequence of steps until termination if z 0 return y and terminate r := remainder(22) z := quotient(z, 2) if r = 1, then y := xy We claim this program always terminates and leaves y = a". To begin, we'll model the behavior of the program with a state machine: 1. states := R R N, 2. start state ::= (a, l, b) 3. transitions are defined by the rule (x2,y, quotient(z,2)) (r2,xy. quotient(z, 2)) if z is nonzero and even x, y, z) if z is nonzero and odd. The preserved invariant P((x. y. z)) will be To prove that P is preserved, assume P((x, y, z)) holds and that (x, y, z) (xr. Vi, zt). We must prove that P((xt, Vt, Z)) holds, that is, (6.2)