divide and conquer approach for exponentiation?

algorithm divide-and-conquer
andandandand picture andandandand · May 14, 2011 · Viewed 7.3k times · Source

As homework, I should implement a divide and conquer approach for exponentiation of big integers. I know Karatsuba's algorithm for multiplication, what divide and conquer algorithm could I apply to get the result of x^y, both being large integers?.

Answer

Femaref picture Femaref · May 14, 2011

There are a couple of algorithms grouped together under the name square and multiply. You could get some inspiration from them.

Related questions

Difference between Divide and Conquer Algo and Dynamic Programming

What is the difference between Divide and Conquer Algorithms and Dynamic Programming Algorithms? How are the two terms different? I do not understand the difference between them. Please take a simple example to explain any difference between the two and …

Read More
How to find the kth smallest element in the union of two sorted arrays?

This is a homework question. They say it takes O(logN + logM) where N and M are the arrays lengths. Let's name the arrays a and b. Obviously we can ignore all a[i] and b[i] where i > …

Read More
How to optimally divide an array into two subarrays so that sum of elements in both are same, otherwise give an error?

How to optimally divide an array into two subarrays so that sum of elements in both subarrays is same, otherwise give an error? Example 1 Given the array 10, 20 , 30 , 5 , 40 , 50 , 40 , 15 It can be divided as 10, 20, 30, 5, 40 and 50, 40, 15 Each subarray sums up to 105. Example 2 10, 20, 30, 5, 40, 50, 40, 10 The …

Read More