Divide et impera.

Karatsuban algoritmi on hyvä esimerkki siitä, miten jokin "tavanomainen" asia tehdään usein liian vaikeasti, vaikka sopiva abstraktion ymmärtäminen johtaisi johonkin parempaan.

Perinteinen paikkaesityksen (oletetaan kanta "x") perustuva kertolasku perustuu yksinkertaisiin yhteen- ja kertolaskujen "kompositionaalisuuteen": Jos kerromme keskenään luvut a = a0 + a_1*x + ... + a_n*xⁿ ja b = b0 + b_1*x + ... + b_n * xⁿ, niin a*b on näiden summien diskreetti konvoluutio, jonka suoraviivainen laskeminen vaatii O(n²) askelta. Konvoluutio voidaan kuitenkin laskea tavattoman paljon nopeamminkin, ja esimerkiksi Schönhage-Strassenin kertolaskualgoritmi selviää tehtävästä O(n log n) ajassa. Kertaluokkaero ilmenee tosin vasta luvuilla, joissa on luokkaa 40 000 numeroa. Puhumattakaan siitä, että SS-algoritmin kunnallinen ymmärtäminen vaatii melko pitkälle menevää abstraktin algebran tuntemusta.

Karatsuba on kuitenkin selvästi suoraviivaisempi, ja vaikka sen tarjoama asymptoottinen säästö onkin vähäisempi, se on tavattoman yksinkertainen. Pätkäistään a ja b kahteen osaan siten, että
a = u*x^n/2 + v, ja b = y*x^n/2 + z. Tästä näemme yksinkertaisehkolla algebrallisella manipulaatiolla, että
a*b = (u*y)*xⁿ + (u*z + v*y)*x^n/2 + z*v
Nyt jos merkitsemme Huomaamme, että uz + vy = (u+v)(y+z) - uy - zv. Tämän vuoksi riittää, että laskemme kolme kertolaskua: uy, zv ja (u+v)(y+z). Yhteen- ja vähennyslaskut ovat O(n)-aikaisia, joten niiden määrän pieni lisäys ei tässä haittaa. Voimme siis ratkaista n-mittaisten lukujen kertolaskun tekemällä kolme n/2- mittaista kertolaskua ja lisäksi vähän ylimääräisiä yhteenlaskuja. Mitä tästä on hyötyä?

Suoritusaika voidaan ratkaista yhtälöstä: T(n) = 3*T(n/2) + c*n, missä c*n on yhteenlaskuihin kuluva "ylimääräinen" aika. En nyt lähde tässä master-teoreeman todistusta tms. esittämään, totean vain, että tästä saadaan tulokseksi O(n^log_2(3)), eli n:n eksponentiksi jää kaksikantainen logaritmi 3:sta, joka on noin 1.585. Ero ei tunnu merkittävältä, mutta jos n on miljoona, niin tämä funktio on suuruusluokaltaan 3 miljardia, kun taas neliöllinen olisi suuruusluokaltaan biljoona, siis yli kolmesataakertainen. Nykyaikaiset tietokoneet ovat nopeita, mutta niissäkin tämä ero on merkittävä.

Olennaista tässä on abstraktiotason valinta. Perinteinen lähestymistapa on ikäänkuin naimisissa sen abstraktiotason kanssa, jossa luku ikäänkuin "koostuu numeroista". Hajoita-ja-hallitse- periaateessa abstrahoidaan luku koostuvan "isosta puolikkaasta" ja "pienestä puolikkaasta", ja tämä voidaan tehdä esitystavasta riippumatta.

Toinen samaa abstraktioperiaatetta toistava algoritmi on Strassenin matriisikertolasku. Matriisin alkiot jaetaan neljään "kulmapalaan", jonka jälkeen voidaan perinteisen kahdeksan kertolaskun sijaan selvitä seitsemällä; n×n-matriisien yhteenlasku vaatii n² askelta, mutta "perinteinen" kertolasku vaatii n³, ja tässäkin eksponentti voidaan murjoa n. 2.8:aan. (kaksikantainen logaritmi seitsemästä).