From Mohammed J. Zaki

IntroAlgorithms: Lab2

lab 2: Integer Multiplication ( Due: Jan 31 During Lab)

In this lab you will compare the three different versions of integer multiplication.

BTW, look at the errata for Fig 2.1, listed at: http://cseweb.ucsd.edu/~dasgupta/book/errata.pdf


What to turn in during lab

Your python script should take d, the number of digits, as a command line parameter.

You will need to perform r=10 runs to record the average time to multiply two d-digit integers in decimal using the three methods above.

For each run generate a random pair of integers x and y, that are d digits long, by using random.randint() or similar python function from the random module. (You can generate d random digits, concatenate them and convert into int). Call Method1, Method2 and Method3 on these inputs and record their running time on each pair.

Finally, print the average time for each method over the r=10 runs.

Answer the following questions:

  1. Which method is the fastest? Why? Try different values of d, such as 100, 1000, 10000 and so on to determine the behavior with increasing d.
  2. What is the largest number of digits d you can use to multiply using each method? Record if one or more method fails to run beyond a certain number of digits and reason why?
Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/Lab2
Page last modified on January 29, 2018, at 08:54 PM