Multiplications

Gauss' complex number multiplications

(four multiplications)

(a+bi)(c+di) = ac + (ad+bc)i - bd, i^2=-1

How to do it with 3 multiplications?

(ad+bc) = (a+b)(c+d)-ac-bd

(a+bi)(c+di)=ac-bd+((a+b)(c+d)-ac-bd)i

We need to multiply two n-bit numbers.

X = X1, X2, X3,…,Xn = [Xl, Xr] = 2^(n/2)Xl + Xr (Xl = left part of X, Xr - right part of X)

Y = Y1, Y2, Y2,…,Yn = [Yl, Yr] = 2^(n/2)Yl + Yr (Yl = left part of Y, Yr - right part of Y)

Example:

X=10110111

Xl=1011, Xr=0111

X = 2^4(1011)+0111

X*Y=?

X*Y = (2^(n/2)*Xl+Xr)*(2^(n/2)*Yl + Yr) = 2^n*Xl*Xr + 2^(n/2)(Xl*Yr+Xr*Yr) + Xr*Yr

Time to add two n-bit numbers is O(n).

T(n) is time to multiply two n-bit numbers.

T(n) = 4*T*(n/2) + O(n)

Why?

In the X*Y formula above there are 4 recursive calls multiplying 2 n/2-bit numbers - it makes first part;
Two to the power of n and two to the power of n/2 are all O(n) - it makes second part.

4T(n/2) + cn (for some constant n) = cn + 4T(n/2) = cn + 4 (4T(n/2^2)+c(n/2)) = cn + 4c(n/2) + 4^2T(n/2^2) = cn(1+2) + 4^2*T(n/2^2) =

cn(1+2)+4^2(4T(n/2^3) + c(n/2^2)) = cn (1+2+2^2) + 4^3*T(n/2^3)

If n = 2^k , cn(1+2+2^2+...+2^(k-1))+4^k*T(n/2^k) = cn(1+2+2^2+...+2^(k-1)) + 4^k*1 = (2^k-1)+4^k , because (n/2^k)=(n/n)=1

4^k = (2^k * 2^k) = n*n=n^2 , since n=2^k

T(n) = cn (n-1)+n^2 = cn^2 - cn + n^2 = (1+c)n^2 = O(n^2)