Divide & Conquer – Karatsuba Algorithm
Rang leh chak taka number puntir hi a pawimawh em em a. Kum 1960 hmalamah kha chuan pawl thum vela kan inzirtir dan ang bak hi Number pahnih puntir dan tha leh rang a la awm lo hrim hrim a ni. Hemi danah hi chuan number pahnih chu a digit awm zat ang zela puntir a ngai tihna a ni a. 234×314 hi kan puntir dawn chuan 32 (9) kan puntir a ngai tihna a ni. Hetianga a mal te tea puntir lova puntir dan thar hi kum 1960 khan Karatsuba’n a lo hmuchhuak a, chu chu Karatsuba Algorithm tiin vawiin thlengin sawi a lo ni ta a. Computer Science leh thil dangah pawh rang tak leh dik taka puntir theih hi a pawimawh em avangin Computer zirlai te chuan hei hi kan hriat ngei a tha a ni. Karatsuba Algorithm hian Divide and Conquer = thendarh a hneh kalphung a hmang a. Number puntir tura chawh ngai a ron ti tlem sawt a ni. Number puntir dan pangaiah chuan Θ(n2) hi kan chawh dan kal hmang a ni a. Karatsuba Algorithm-ah thung chuan Θ(nlog23)≈Θ(n1.585) kalphung hmanga chawh tur a ni thung a, chawhtur a tlem sawt tih a exponent atang hian kan hmu thei ang. Number lian thamah chuan chawhtur step khat leka tlem pawh hi a hlu em em a, Computer science lamah pawh tihdan phung tlem leh dik apiang hi good algorithm an ni zel a ni.
Karatsuba Algorithm (KA)-ah chuan number te zawk hmanga number kan puntir theih nan number lian te chu number te-in a thensawm vek a, hei hi number system dang dang, binary, hexa, octal. etc ah pawh a hman vek theih a ni. Number kan puntir dan pangai hi lo en phawt ila
hi vertical multiplication tih a ni a. Number kan puntir dan tlanglawn ber a ni a. A then chuan 45×32 a kham phei zawnga ziakin an dah bawk a. A puntir dan step erawh a ngai reng thung a ni. Divide & Conquer kalphung ang chuan, A veilam zawk kha high bits \( H \) tiin a dinglam zawk kha Low bit \(L\) tiin hming an pe a. Number puntir tur pahnih te chu \(x\) leh \(y\) angah lo ngai ta ila a hnuaia mi ang hian a semdarh a ni.
\( x = x_Hb^\frac{2}{n}+X_L \) = 45
\( y = y_Hb^\frac{2}{n}+Y_L \) = 32
A hnuaia mi ang hian a puntir thung a ni.
\(xy = (x_Hb^\frac{2}{n}+X_L) \times (y_Hb^\frac{2}{n}+Y_L) \)
\( = x_Hy_Hb^\frac{n}+(x_Hy_L+x_Ly_H)b^\frac{n}{2}+x_Ly_L \)
He formula hmang hian a chunga verticle/horizontal multiplication kalphung ang thovin Divide & Conquer pawhin chawh dan step a nei tlem chuang lo tih kan hmu thei a. Kan hmuh ang hian puntirna hmun li-ah a awm a, chu chu \(x_Hy_Hb^\frac{n} , (x_Hy_L)b^\frac{n}{2}, (x_Ly_H)b^\frac{n}{2} \) leh \(x_Ly_L\) te an ni a. Running time pawh O(n2) tho a ni.
He dan hmang hian base-10 numbers 1235 leh 8765
\( x = x_Hb^\frac{n}{2} + X_L \)
\( = 12 \times 10^2 + 34 \)
\( y = y_Hb^\frac{n}{2} + Y_L \)
\( = 87 \times 10^2 + 65 \)
\(xy = (x_Hb^\frac{n}{2} + X_L) \times (y_Hb^\frac{n}{2} + Y_L) \)
\( = (12 \times 10^2 + 34) \times (87 \times 10^2 + 65) \)
\( = x_Hy_Hb^\frac{n}+(x_Hy_L+x_Ly_H)b^\frac{n}{2}+x_Ly_L \)
\( = 12 \times 87 \times 10^4 + (12 \times 65 + 34 \times 87) \times 10^2 + (65 \times 34) \)
Karatsuba Algorithm
- \( a = x_Hy_H \)
- \( d = x_Ly_L \)
- \( e = (x_H + x_L) (y_H + y_L) – a – d \)
- \( xy = ab^n + eb^\frac{n}{2} + d \)
Number digit pakhat aia tam reng reng chu digit khat a nih hma a then te zel phawt a ni. Ti chuan formulaa kan hmuh ang hian \(a, d, e\) ah chiah puntirna kan hman a ngai a, a bak chu belh leh \(e\)-ah paih kan hmang a nih hi. Entirna nen a takin KA hi hmang dawn ila:
Q. 1234 × 4321 = ?
Sol: A hmasa berin \(a\) value hi kan chawh chhuah phawt a ngai a. Number digit a tam dan a zirin a value chawh nawn (then tet nan) ngai zat hi a danglam theih vangin kan a value hmasa ber atan \(a_1\) tiin kan dah ang. Formula-a kan hmuh ang hian \(x\) high leh \(y\) kan neih a ngai a. \(x\) leh \(y\) te hian 4 bit (4 digit) an nei ve ve a. A veilam digit 2 ve ve te hi hight bit chu a ni dawn tihna a ni. Tichuan
\(a_1 = 12 \times 43 \) KA kan hman tawh dawn avangin hei pawh hi a la then tet leh theih a ni a, single digit a ni lo miau a. Tuna kan thendan phung bawka zuk then tet leh kha recursion tiin an sawi. Maherawh chu recursion kan tih hmain \(d_1\) leh \(e_1\) value hi kan zawng leh phawt ang. \(d\) hi lower bit sawina a ni a, tichuan kan zawhnaah hian 4 digit kan nei a, kan lower bit tur chu high bit ni lo zawng kha a ni mai a. Ti chuan,
\(d_1 = 34 \times 21\) – Single digit a la nih miau loh avangin kan thentet (Recursion) leh a ngai dawn tih hria ila.
\(e\) tlukpui formula kha han en let leh phawt ila
\(e = (x_H + x_L) (y_H + y_L) – a – d \) hi kan chawh tur number hmang khan thlak ta ila
\(e = (12 + 34) \times (43 + 21) – a_1 – d_1 \). Awle, kan hmuh ang hian \(a_1\) leh \(d_1\) value kan hriat hma chuan chawhchhunzawm theih a ni tawh lo va. Chuvangin kan High bit leh Low bit kha then te (recurse) leh phawt ila.
\(a_1 = 12 \times 43 \) hi kan then tet leh chuan a high atan \(a_2\) angin kan dah ang a, a low atan \(d_2\) kan dah thung ang
\(a_2 = 1 \times 4 = 4 \)
\(d_2 = 2 \times 3 = 6 \)
Kan hmuh ang hian \(a_1\) then tet leh (resurce) chu 1 × 4 = 4) a ni a, high bit a nih hi. \(d_2\) pawh 2 × 3 =6 = low bit. kan \(e\) formula pawh \(e_2\) a ni tawh ang a.
\(e_2 = (1+2)(4+3) – a_2 – d_2 \)
\( = (1+2)(4+3) – 4 – 6 \)
\( = 11 \)
Kan \(xy\) formula en leh ila \(xy = ab^n+eb^\frac{n}{2}+d\). Kan value neih hmanga kan thlak chuan
\(a_1 = 12 \times 43 \)
\(a_1 = 4 \times 10^2 + 11 \times 10 + 6 = 516 \)
\(a_1\) value kan nei ta a, \(d_1\) zawng ve leh ila.
\(d_1 = 34 \times 21 \)
\(a_2 = 3 \times 2 = 6 \)
\(d_2 = 4 \times 1 = 4 \)
\(e_2 = (3 + 4) (2 + 1) – a_2 – d_2 \)
\( = 11 \)
\(xy = ab^n+eb^\frac{n}{2}+d \) hi a tluk avangin
\(d_1 = 34 \times 21 \)
\(d_1 = 6 \times 10^2 + 11 \times 10 + 4 = 714 \)
\(e_1\) value tur kan zawng leh ang.
\(e_1 = (46 \times 64) – a_1 – d_1 \)
\(a_2 = 4 \times 6 = 24 \)
\(d_2 = 6 \times 4 = 24 \)
\(e_2 = (4 + 6) (6 + 4) – a_2 – d_2 \)
\( = 52 \)
\(xy = ab^n+eb^\frac{n}{2}+d \) hi a tluk avangin
\(e_1 = (46 \times 64) – a_1 – d_1 \)
\( = 24 \times 10^2 + 52 \times 10 + 24 – 714 – 516 \)
\( = 1714 \)
Tichuan \(a_1, d_1\) leh \(e_1 \) te theuha kan value neih tak te chu
\(a_1 = 516 \)
\(d_1 = 714 \)
\(e_1 = 1714 \)
\(xy = ab^n+eb^\frac{n}{2}+d \) kan formula-ah khung ta ila
\(xy = (516)10^4 + (1714)10^2 + 714 = 5332114 \)
Rang taka hman chhuah dan tarlang ve hrim hrim ila, formula leh rem kual vel ngai a tam hian hriatthiam a har thin a. Kan puntir tur kha \(1234 \times 4321 \) a ni a. A hnuaia mi ang hian
Step 1: \(12 + 34 = 46 \) (Chawh dan chipchiar zawkah chuan 1 + 2 angin a thensawm lehna tang hian kan chawk zawk thin)
Step 2: \(43 + 21 = 64 \)
Step 3: \(12 \times 43 = 516 \)
Step 4: \(34 \times 21 = 714 \)
Step 5: \(46 \times 64 = 2944 \)
Step 6: \(516 + 714 = 1230 \)
Step 7: \(2944 – 1230 = 1714 \)
Step 8: \(516 \times 100^2 = 5160000 \)
Step 9: \(1714 \times 100 = 171400 \)
Step 10: \(714 + 5160000+171400 = 5332114 \)
Detail zawka kan chawh chuan a hnuaia mi ang hian a ni ang
Step 1: \(12 + 34 = 46 \)
Step 2: \(43 + 21 = 64 \)
A chunga result hi kan chawk te (then te) leh phawt ang.
Step 3: \(4 + 6 = 10 \)
Step 4: \(6 + 4 = 10 \)
Step 3 leh 4-a + veilama awm ve ve 4 leh 6 te hi kan multiply ang. Hetiang bawkin a dinglama 6 leh 4 te pawh, 10 ve ve te pawh hi multiply tho tur.
Step 5: \(4 \times 6 = 24, 6 \times 4 = 24, 10 \times 10 = 100 \)
Step 5-a 24 ve ve te hi belha, a chunga 100 lo chhuak atang hian paih tur.
Step 6: \(24 + 24 = 48 \) 100 atangin kan paih leh ang. \(100 – 48 = 52 \)
Step 6-a 24 hmasa zawk hi digit hnih a nih angin \(10^2 \) hmangin kan multiply ang
Step 7: \(24 \times 10^2 = 2400 \)
A chunga 52 kan tihchhuah hi 10-in kan multiply leh ang
Step 8: \(52 \times 10 = 520 \)
Step 5-a 24 kan tihchhuah hnuhnung zawk leh 2400 leh 520 te hi kan belh leh ang
Step 9: \(24 + 2400 + 520 = 2944 \)
Step 1 leh Step-2 mi te khi digit 2 an la nih avangin kan then te leh ang. A chawhdan phung chu a chunga mi nen hian a in ang reng. High bit chawk hmasa phot ila
Step 10: \(1 + 2 = 3 \)
Step 11: \(4 + 3 = 7 \)
Step 12: \(4 \times 1 = 4 \)
Step 13: \(2 \times 3 = 6 \)
Step 14: \(7 \times 3 = 21 \)
Step 12 leh 13 result hi belh leh tur
Step 15: \(4 + 6 = 10 \)
21 atangin 10 hi kan paih leh ang
Step 16: \(21 – 10 = 11 \)
Step 17: \(4 \times 10^2 = 400 \)
Step 18: \(11 \times 10 = 110 \)
Step 19: \(6 + 400 + 110 = 516 \)
Low bit chawk leh ila:
Step 20: \(3 + 4 = 7 \)
Step 21: \(2 + 1 = 3 \)
Step 22: \(3 \times 2 = 6 \)
Step 23: \(4 \times 1 = 4 \)
Step 24: \(7 \times 3 = 21 \)
Step 25: \(6 + 4 =10 \)
Step 26: \(21 – 10 = 11 \)
Step 27: \(6 \times 10^2 = 600 \)
Step 28: \(11 \times 10 = 110 \)
Step 29: \(4 + 600 + 110 = 714 \)
Low bit result kan nei leh ta.
Step 30: \(516 + 714 = 1230 \)
Step 31: \(516 \times 100^2 = 5160000 \)
Step 32: \(2944 – 1230 = 1714 \)
Step 33: \(1714 \times 100 = 171400 \)
Step 34: \(714 + 5160000+171400 = 5332114 \)
Python hmanga kan dah dawn chuan a hnuaia mi ang hian function kan ziak ang.
from math import ceil, floor
def karatsuba(x,y):
#base case
if x < 10 and y < 10: # x leh y te hi single digit an nih chuan
return x*y
n = max(len(str(x)), len(str(y)))
m = ceil(n/2) #n hi float number a lo nih palh takin integer-ah chantir nan.
x_H = floor(x / 10**m)
x_L = x % (10**m)
y_H = floor(y / 10**m)
y_L = y % (10**m)
#recursive steps (chawh sawm lehna)
a = karatsuba(x_H,y_H)
d = karatsuba(x_L,y_L)
e = karatsuba(x_H + x_L, y_H + y_L) - a - d
return int(a*(10**(m*2)) + e*(10**m) + d)
#print(karatsuba(12,12))
#print(karatsuba(0,0))
#print(karatsuba(1234,4321))
#print(karatsuba(3141592653589793238462643383279502884197169399375105820974944592,2718281828459045235360287471352662497757247093699959574966967627))
Ref: Detail explanation
