CS435 Extra-credit Assignment

CS435

Extra-credit Assignment 

Late submissions not accepted

Multiply two 3-digit integers with 6 single-digit multiplications

In class, we discussed a divide-and-conquer algorithm (attributed to Karatsuba) to multiply two long integers by dividing the numbers into two halves and using only 3 half-size multiplications, with time complexity ????(????????????????????????) = ????(????????.????????????). In this exercise, we explore dividing the integers into three.

(a) Consider two 3-digit decimal integers ???? = ???????????????????????? and ???? = ????????????????????????. The standard elementary-school method of multiplication requires ???? × ???? = ???? single digit multiply.

???????? ???????? ????????

× ???????? ???????? ????????

________________________________________________________________________

???????????????? ???????????????? ????????????????

???????????????? ???????????????? ????????????????

???????????????? ???????????????? ????????????????

________________________________________________________________________ ???????????????? (???????????????? + ????????????????) (???????????????? + ???????????????? + ????????????????) (???????????????? + ???????????????? ) ????????????????

Let us call the 5 sum terms as (????????, ????????, ????????, ????????, ????????), from left-to-right.

Show how it can be done with only six single-digit multiplications, and some additions/subtractions. Show clearly your 6 multiplication steps, and then show how the sum terms are computed by some additions/subtractions.

(b) Illustrate your algorithm for the example (???????????? × ????????????). (c) Analyze the time complexity of a divide-and-conquer algorithm based on this technique. (The time complexity is worse than Karatsuba algorithm.)