Karatsuba algorithm: Difference between revisions

Revision as of 01:32, 8 February 2022

Revision as of 05:58, 1 March 2022

Line 60:

:<math>z_1 = (x_1 + x_0)(y_1 + y_0) - z_2 - z_0.</math>

An issue that occurs, however, when computing <math>z_1</math> is that the above computation of <math>(x_1 + x_0)</math> and <math>(y_1 + y_0)</math> may result in overflow (will produce a result in the range <math>B^m \leq \text{result} < 2 B^m</math>), which require a multiplier having one extra bit. This can be avoided by noting that

:<math>z_1 = (x_0 - x_1)(y_1 - y_0) + z_2 + z_0.</math>

This computation of <math>(x_0 - x_1)</math> and <math>(y_1 - y_0)</math> will produce a result in the range of <math>-B^m < \text{result} < B^m</math>. This method may produce negative numbers, which require one extra bit to encode signedness, and would still require one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of <math>(x_0 - x_1)</math> and <math>(y_1 - y_0)</math> to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though <math>(x_0 - x_1)(y_1 - y_0)</math> may be negative, the final computation of <math>z_1</math> only involves additions.

===Example===

Line 88 ⟶ 82:

In a computer with a full 32-bit by 32-bit [[Binary multiplier|multiplier]], for example, one could choose ''B'' = 2³¹ = {{val|2,147,483,648}}, and store each digit as a separate 32-bit binary word. Then the sums ''x''₁ + ''x''₀ and ''y''₁ + ''y''₀ will not need an extra binary word for storing the carry-over digit (as in [[carry-save adder]]), and the Karatsuba recursion can be applied until the numbers to multiply are only one-digit long.

===[[Time complexity]] analysis===

===Asymmetric Karatsuba-like formulae===

Karatsuba's original formula and other generalizations are themselves symmetric. For example, the following formula computes

:<math>c(x)=c_4x^4+c_3x^3+c_2x^2+c_1x+c_0=a(x)b(x)=(a_2x^2+a_1x+a_0)(b_2x^2+b_1x+b_0)</math>

with 6 multiplications in <math>{\text{GF}}(2)[x]</math>, where <math>{\text{GF}}(2)</math> is the Galois field with two elements 0 and 1.

:<math>\begin{align}

