$[Matematiikkaa]$

Paimentolaisten kertolasku

Seuraavassa lainauksessa [1] esitetty algoritmi vaikuttaa ensilukemalla melko mielenkiintoiselta.

Egyptiläisten luku-, kirjoitus- ja laskutaidottomien paimenten lammaskaupanteko on näkemisen arvoista puuhaa. Tämä johtuu heidän lievästi sanoen uskomattomasta kertolaskumenetelmästään. Kuulin siitä aikoinani Damasissa, mutta en käsittänyt sitä, enkä rehellisesti sanoen käsitä sitä vieläkään. Kaupankäynti käy seuraavasti: Ostaja ja myyjä istuvat hiekalle vastakkain ja piirtävät maahan kepillä ristin. Käytyään arabialaiseen kulttuuriin kuuluvan tinkimisseremonian läpi, he lopulta pääsevät sopimukseen hinnasta. Sanotaanpa vaikka 14 lammasta 60 dinaaria kappale. Ristin yläpuolelle asetetaan vierekkäin lampaita vastaava määrä pieniä kiviä ja toiselle puolelle sovittu dinaarimäärä. Nyt aletaan toiselta puolelta kaksinkertaistamaan kivien määrää, ja toiselta puolelta puolitetaan. (On muuten yksi lysti kummalta puolelta lähtee vähentämään ja nostamaan.) Jos esimerkiksi luku 7 joudutaan puolittamaan saadaan tietysti kolme ja puoli, mutta puolikkaita ei yksinkertaisesti lasketa (eihän kiviä voi puolittaa).Kun vähenevältä puolelta lopulta vääjäämättä päädytään lukuun yksi, seuraa uskomattomin manööveri: vähennettävältä puolelta etsitään kaikki kivikasat, joissa symboleja on parillinen määrä. Koska parillinen luku on "epäpyhä", nämä kivet yksinkertaisesti poistetaan mukaanlukien vastakkainen puoli. Sitten vain lasketaan yhteen tuplattujen puolella olevat kivet. Suorastaan taianomaisesti päädytään aina oikeaan lopputulokseen. Edes matematiikan opettajani ei pystynyt ratkaisemaan menetelmää, mutta totesi siihen liittyvän toki jokin luonnollinen selitys. Olen kokeillut menetelmää kaikilla mahdollisilla luvuilla ja aina se toimii. Olen demonstroinut kummallista laskutapaa muutamalla esimerkillä. Ottakoon selvää kuka osaa.
   6 | 7     5 | 8    17 | 9    18 | 11   25 | 12   13 | 7
 ----+---  ----+---  ----+---  ----+---  ----+---  ----+---
  12 | 3    10 | 4    34 | 4    36 | 5    50 | 6    26 | 3
  24 | 1    20 | 2    68 | 2    72 | 2   100 | 3    52 | 1
     |      40 | 1   136 | 1   144 | 1   200 | 1       |
 ----+---  ----+---  ----+---  ----+---  ----+---  ----+---
  42 |      40 |     153 |     198 |     300 |      91 |

Pari kommenttia:

Matematiikanopettaja hävetköön.
Mahtoikohan kirjoittaja sittenkään kokeilla ihan kaikilla mahdollisilla luvuilla...
Algoritmi tunnetaan myös nimellä venäläisen talonpojan kertolasku (Russian peasant's algorithm), koska se oli yleisesti käytössä Venäjällä 1800-luvulla. [2].

Ilonpilaus

Tämä on taas yksi hieno asia, josta liika opiskelu vie hohdon. Tutkitaan kertolaskua a × b kyseisellä menetelmällä. Valitaan puolitettavaksi luvuksi b ja tuplattavaksi luvuksi a. Luku b voidaan esittää yksikäsitteisesti kakkosen potenssien summana:

b = sum( b(i)*2^i, i=0..m ),

missä kertoimet b₀...b_m ovat nollia tai ykkösiä. Toisin sanoen esitetään b binäärimuodossa. Ylläesitetty algoritmi suorittaa ihan tavallisen binäärilukujen kertolaskun allekkain. Juttu näyttää hienolta, koska kymmenjärjestelmän käyttö piilottaa bittien vilinän. Seuraava mahdollisesti selvittänee, mistä on kysymys.

Bitti	Kerrottava	Kertoja
0	a = 2⁰×a	b = 2^mb_m + ... + 2b₁ +	b₀
1	2×a	2^m-1b_m + ... + 2b₂ +	b₁
2	2²×a	2^m-2b_m + ... + 2b₃ +	b₂
...	...	...
m-1	2^m-1×a	2b_m +	b_m-1
m	2^m×a		b_m = 1
	Tulo: a × (b₀ + 2b₁ + 2²b₂ + ... + 2^m-1b_m-1 + 2^mb_m) = ab

Taulukon k:nnella rivillä oikean sarakkeen luku on pariton, jos kerroin b_k on yksi. Tällöin lopuksi laskettavaan summaan otetaan mukaan termi a × 2^k = a × b_k × 2^k. Jos taas b_k = 0, niin oikeassa sarakkeessa oleva luku on parillinen (epäpyhä). Tällaiselta riviltä summaan tulee termi a × b_k × 2^k = 0, eli ei mitään. Näin a:n kertoimien summa vasemmassa sarakkeessa on tasan b.

Vielä yksi esimerkki: 11 × 18 laskettuna kyseisellä algoritmilla sekä allekkain binäärisenä. Rinnalla on myös sama binäärilukujen kertolasku esitettynä kymmenjärjestelmässä:


                             1 0 0 1 0                 18
     18 | 11              ×  0 1 0 1 1          ×      11
    ----+----            --------------        -----------
     36 | 5                  1 0 0 1 0             1 × 18
     72 | 2                1 0 0 1 0               2 × 18
    144 | 1            1 0 0 1 0                   8 × 18
   -----+----         -----------------    ---------------
    198 |              1 1 0 0 0 1 1 0      11 × 18 = 198

Esiteltyä algoritmia voi käyttää ihan oikeasti kerrottaessa binäärilukuja. Oikein toteutettuna algoritmi kertoo kaksi n-bittistä lukua keskenään ajassa Theta( n ) [2].

Viitteet

[1] Valtteri Suomalainen, Marianna Wallinheimo (toim.): Sauna Syyriassa, Recallmed 1995.
[2] Cormen, T., Leiserson, C., Rivest, R.: Introduction to algorithms, MIT Press, 1990.

Edellinen | Matematiikan valikko | Etusivu | Seuraava

Mikko Pekkarinen, Sivu luotu 1999-03-01, muokattu 2000-11-13. URL: https://iki.fi/empii/matikka/kertolasku.html