CSC 451.1: Topics in Theoretical Computing Science 1

FALL 1998-99

Assignment #1

Instructor: Dr. Pawan Lingras

 Due Date: September 23,1998

Write two functions to multiply two large integers for any base b. One of the functions will use the algorithm for multiplication of large numbers given in Chapter 1. The second function will use the method for multiplying large numbers that you learned in grade school. Compile and run the program. Your output should confirm that both the functions produce the same results, and should also include the run-time required for both the methods.

On a separate paper provide run-time and memory requirement comparisons for both the algorithms. Explain, with the help of an example, how the algorithm for multiplying the large numbers can also be used for multiplying large polynomials.