

Main 



Eden Example ProgramsKaratsuba algorithm (divideandconquer)Karatsuba's algorithm computes the product of two large integers using a divideandconquer 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: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 subproblems of length n=2 are generated when splitting a problem. Combining the subresults has a cost in O(n). This leads to an overall complexity in O(n^(log 3)). This algorithm perfectly fits into a divideandconquer scheme. Notice that the granularity of the subtasks 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 divideandconquer skeleton dcN is as follows: where the code of split and combine follows the patterns described above.type LongInteger = [Int] karat :: LongInteger > LongInteger > LongInteger karat is1 is2 = divCon_c trivial solve split combine (is1,is2) Our parallel implementation of the Karatsuba algorithm works with various divideandconquer skeletons, which can be selected in the program call (omit parameters for the program usage). Download source code  
Eden  Parallel Functional Programming. EMail This page: http://www.mathematik.unimarburg.de/~eden 
Last change: 14/06/12  