
CSE Home  About Us  Search  Contact Info 
Executive Summary: implement and compare the standard "gradeschool" algorithm for integer multiplication to Karatsuba's algorithm (Section 5.5).
Details: Implement both algorithms. There probably will be some parts in common, e.g. a subroutine for addition. As with the previous assignment, I want you to time them and compare the timings on a range of input lengths, say up to n = 1000 or so. You don't need to do every value of n; just do a dense enough set to clearly show the trend. Also, discuss/analyze how your timing results compare to the theoretical "bigO" analyses for these algorithms.
Both algorithms could easily be done in any base: decimal, binary, base 42, or whatever. In reality, if you were implementing a highprecision arithmetic package, you'd probably choose base 2^{32} or 2^{64} depending on your underlying computer hardware. However, for this assignment, I want you to do it in base 2. In particular, your program's representation for an nbit number should be a length n array of ints, each entry of which is either 0 or 1, with the leastsignificant bit held in array[0], and the most significant bit in array[n1], etc. For convenience, your toplevel function should take as input a pair of character strings of 0's and 1's. As usual, the leastsignificant bit in a string should be its rightmost character (which will have index n1 in the character string, the reverse of the array indices); similarly, your printout should put the leastsignificant bit on the right end. But use the character string representation only for the toplevel input and output; use arrays of ints for the recursion. If the two input strings are of different lengths, treat them as if the shorter were padded with leading zeros to make them of equal length.
Implementation Tips: Hopefully the basic methods for binary arithmetic are clear; please ask if not. For purposes of debugging, you might find it convenient to convert a binary number (of < 32 bits) into an ordinary int. A simple way to do this is basically Horner's rule: 1101_{2} = 1*2^{3}+1*2^{2}+0*2^{1}+1*2^{0} = ((1*2+1)*2+0)*2+1 = 13_{10}, i.e., working from most to leastsignificant bits, double then add each successive bit. Pay close attention to the length needed for various intermediate results. E.g., if x and y are n bit numbers, then x + y may be (n+1) bits (but not longer).
Karatsuba's algorithm uses subtraction as well as addition. You may choose to implement a binary subtraction routine as well as addition. The method is again just like grade school: to subtract 1 from zero, you "borrow" from the next nonzero position to the left. Alternatively, the following trick, known as ``two's complement arithmetic,'' which is exactly what most computers do, is perhaps easier. Note that the largest number that fits in n bits is 2^{n}1. Instead of calculating x  y for nbit numbers x and y, we calculate x + (2^{n}  y) = x  y + 2^{n}. In this calculation, there will be a "carry" off the left end that we simply ignore (since the 2^{n} spills over into bit n+1), and the remaining nbit quantity is the correct difference. So we can replace subtraction by addition, plus the simpler problem of subtracting from 2^{n}. For that, simply invert each bit of y (0 <> 1) and add 1 (which is basically the gradeschool borrow method; try it). E.g., for n = 8, negative 13_{10} becomes 11110010 + 1 = 11110011, and (1713)_{10} becomes:
00010001 + 11110011  00000100I.e. 1713=4, as desired. (The "carry" off the left end is simply ignored.) Slick, eh?
Test Cases:
What to turn in: Again, turn in your program electronically via the turnin form on the course web page, and turn in (in class) a printed version of it together with outputs on the five test cases specified above and your graphs/discussion of performance.
Extra Credit: As mentioned in class, when n is large, the divide and conquer approach is fast, but when n is small, the extra overhead is probably not worth it. Although there are ``software engineering'' drawbacks to this, the fastest approach is probably to do divide and conquer until n is "small" (but bigger than 1 or 2), then switch over to the simpler gradeschool method as the base case for the recursion. What's the right switchover point? How much faster does this make the algorithm overall? Investigate and report on this.
Points: [50 total + 10 extra]
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 981952350 (206) 5431695 voice, (206) 5432969 FAX [comments to cse417webmaster@cs.washington.edu] 