|
CSE 417, Wi '07: Assignment #5, Due: Friday, March 2, 2007 |
|
 CSE Home |
About Us |
Search |
Contact Info |
Executive Summary: implement the standard "gradeschool" algorithm for integer multiplication as well as Karatsuba's algorithm (Section 5.5), and compare them.
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 "big-O" 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 high-precision arithmetic package, you'd probably choose base 232 or 264 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 n-bit number should be a length n array of ints, each entry of which is either 0 or 1, with the least-significant bit held in array[0], and the most significant bit in array[n-1], etc. For convenience, your top-level function should take as input a pair of character strings of 0's and 1's. As usual, the least-significant bit in a string should be its rightmost character (which will have index n-1 in the character string, the reverse of the array indices); similarly, your printout should put the least-significant bit on the right end. But use the character string representation only for the top-level 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: 11012 = 1*23+1*22+0*21+1*20 = ((1*2+1)*2+0)*2+1 = 1310. I.e., working from most- to least-significant 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).
Be careful about n/2 when n is odd.
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 non-zero 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 2n-1. Instead of calculating x - y for n-bit numbers x and y, we calculate x + (2n - y) = x - y + 2n. In this calculation, (assuming x > y) there will be a "carry" off the left end that we simply ignore (since the 2n spills over into bit n+1), and the remaining n-bit quantity is the correct difference. So we can replace subtraction by addition, plus the simpler problem of subtracting from 2n. For that, simply invert each bit of y (0 <-> 1) and add 1 (which is basically the grade-school borrow method; try it). E.g., for n = 8, negative 1310 becomes 11110010 + 1 = 11110011, and (17-13)10 becomes:
00010001
+ 11110011
----------
00000100
I.e. 17-13=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 Catalyst link on the course homempage, 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 Ideas: 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 grade-school method as the base case for the recursion. What's the right switch-over point? How much faster does this make the algorithm overall? Investigate and report on this.
Redo the Karatsuba implementation with a more realistic radix/base case, e.g., 2k/n=k, perhaps for k=32, or 31, or 16. Pay attention to carries off the left end. Discuss the changes you needed to make. Investigate its speed.
Points: [50 total]
 |
Computer Science & Engineering University of Washington Box 352350 Seattle, WA 98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX |