Eden Example Programs

Karatsuba algorithm (divide-and-conquer)

Karatsuba's algorithm computes the product of two large integers using a divide-and-conquer approach. Let us assume that a long integer is represented in base b as a list of "digits" d.i, where for all i we have 0 <= d.i < b. If two large integers x and y are to be multiplied, the algorithm works as follows:

• Let n be half of the length of the longest of the two integers.
• Let x1 = x/b^n, x2 = x mod b^n, y1 = y/b^n and y2 = y mod b^n.
• Let u = x1 * y1, v = x2 * y2, w = (x1 + x2)(y1 + y2).
• The result of the multiplication is ub^(2n) + (w - u - v)b^n + v.

Notice that it is not necessary to perform any division to obtain x1, x2, y1 and y2. It is enough to cut the lists representing x and y into two halves. The multiplication with bn and b2n only needs appending zeros to the corresponding list. Therefore, only three multiplications are needed, i. e. three sub-problems of length n=2 are generated when splitting a problem. Combining the sub-results has a cost in O(n). This leads to an overall complexity in O(n^(log 3)). This algorithm perfectly fits into a divide-and-conquer scheme. Notice that the granularity of the sub-tasks may not be uniform as the three multiplications are possibly applied to integers of different lengths. Also, trivial nodes may appear at any depth in the tree. The implementation of the Karatsuba algorithm in terms of the divide-and-conquer skeleton dcN is as follows:

type LongInteger = [Int] 
karat :: LongInteger -> LongInteger -> LongInteger
karat is1 is2 = divCon_c trivial solve split combine (is1,is2)

where the code of split and combine follows the patterns described above.
Our parallel implementation of the Karatsuba algorithm works with various divide-and-conquer skeletons, which can be selected in the program call (omit parameters for the program usage).

Download source code