# Multiplying two integers by dividing each into 3 parts

Integer Multiplication: $$x$$ and $$y$$ are two n-bit integers, where $$n=3^k$$ for some $$k>0$$. We break $$x$$ into three parts $$a$$, $$b$$, $$c$$, each with $$n/3$$ bits; and $$y$$ into three parts $$d$$, $$e$$, $$f$$, each with $$n/3$$ bits. The multiplication is:

$$xy = ad \cdot 2^\frac{4n}{3} + (ae + bd) \cdot 2^n + (af + cd + be) \cdot 2^\frac{2n}{3} + (bf + ce) \cdot 2^\frac{n}{3} + cf$$

The multiplication can be calculated as follows:

$$r_1 = ad$$
$$r_2 = (a + b)(d + e)$$
$$r_3 = be$$
$$r_4 = (a + c)(d + f)$$
$$r_5 = cf$$
$$r_6 = (b + c)(e + f)$$
$$xy = r_1 \cdot 2^\frac{4n}{3} + (r_2 - r_1 - r_3) \cdot 2^n + (r_3 + r_4 + r_1 - r_5) \cdot 2^\frac{2n}{3} + (r_6 - r_3 - r_5) \cdot 2^\frac{n}{3} + r_5$$

Write the recurrence equation representing the algorithm and find the running time of this algorithm (Some logarithms you may need: $$\log{3} = 0.477$$, $$\log{6} = 0.778$$, $$\log{9} = 0.954$$).

For now I am only concerned with the first part of the question (the one asking for the recurrence relation).

What I can deduce from this procedure is that each of the two integers x and y is split into three parts, the variables r1 through r6 are calculated and then summed up using the formula mentioned in the last line of the problem. Since each call results in 6 calls to the same procedure, and the number of additions made is irrelevant of the size of the integer, the recurrence relation is:

$$T(n)=6T(n/3) + \theta(1)$$

Is my reasoning correct?

• We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher.
– D.W.
Jul 31 at 16:21
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. Please give proper attribution to the source of this material!
– D.W.
Jul 31 at 16:22
• @D.W. I will add the text soon, just when I get the time to. Jul 31 at 18:56