CSE 417, Wi '06: Assignment #5, Due: Friday, Mar. 3, 2006

CSE Home

About Us

Search

Contact Info

Reading:

Problem:

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 "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 2³² or 2⁶⁴ 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: 1101₂ = 1*2³+1*2²+0*2¹+1*2⁰ = ((1*2+1)*2+0)*2+1 = 13₁₀, 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).

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 2ⁿ-1. Instead of calculating x - y for n-bit numbers x and y, we calculate x + (2ⁿ - y) = x - y + 2ⁿ. In this calculation, there will be a "carry" off the left end that we simply ignore (since the 2ⁿ 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 2ⁿ. 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 13₁₀ becomes 11110010 + 1 = 11110011, and (17-13)₁₀ becomes:

      00010001
    + 11110011
    ----------
      00000100

Test Cases:

1. 0 * 1,
2. 0111 * 1001,
3. 1001 * 111 (yes, the same answer as before, we hope),
4. 11111 * 11111, and
5. 111010011000001011001111101001101 * 1000110001010011110100111001111011
   (33 & 34 bits resp.; cut & paste these from the web page so you get them right; their product has an especially simple form so it should be obvious if you got it).

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 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.

Points: [50 total + 10 extra]

• 10 points - program that compiles and runs in C, C++, Java, C#, Perl, or Python.
• 10 points - description of your two algorithms. You don't need to repeat the discussion in the textbook or problem statement, but briefly mention what choices you made, especially if it is a detail that we have left vague or unspecified.
• 10 points - running time analysis. Give and justify upper bounds on run time, as a function of n, the length of the longest input number.
• 10 points - measurement and plot. Generate test cases for enough n to show the performance difference between the two algorithms. Do some kind of curve fitting, either with a built-in tool or by dividing by appropriate powers of n and discussing the resulting plot.
• 10 points - test cases. 2 points per case. Cut and paste the terminal window where you ran your test cases, including the commands you used and the output of your program.
• 10 points - extra credit.

	Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cse417-webmaster@cs.washington.edu]