keskiviikko 2. kesäkuuta 2010

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*xn ja b = b0 + b_1*x + ... + b_n * xn, niin a*b on näiden summien diskreetti konvoluutio, jonka suoraviivainen laskeminen vaatii O(n2) 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*xn/2 + v, ja b = y*xn/2 + z. Tästä näemme yksinkertaisehkolla algebrallisella manipulaatiolla, että
a*b = (u*y)*xn + (u*z + v*y)*xn/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(nlog_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 n2 askelta, mutta "perinteinen" kertolasku vaatii n3, ja tässäkin eksponentti voidaan murjoa n. 2.8:aan. (kaksikantainen logaritmi seitsemästä).

2 kommenttia:

Ari Timonen kirjoitti...

Abstrakti ajattelu on mielenkiintoinen asia. Olisi mielenkiintoista tietää minkälaisia sanotaanko yhteiskunta-algoritmeja pitäisi soveltaa, jotta ihmisfunktiot saataisiin optimaalisesti tyytyväisiksi ja resurssit tehokkaasti käyttöön. Tässäkin näen, että jos haluaa ymmärtää asiaa tarpeeksi suurella tasolla pitää pystyä aika syvälliseen abstraktiin ajatteluun. Markkinatalous allokoi asiat tehokkaasti, mutta entäpä tietyt ongelmat kuten asymmetrinen informaatio tai tapaukset jossa keskusjohtoinen suunnitelu olisi orgaanista parempaa (kaupunkisuunnitelu).

Odotan vieläkin postausta tuosta epistemelogisesta kysymyksestä. Bryan Caplan ja Peter Boettke ym. väittelivät siis matematiikan käytöstä ja itävaltalaisten praksaelogian selitysvoimaisuudesta. Siellä on mielenkiintoista juttua mm. Kaldors-Hicks -tehokkuudesta, Bayesin menetelmästä, todennäköisyyslaskennasta ja rajahyötykäyrien toimivuudesta (koska utiliteetti on kardinaalinen ei ordinaalinen arvo). Sama väittely on myös videolla tosin huomattavasti "kevyemmin" esitettynä. Luulisi sinuakin kiinnostavan ja Caplan on erittäin karismaattinen. :)

Tietokonealgoritmit, mitä itsekin opiskelen, ovat mielenkiintoisia mutta vain nörteille. Tämä pätee myös merkitsevyyteen. Jos tietää tehokkaan tavan rakentaa koneita, hintajärjestelmä palkitsee. Tälläistä kannustinjärjestelmää ei ole politiikassa.

Mielestäni nykyinen poliittinen prosessi on viallinen. Esim. futuarkia on mielenkiintoinen ehdotus. Tietenkin arvoja ja uskomuksia (belief) ei voida jakaa oikein tehokkaasti eriäviin joukkoihin. Tai oikeastaan ei voida rakentaa mitään objektiivista mittaria mittamaan kansakunnan. BKT on arvoneutraali (sitä ei voi peukaloida hirveästi), mutta se ei kerro kaikkea (ympäristötuhot, tulojakauma), ja HID:t, ISEW:it sun muut on painotettu miten niiden tekijöiden arvomaailman mukaan. Olisi mielenkiintoista, jos demokraattisesti valittaisin mittari, joka kertoo meneekö kansalla hyvin. Poliitikkojen tehtävä olisi sitten saada tämä mittari mahdollisimman paljon plussalle. Hintajärjestelmä ja kaikenkarvaisia järjestelmiä voisi tuunata tähän tarkoitukseen. Intraden tapaisissa palveluissa kyseisen mittarin tuloksella voisi tehdä omaisuuksia.

Tiedemies kirjoitti...

Viitteet ovat erittäin mielenkiintoisia.

Algoritmit sinänsä ovat "vain nörteille", mutta niitä hahmottamalla oppii mielestäni erittäin hyvin ymmärtämään abstraktioita, joita erilaisten prosessien hahmottamiseen vaaditaan. Prosessit voikin ymmärtää usein online-algoritmeina.