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