0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jul 31 at 16:21
  • $\begingroup$ 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! $\endgroup$
    – D.W.
    Jul 31 at 16:22
  • $\begingroup$ @D.W. I will add the text soon, just when I get the time to. $\endgroup$
    – Wais Kamal
    Jul 31 at 18:56
1
$\begingroup$

Close. But consider that for example a+b isn’t an n/3 bit but an n/3 + 1 bit number, and the additions take not O(1) but O(2n/3) operations.

$\endgroup$
1
  • $\begingroup$ It is given in the question that n is a power of 3. $\endgroup$
    – Wais Kamal
    Jul 31 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.