How fast can we multiply

TA NHAN NHANH N M C NAO?
Nguy n T n Thong
Ngay 30 thang 7 nm 2011
Lo t bai v phep nhan sau ay co th xem la m t b n l t d ch + them b t c a tac gi t
m c 4.3.3 [How fast can we multiply?] trong cu n The Art of Computer Programming
- Volume 2.
1
Phat bi u bai toan
Cho hai s U, V bi u di n
c s b b t ki:
U = (un-1un-2 * * * u0)b
V = (vn-1vn-2 * * * v0)b
H i: s phep toan c n thi t tinh U x V [v i k t qu tr v c bi u di n
c s b]?
gi i quy t tr n v n v n ta s duy t qua cac y t ng [k c nh ng y t ng n gi n
nh t], tim cach hoan thi n cac y t ng nay.
2
Thu t toan "th ngay"
Ta b t u v i y t ng th c hi n phep nhan th ng c d y cho h c sinh ti u h c.
Vi d :
1 2 3 4
x
2 3 1 4
----------------
4 9 3 6
+
1 2 3 4
3 7 0 2
1

---

2 4 6 8
----------------
2 8 5 5 4 7 6
Ro rang thu t toan nay co ph c t p la O(n2) v i n la s ch
s trong bi u di n c a
cac nhan t d i m t c s b t ki ( vi d tren la c s 10.) N u 2 s co dai1 khac nhau
(1234 x 23, ch ng h n) ta l y n b ng chi u dai c a s dai hn va them cac s 0 vao bi u
di n c a s con l i.(1234 x 0023, n = 4)
Cach th c hi n la v y, nhng b n co bao gi
t
h i vi sao thu t toan nay ho t ng
UNG khong? Ta th tim hi u, bi t au l i co m t y t ng nao o.
L y t vi d tren [cho ti n]:
1234 = 1 x 103 + 2 x 102 + 3 x 101 + 4 x 100
2314 = 2 x 103 + 3 x 102 + 1 x 101 + 4 x 100
1234 x 2314 = (1 x 103 + 2 x 102 + 3 x 101 + 4 x 100)
x (2 x 103 + 3 x 102 + 1 x 101 + 4 x 100)
Gi thi ta dung tinh ch t k t h p c a phep nhan [a x (b + c) = a x b + a x c)] cung m t
chut tinh y v cach t v tri c a cac k t qu hi u ro vi sao khi con ti u h c ta co th
nhan chinh xac.
Ta nh n th y thu t toan "th ngay" tach 2 s h ng thanh t ng ph n nh r i th c hi n
nhan k t h p hai s v i nhau. Ta th tach theo m t cach khac xem k t qu co kh quan
hn khong?
V i hai s u, v
d ng u = (u2n-1u2n-2 * * * u0)2, v = (v2n-1v2n-2 * * * v0)2 [co 2n ch s , c
s 2]
Ta khong tach u thanh u2n-1, u2n-2, * * * u0 ma thanh ua, ub sao cho
u = ua x 2n + ub
[t c ta chia oi u thanh uava ub]
Tng t ta bi u di n v = va x 2n + vb.
Th c hi n tng t thu t toan ngay th, ta co:
u x v = (ua x 2n + ub) x (va x 2n + vb)
= ua x va x 22n + (ua x vb + ub x va) x 2n + ub x vb
(1)
ay n u c
"ngay th" th c hi n ua x va, ua x vb, ub x va, ub x vb, thi ta t n 4 phep
nhan va 3 phep c ng. Th c hi n cac phep nhan nay m t cach qui ta co th i gian th c
1Ta hi u dai c a m t s la dai c a bi u di n s o d i m t c s b t ki.
2

---

hi n thu t toan:
T (2n) 4 x T (n) + cn
v i c la m t h ng s dng nao o.
Sau tinh toan ta l i c T (n) = O(n2), khong co s c i thi n nao so v i thu t toan "th
ngay".
B n co nh n ra la n u mu n gi m s phep tinh t ng th , thi ta ph i tim cach gi m s
phep nhan th c hi n (1).[co th tng s phep c ng nh la m t hi u ng ben l ]
M o tinh toan2 sau giup ta th c hi n c mong mu n:
x = ua x va
y = ub x vb
z = (ua + ub) x (va + vb)
k = z - x - y = ua x vb + ub x va
V i 3 phep nhan va 4 phep c ng (tr ) ta c x, y, k.
Tinh toan l i th i gian th c hi n c a thu t toan, ta co:
T (2n) 3T (n) + cn
Ch ng minh b ng qui n p, ta c:
T (2k) c(3k - 2k)
hay
T (n) = O(nlg(3))
[lg(3) 1.585]
Y t ng [nay] c a A. Karatsuba (1962) a giup ta a ti n c m t b c tren ng
con ng chinh ph c phep nhan.
bai ti p theo ta s y y t ng nay n gi i h n t
1+
3.5

m t k t qu c T (n) = O(n
lg(n) ).
2M o nay kha gi ng v i m o do Volker Strassen ngh ra khi c g ng c i thi n t c nhan hai ma tr n
va k t qu t c cng gi ng v i k t qu ta t c
tre.
3

---