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