Problem 2: In class, we saw how to implement exponentiation as a divide and-conq

Question

Problem 2: In class, we saw how to implement exponentiation as a divide and-conquer algorithm. Recall that in this algorithm, we recursively com puted Exple, N) = TN, as TN = (12) % = Epix, A). This method works if N is a power of 2. Provide pseudocode showing how to implement this method for the more general case where N is an arbitrary positive integer. (Hint: Suppose you write an arbitrary positive integer N as N = n; + n 2 + .. + nm, for positive ? Can integers ni, Ga. , no. Then how do you write TN in terms of T' "), J., Tren you find n, values such that each one is a power of 2?).

Explanation / Answer

Here we have a method to find out x^N where N is power of 2

FUNCTION EXP(x,N)
   IF N==1
       RETURN x
   ANS = EXP(x*x,N/2)
   RETURN ANS
  
We need to implement a method for any N. But we only have available function if N is power of 2.

Now, we can write N as sum of powers of 2. How can we do this?
If we write N in binary, each 1 bit corresponds to some power of 2.

Eg 5 in binary is 101. That is 2^2 + 2^0
7 in binary is 111. i.e 2^2 + 2^1 + 2^0

say, we need to find 5^7
5^7 = 5^(2^2+2^1+2^0) ** a^(m+n) = a^m * a^n

   = (5^(2^2))*(5^(2^1))*(5^(2^0))
  
   = EXP(5,2^2)*EXP(5,2^1)*EXP(5,2^0)
  
So, we just need to convert the given N into binary

FUNCTION EXP(x,N)
   IF N==1
       RETURN x
   ANS = EXP(x*x,N/2)
   RETURN ANS
END

FUNCTION EXP2(x,N):
   ANS = 1
   FOR I 0 to 31:
       //Ith bit from left is 1
       IF N&(1<<I)!=0
           ANS = ANS * EXP(x,1<<I)
   RETURN ANS
END

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.