CSE 254, Spring 05, HW A
				T. J. Peters


 For HWA, you are allowed to consult and/or collaborate with others,
 even hand-in a joint report (If so, all participants receive the same
 grade.). 

 When multiplying integers with a very large number of digits, the usual
 base 10 algorithm that we all learned in grade school is not very
 efficient.  This HW will help you to discover those performance
 differences.  Please follow the steps indicated.  The class of
 Tues, 1/25/05 will be left free for you to work on this.  But,
 you will need more time than that so plan accordingly.  The
 assignment is due, hardcopy, word-processed at the beginning of
 class on Tues, Feb. 1, 2005.  It is important that you respect
 this timing, as I will answer questions and go over any subtleties
 at that time.

 HWA implementation:

 A. Read http://en.wikipedia.org/wiki/Multiplication_algorithm
 for a good description of this alternate algorithm.

 B. Read http://www-2.cs.cmu.edu/~cburch/251/karat/index.html,
 which has source code you can use or you can create your
 own implementation.  If you use the cited code, you must
 make reference to this in your submission or lose points for
 failing to do so.

 Things to submit:

 1. Your timing statistics, similar to those tabulated in B, above.
 Your results should be different, but follow a similar patter
 for itegers with more than 8 digits.

 2. A short explanation of how you determined #1.

 3. What are some reasons why your values will be different than
 those reported in B?

 4. Determine where the 'grade school' algorithm is faster
 on your machine and state the maximum number of digits for
 which this is true.

 5. The code created does multiplication in software, but your
 machine likely has its own multiplication implementation.
 Do some experiments to answer the following questions:

 5a. Is your machine supplied multiplication faster than the 'grade
 school' algorithm for some products?  Is this determined by the number
 of digits in each factor?

 5b. Is your machine supplied multiplication faster than the alternative
 multiplication algorithm for some products?  Is this determined by the number
 of digits in each factor?