\left\{ {

\begin{array}{l}

c_0 = p_0, \\

c_1 = p_{012} + p_{02} + p_{12} + p_2, \\

c_2 = p_{012} + p_{01} + p_{12}, \\

c_3 = p_{012} + p_{01} + p_{02} + p_0, \\

c_4 = p_2,

\end{array}

}\right.

\end{align}</math>

where <math>p_{i}=a_ib_i, \ \ p_{ij}=(a_i+a_j)(b_i+b_j)</math> and <math>p_{ijk}=(a_i+a_j+a_k)(b_i+b_j+b_k)</math>.

We note that addition and subtraction are the same in fields of characteristic 2.

This formula is symmetrical, namely, it does not change if we exchange <math>a</math> and <math>b</math> in <math>p_i, \ \ p_{ij}</math> and <math>p_{ijk}</math>.

Based on the second [[Euclidean division|Generalized division algorithms]],<ref>Haining Fan, Ming Gu, Jiaguang Sun, Kwok-Yan Lam,"Obtaining More Karatsuba-Like Formulae over the Binary

Field", IET Information security Vol. 6 No. 1 pp. 14-19, 2012.</ref> Fan et al. found the following asymmetric formula:

:<math>\begin{align}

\left\{ {

\begin{array}{l}

c_{0}=p_{0} \\

c_{1}=p_{012}+p_{2}+m_{4}+m_{5} \\

c_{2}=p_{012}+m_{3}+m_{5} \\

c_{3}=p_{012}+p_{0}+m_{3}+m_{4} \\

c_{4}=p_{2},

\end{array}

}\right.

\end{align}</math>

where <math>m_{3}=(a_{1}+a_{2})(b_{0}+b_{2}), \ \ m_{4}=(a_{0}+a_{1})(b_{1}+b_{2})</math> and <math>m_{5}=(a_{0}+a_{2})(b_{0}+b_{1})</math>.

It is asymmetric because we can obtain the following new formula by exchanging <math>a</math> and <math>b</math> in

<math>m_{3}, \ \ m_{4}</math> and <math>m_{5}</math>.

:<math>\begin{align}

\left\{ {

\begin{array}{l}

c_{0}=p_{0} \\

c_{1}=p_{012}+p_{2}+m_{4}+m_{5} \\

c_{2}=p_{012}+m_{3}+m_{5} \\

c_{3}=p_{012}+p_{0}+m_{3}+m_{4} \\

c_{4}=p_{2},

\end{array}

}\right.

\end{align}</math>

where <math>m_{3}=(a_{0}+a_{2})(b_{1}+b_{2}), \ \ m_{4}=(a_{1}+a_{2})(b_{0}+b_{1})</math> and <math>m_{5}=(a_{0}+a_{1})(b_{0}+b_{2})</math>.

==[[Time complexity]] analysis==

Karatsuba's basic step works for any base ''B'' and any ''m'', but the recursive algorithm is most efficient when ''m'' is equal to ''n''/2, rounded up. In particular, if ''n'' is 2^''k'', for some integer ''k'', and the recursion stops only when ''n'' is 1, then the number of single-digit multiplications is 3^''k'', which is ''n''^''c'' where ''c'' = log₂3.

Line 154 ⟶ 95:

It follows that, for sufficiently large ''n'', Karatsuba's algorithm will perform fewer shifts and single-digit additions than longhand multiplication, even though its basic step uses more additions and shifts than the straightforward formula. For small values of ''n'', however, the extra shift and add operations may make it run slower than the longhand method. The point of positive return depends on the [[computer platform]] and context. As a rule of thumb, Karatsuba's method is usually faster when the multiplicands are longer than 320–640 bits.<ref>{{Cite web|url=http://www.cburch.com/proj/karat/comment1.html|title=Karatsuba multiplication|website=www.cburch.com}}</ref>

==PseudocodeImplementation==

Here is the pseudocode for this algorithm, using numbers represented in base ten. For the binary representation of integers, it suffices to replace everywhere 10 by 2.<ref>{{cite book |last= Weiss |first= Mark A. |date= 2005 |title= Data Structures and Algorithm Analysis in C++ |publisher= Addison-Wesley|page= 480|isbn= 0321375319}}</ref>

Line 180 ⟶ 122:

return (z2 × 10 ^ (m2 × 2)) + ((z1 - z2 - z0) × 10 ^ m2) + z0

</syntaxhighlight>

An issue that occurs, however, when computing <math>z_1</math>implementation is that the above computation of <math>(x_1 + x_0)</math> and <math>(y_1 + y_0)</math> for <math>z_1</math> may result in overflow (will produce a result in the range <math>B^m \leq \text{result} < 2 B^m</math>), which require a multiplier having one extra bit. This can be avoided by noting that

:<math>z_1 = (x_0 - x_1)(y_1 - y_0) + z_2 + z_0.</math>

This computation of <math>(x_0 - x_1)</math> and <math>(y_1 - y_0)</math> will produce a result in the range of <math>-B^m < \text{result} < B^m</math>. This method may produce negative numbers, which require one extra bit to encode signedness, and would still require one extra bit for the multiplier. However, one way to avoid this is to record the sign and then use the absolute value of <math>(x_0 - x_1)</math> and <math>(y_1 - y_0)</math> to perform an unsigned multiplication, after which the result may be negated when both signs originally differed. Another advantage is that even though <math>(x_0 - x_1)(y_1 - y_0)</math> may be negative, the final computation of <math>z_1</math> only involves additions.

==References==