-
Notifications
You must be signed in to change notification settings - Fork 2
/
integer_multiplication.tex
81 lines (67 loc) · 2.12 KB
/
integer_multiplication.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
\chapter{Integer Multiplication}
Let us consider an integer $X$ which is composed of $X_L$ which are
the leftmost bits of $X$, and $X_R$ which are the rightmost bits of
$X$.
\begin{displaymath}
X = X_L | X_R
\end{displaymath}
We can multiply integers $X,Y$ as follows:
\begin{align*}
XY
&= (2^{n/2}X_L + X_R)(2^{n/2}Y_L + Y_R) \\
&= 2^n X_LY_L + 2^{n/2}X_LY_R + 2^{n/2}X_RY_L + X_RY_R \\
&= 2^n X_LY_L + 2^{n/2}(X_LY_R + X_RY_L) + X_RY_R \\
\end{align*}
Which gives the recurrence
\begin{align*}
T(n)
&= 4T(n/2) + O(n) \\
&\leq 4T(n/2) + cn \\
&\leq 4(4T(n/4) + cn/2) + cn \\
&\leq 4(4(4T(n/8) + cn/4) + cn/2) + cn \\
&\leq 64T(n/8) + cn(1 + 2 + 4) \\
&... \\
&\leq 4^iT(n/2^i) + cn(1 + 2 + ... + 2^{i-1})
\end{align*}
Where $i$ is the number of times we can divide $n$ by 2, or $log_2n$.
\begin{align*}
T(n)
&\leq 4^{log_2n}T(n/2^{log_2n}) + cn(1 + 2 + ... + 2^{log_2n-1}) \\
&\leq n^{log_24}T(n/n^{log_22}) + cn \summ{i=0}{log_2n-1} 2^i \\
&\leq n^2T(1) + cn 2^{log_2n} \\
&\leq n^2T(1) + cn n^{log_22} \\
&\leq n^2T(1) + cn^2 \\
&\leq n^2(T(1) + c) \\
&\leq n^2(O(1) + c) \\
&\leq O(n^2)
\end{align*}
Can we do better? Yes.
We need: $X_LY_L, X_RY_R,$ and $X_LY_R + X_RY_L$
Observe:
%
\begin{align*}
&(X_L + X_R)(Y_L + Y_R) - X_LY_L - X_RY_R \\
&= X_LY_L + X_RY_L + X_LY_R + X_RY_R - X_LY_L - X_RY_R \\
&= X_RY_L + X_LY_R
\end{align*}
Since we must compute $X_LY_L$ and $X_RY_R$ anyway, this saves us an
entire multiplication. Reducing our recurrence from $T(n) = 4T(n/2) +
O(n)$ to $T(n) = 3T(n/2) + O(n)$.
We can solve this new recurrence as follows:
\begin{align*}
T(n)
&= 3T(n/2) + O(n) \\
&\leq 3T(n/2) + cn \\
&\leq 3(3T(n/4) + cn/2) + cn \\
&\leq 3^iT(n/2^i) + cn(1 + 3/2 + ... + (3/2)^{i-1}) \\
&\leq 3^{log_2n}T(n/2^{log_2n}) + cn(1 + 2 + ... + (3/2)^{log_2n-1}) \\
&\leq n^{log_23}T(1) + cn \summ{i=0}{log_2n-1} (3/2)^i \\
&\leq n^{log_23}T(1) + cn (3/2)^{log_2n} \\
&\leq n^{log_23}T(1) + cn n^{log_2(3/2)} \\
&\leq n^{log_23}T(1) + cn n^{log_23 - log_22} \\
&\leq n^{log_23}T(1) + cn n^{log_23 - 1} \\
&\leq n^{log_23}T(1) + cn n^{log_23}n^{-1} \\
&\leq n^{log_23}(T(1) + cn/n) \\
&\leq n^{log_23}(T(1) + c) \\
&\leq O(n^{log_23})
\end{align*}