1
$\begingroup$

I'm currently trying trouble to set up the recursive expression for the Karatsuba multiplication of two integers with $n$ and $m$ bits (both having a different number of bits). Usually, the recursion for two $n$ bit integers for Karatsuba multiplication would be:

$T_{n} = \begin{cases} 3T_{n/2} + cn &\mbox{if } n > 1 \\ 1 &\mbox{if } n = 1\end{cases}$

However, when working with two integers with different number of bits, the expression would be different, as we would have $T_{n,m}$ as a recursion. Is there any way to reduce the problem of setting up the recursion in terms of only one variable $n$? I was thinking of letting $T_{n}$ be the maximum number of operations with the pairs $(n,m)$, and basically giving the same recursive formula as stated above. Would that change the running time of the program or is there a more clever way to change it into a one variable recursion?

$\endgroup$
  • $\begingroup$ Why would you want to reduce it to a single variable recurrence? The answer likely depends on both $n$ and $m$. Can you write the two variable recurrence relation? $\endgroup$ – Yuval Filmus Jan 21 '15 at 3:41
  • $\begingroup$ Would the recurrence (for $m, n$ greater than 1) be $3T_{n/2,m/2} + c(n+m)$ where $c$ is a positive constant? I wanted to reduce it to a single variable recurrence so that we could solve it with a method similar to the master theorem (or to find the running time for inputs of size $n, n^{2}$ say). Can it be as well done for recurrences of two variables? $\endgroup$ – arcbloom Jan 21 '15 at 4:03
  • 1
    $\begingroup$ I don't know what the recurrence is, but you better find out, since otherwise you definitely can't solve it! Once you have the recurrence sorted out, you can try to solve it. Use whatever method necessary. The master theorem just codifies results which can be obtained by expanding the recurrence. Hopefully the same technique will work here even though the master theorem itself cannot be applied directly. $\endgroup$ – Yuval Filmus Jan 21 '15 at 4:05
1
$\begingroup$

The recurrence with two variables $n,m$ is as what you have obtained:

$$T(n, m) = 3T(n/2, m/2) + O(\max(n,m))$$

Assume $n = \Omega(m)$. We have

$$T(n, m) = 3T(n/2, m/2) + O(n)$$

Although the master theorem cannot be applied directly, if you expand this recurrence, then you will eventually identify the patterns and the result:

$$T(n, m) = 3T(n/2, m/2) + O(n) = \cdots = \sum_{k=?}^{k=?} (3/2)^{k} \cdot O(n) + c \cdot T(n/m,1) = \cdots$$ Please find out $c$ and the range of $k$, and fill the gaps.


There is a method to reduce the two variables $n,m$ recurrence to a single one:

Assume $n = \max(n,m)$ and pre-append $n-m$ $0$'s to the integer with less bits.

The problem is this will yield a different time complexity from that given above. This can be seen from an extreme example: $1$-bit $\times$ $O(n)$-bit.

$\endgroup$
  • $\begingroup$ It's probably OK to assume the (stronger) $n \geq m$. $\endgroup$ – Yuval Filmus Jan 21 '15 at 13:28

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.