1  x := 1
2  while n > 0 do
3      if n mod 2 = 1 then
4          n := n − 1
5          x := x · a
6      n := n div 2
7      a := a · a
AN = xan

Teh­tä­vä:
Bi­nää­ri­po­tens­si

Ly­hyt Math­Check-oh­je (uu­teen vä­li­leh­teen)

Oh­jel­mien saa­mi­nen toi­mi­maan oi­kein on vai­keaa. Vuon­na 1986 ra­por­toi­dus­sa koe­ti­lan­tees­sa vain 10 % am­mat­ti­mai­sis­ta oh­jel­moi­jis­ta sai yk­sin­ker­tai­sen pe­rus­al­go­rit­min koo­dat­tua oi­kein, vaik­ka yli­vuo­to­ja ei kat­sot­tu vir­heik­si. Ha­vain­to on he­rät­tä­nyt pal­jon kes­kus­te­lua ja jat­ko­ha­vain­to­ja. Nii­hin tu­tus­tu­mi­sen voit ha­lu­tes­sa­si aloit­taa täs­tä.

Sik­si on ke­hi­tet­ty eri­tyi­nen ajat­te­lu­ta­pa, jol­la oh­jel­mat saa toi­mi­maan oi­kein. Tä­mä teh­tä­vä on tar­koi­tet­tu en­sim­mäi­sek­si tu­tus­tu­mi­sek­si sii­hen.

Tur­val­li­nen asioin­ti verk­ko­pan­kis­sa edel­lyt­tää tie­don sa­laus­ta. Yk­si las­ku­toi­mi­tus, jo­ta ny­ky­ai­kai­sis­sa sa­laus­me­ne­tel­mis­sä tar­vi­taan, on an mod M, mis­sä kaik­ki kol­me lu­kua ovat iso­ja (esi­mer­kik­si 300-nu­me­roi­sia) ja mod tar­koit­taa ja­ko­jään­nös­tä. Sen suo­rit­ta­mi­nen las­ke­mal­la n − 1 eli noin 10300 ker­to­las­kua ja ja­ko­jään­nös­tä vei­si ai­kaa mel­ko mon­ta maail­man­kaik­keu­den ikää.

Yl­lä mai­nit­tua ajat­te­lu­ta­paa so­vel­le­taan täs­sä teh­tä­väs­sä al­go­rit­miin, jo­ka suo­rit­taa las­kun tar­peek­si no­peas­ti. Yk­sin­ker­tai­suu­den vuok­si ja­ko­jään­nök­sen las­ke­mi­nen jä­te­tään näyt­tä­mät­tä, mut­ta se on help­po li­sä­tä al­go­rit­min jo­ka kier­rok­sel­le.

Al­go­rit­mi ja to­dis­tus­me­ne­tel­mä

Ker­ra­taan aluk­si pa­ri asiaa.

Kun jae­taan kol­me lit­raa eli 30 de­si­lit­raa lim­saa ta­san kah­dek­sal­le ih­mi­sel­le, jo­kai­nen saa 3,75 de­si­lit­raa. Täs­sä käy­tet­tiin reaa­li­lu­ku­jen ja­ko­las­kua. Kun jae­taan 30 il­ma­pal­loa kah­dek­sal­le ih­mi­sel­le niin ta­san kuin mah­dol­lis­ta, niin jo­kai­nen saa kol­me ja kuu­si il­ma­pal­loa jää yli. Nyt käy­tet­tiin ko­ko­nais­lu­ku­jen ja­ko­las­kua. Jo­kai­sen saa­ma mää­rä on osa­mää­rä ja yli­jää­nei­den mää­rä on ja­ko­jään­nös.

Mo­nis­sa oh­jel­moin­ti­kie­lis­sä n / m tar­koit­taa jo­ko li­ki­mää­räis­tä reaa­li­lu­ku­jen ja­ko­las­kua tai ko­ko­nais­lu­ku­jen osa­mää­rää riip­puen sii­tä, mi­tä tyyp­piä n ja m ovat. Mo­nis­sa oh­jel­moin­ti­kie­lis­sä ja­ko­jään­nös­tä mer­ki­tään n % m. (Va­roi­tus: ne­ga­tii­vi­sil­la ko­ko­nais­lu­vuil­la nä­mä ei­vät vält­tä­mät­tä pä­de.) Täs­sä teh­tä­väs­sä n / m tar­koit­taa tark­kaa reaa­li­lu­ku­jen ja­ko­las­kua. Mer­kit­sem­me ko­ko­nais­lu­ku­jen osa­mää­rää n div m ja ja­ko­jään­nös­tä n mod m.

Ko­ko­nais­lu­ku n on pa­ri­ton, jos ja vain jos mod = . Päin­vas­tai­ses­sa ta­pauk­ses­sa n on pa­ril­li­nen.
tai

Jos n on pa­ril­li­nen, niin n div 2 = , ja jos n on pa­ri­ton, niin n div 2 = (il­mai­se vas­tauk­set il­man sym­bo­lei­ta div ja mod). Vih­je 1Käy­tä /. Vih­je 2Li­sää tai vä­hen­nä en­nen ja­ko­las­kua sel­lai­nen lu­ku, et­tä ja­ko tu­lee me­ne­mään ta­san mut­ta alas­päin pyö­ris­tet­ty tu­los ei muu­tu.
tai

Bi­nää­ri­po­tens­si näyt­tää täl­tä. Se on ko­pioi­tu oi­keal­le alas, jot­ta se oli­si kä­sil­lä myös kun al­la ole­va ko­pio on ka­don­nut ruu­dun ylä­reu­nan ylä­puo­lel­le.

1  x := 1
2  while n > 0 do
3      if n mod 2 = 1 then
4          n := n − 1
5          x := x · a
6      n := n div 2
7      a := a · a

Har­maal­la kir­joi­tet­tua ri­viä 4 ei oi­keas­ti tar­vi­ta, mut­ta sen li­sää­mi­nen hel­pot­taa al­go­rit­mis­ta päät­te­le­mis­tä. Sen li­sää­mi­nen ei muu­ta si­tä ar­voa, mi­kä ri­vil­lä 6 si­joi­te­taan n:ään, kos­ka ri­vin 3 eh­don vuok­si se suo­ri­te­taan vain kun n on pa­ri­ton, ja sil­loin n div 2 = (n − 1) / 2 = (n − 1) div 2. (Mik­si vih­jeen yh­tä­suu­ruu­det pä­te­vät? en­sim­mäi­nenn div 2 = (n − 1) / 2: tä­män näim­me edel­lä. toi­nen(n − 1) / 2 = (n − 1) div 2: ja­ko me­nee ta­san, jo­ten / tuot­taa sa­man tu­lok­sen kuin div.) Mi­tään muu­ta­kaan vai­ku­tus­ta sen li­sää­mi­sel­lä ei ole jat­koon, kos­ka ri­vien 4 ja 6 vä­lis­sä n:n ar­voa ei käy­te­tä mi­hin­kään.

Oh­jel­moin­ti­tai­don osal­ta täs­sä teh­tä­väs­sä riit­tää ky­ky teh­dä pää­tel­miä yh­den tai muu­ta­man ri­vin vai­ku­tuk­ses­ta, ku­ten teh­tiin juu­ri äs­ken. Ei tar­vit­se tie­tää, mi­ten bi­nää­ri­po­tens­si toi­mii ko­ko­nai­suu­te­na. Saat­taa ol­la jo­pa eduk­si jos ei tie­dä, kos­ka se hel­pot­taa ajat­te­lun kes­kit­tä­mis­tä to­dis­tus­me­ne­tel­mään ja kul­loin­kin to­dis­tet­ta­vaan pik­ku­asiaan, sen si­jaan et­tä vas­tauk­sia et­sit­täi­siin bi­nää­ri­po­tens­sin toi­min­taa kos­ke­vas­ta in­tui­tios­ta. Ku­ten alus­sa to­det­tiin, in­tui­tiom­me ei ole luo­tet­ta­va.

Mer­ki­tään muut­tu­jien a ja n ar­vo­ja al­go­rit­min alus­sa sym­bo­leil­la A ja N. Min­kä seu­raa­vis­ta ar­vot ei­vät muu­tu al­go­rit­min suo­ri­tuk­sen ai­ka­na?
A a N n x
tai

Al­go­rit­min teh­tä­vä­nä on siis las­kea AN, mis­sä N on luon­nol­li­nen lu­ku. To­dis­tam­me, et­tä al­go­rit­mi las­kee oi­kean lop­pu­tu­lok­sen. Lo­puk­si sel­vi­täm­me, suun­nil­leen kuin­ka no­peas­ti se toi­mii.

Käy­täm­me sil­mu­koi­den to­dis­ta­mi­ses­sa hy­vin yleis­tä päät­te­ly­ta­paa, jos­sa on vii­si vai­het­ta:

  1. Va­li­taan jo­kin väi­te, jol­la päät­te­ly saa­daan on­nis­tu­maan. Si­tä kut­su­taan in­va­rian­tik­si. In­va­rian­tin va­lit­se­mi­nen vaa­tii, et­tä ym­mär­re­tään, mi­ten al­go­rit­mi toi­mii ko­ko­nai­suu­te­na. Täs­sä teh­tä­väs­sä in­va­riant­ti on kui­ten­kin an­net­tu val­mii­na: bi­nää­ri­po­tens­sin in­va­riant­ti on yh­tä­lö AN = xan.
  2. Osoi­te­taan, et­tä in­va­riant­ti pä­tee sil­mu­kan alus­sa eli kun ri­vil­le 2 tul­laan en­sim­mäi­sen ker­ran.
  3. Osoi­te­taan, et­tä jos sil­mu­kan eh­to pä­tee, niin sil­mu­kan var­ta­lon suo­ri­tus ei voi saa­da in­va­riant­tia pois voi­mas­ta (pait­si ken­ties ti­la­päi­ses­ti kes­ken var­ta­lon suo­ri­tuk­sen). Siis osoi­te­taan, et­tä jos AN = xan pä­tee ri­vin 3 alus­sa ja n > 0, niin AN = xan pä­tee ri­vin 7 lo­pus­sa. Täs­tä, edel­li­ses­tä ja sii­tä, et­tä ri­vil­lä 2 ei muu­te­ta min­kään muut­tu­jan ar­voa seu­raa, et­tä AN = xan on voi­mas­sa ai­na ri­vin 2 alus­sa.
  4. Osoi­te­taan, et­tä sil­mu­kan suo­ri­tus lop­puu jos­kus.
  5. Osoi­te­taan, et­tä jos in­va­riant­ti pä­tee ja sil­mu­kan eh­to ei pä­de, niin sil­mu­kan lop­pu­tu­lok­sel­ta ha­lut­tu asia pä­tee, eli et­tä al­go­rit­mi on las­ke­nut oi­kean lop­pu­tu­lok­sen.

Kos­ka po­tens­si­las­ku ei ole mää­ri­tel­ty esi­mer­kik­si sil­loin kun kan­ta­lu­ku on nol­la ja eks­po­nent­ti ne­ga­tii­vi­nen, mei­dän on pi­det­tä­vä tark­kaan huol­ta, et­tä väit­teis­säm­me eks­po­nen­tit ovat ai­na ei-ne­ga­tii­vi­sia.

In­va­riant­ti sil­muk­kaan tul­taes­sa

Me­ne­tel­män vai­he 2 on täl­lä ker­taa mel­ko help­po. Kun ri­vil­le 2 tul­laan en­sim­mäi­sen ker­ran x = vih­jeMi­tä x:lle ta­pah­tuu ri­vil­lä 1?, a = vih­jeMi­kä ni­mi an­net­tiin a:n ar­vol­le al­go­rit­min alus­sa? Mi­ten a:n ar­vo on sen jäl­keen muut­tu­nut? ja n = , jo­ten xan = . Il­mai­se vas­tauk­set sym­bo­lien A ja N avul­la.
tai

In­va­rian­tin säi­ly­mi­nen sil­mu­kas­sa

Vai­heen 3 hoi­ta­mi­sek­si ole­tam­me, et­tä in­va­riant­ti ja sil­mu­kan eh­to pä­te­vät ri­vin 3 alus­sa, ja to­dis­tam­me, et­tä in­va­riant­ti pä­tee ri­vin 7 lo­pus­sa. Tä­män teh­däk­sem­me alam­me käy­dä sil­muk­kaa lä­pi.

Ri­vin 3 alus­sa tie­de­tään var­mas­ti, et­tä n, kos­ka n on ko­ko­nais­lu­ku ja sil­mu­kan eh­to lu­paa n > 0. Tä­män tie­don an­sios­ta ri­vin 4 lo­pus­sa (jos sin­ne jou­du­taan) n.
tai

Kos­ka n muut­tuu ri­vil­lä 4, ri­vin 5 alus­sa in­va­riant­ti ei pä­de sel­lai­se­naan, vaan muu­te­tus­sa muo­dos­sa vih­jeRi­vin 5 alus­sa in­va­riant­ti pä­tee yhä n:n van­hal­le ar­vol­le, eli ar­vol­le juu­ri en­nen si­joi­tus­ta n := n − 1. Il­mai­se n:n van­ha ar­vo n:n ny­kyi­sen ar­von avul­la.:
AN = .
tai

Vas­ta­tes­sa­si edel­li­seen koh­taan huo­ma­sit eh­kä, et­tä tä­män muo­don voi pää­tel­lä suo­raan, mut­ta voi ol­la vai­keaa miet­tiä pi­tää­kö si­joi­tuk­sen n := n − 1 vai­ku­tus ot­taa huo­mioon li­sää­mäl­lä vai vä­hen­tä­mäl­lä in­va­rian­tis­sa n:ään yk­kö­nen. Jos si­joi­tus­lau­seen oi­keal­la puo­lel­la on jo­tain mo­ni­mut­kai­sem­paa, vai­keus kas­vaa. Sik­si jä­täm­me bi­nää­ri­po­tens­sin het­kek­si, ja opet­te­lem­me ki­kan, jol­la voi­daan rat­kais­ta seu­raa­va on­gel­ma:

Oh­jel­mas­sa on si­joi­tus­lau­se ja tun­ne­taan kaa­va, jo­ka pä­tee juu­ri en­nen si­joi­tus­lau­set­ta. Joh­da mah­dol­li­sim­man vah­va kaa­va, jo­ka pä­tee he­ti si­joi­tus­lau­seen jäl­keen.

En­nen si­joi­tus­lau­set­ta voi­mas­sa ole­va kaa­va kan­nat­taa muut­taa muo­toon, jos­sa si­joi­tus­lau­seen oi­kea puo­li esiin­tyy sel­lai­se­naan. Tyy­pil­li­ses­ti se esiin­tyy yh­den ker­ran, mut­ta muut­kin mää­rät ovat mah­dol­li­sia. Si­joi­tuk­sen koh­tee­na ole­va muut­tu­ja ei saa esiin­tyä muual­la kuin näis­sä oi­keis­sa puo­lis­sa. Si­joi­tus­lau­seen jäl­kei­nen ti­lan­ne saa­daan kor­vaa­mal­la ne muut­tu­jal­la, jo­hon si­joi­te­taan.

Esi­mer­kik­si si­joi­tus­lau­seen n := 2n + 1 ja kaa­van 4n = k ta­pauk­ses­sa se tar­koit­taa, et­tä en­sin kaa­va muu­te­taan muo­toon 2(2n + 1) − 2 = k. Tä­mä on loo­gi­ses­ti yh­tä­pi­tä­vä al­ku­pe­räi­sen kaa­van kans­sa, kos­ka 2(2n + 1) − 2 = 4n. Sit­ten 2n + 1 kor­va­taan n:llä, jol­loin saa­daan 2n − 2 = k. Tu­lok­sek­si saa­tiin, et­tä jos en­nen si­joi­tus­ta n := 2n + 1 pä­ti 4n = k, niin si­joi­tuk­sen jäl­keen pä­tee 2n − 2 = k.

Har­joit­te­lem­me tä­tä kik­kaa! En­nen si­joi­tus­lau­set­ta i := i + 1 pä­ti 3b + 2i ≥ 0. Sie­ven­nä se muo­toon, jos­sa i esiin­tyy vain osa­lau­sek­keis­sa muo­toa i + 1.

Kir­joi­ta vas­taa­va eh­to, jo­ka pä­tee si­joi­tus­lau­seen jäl­keen.
tai

Täs­sä laa­ti­kos­sa voit ha­lu­tes­sa­si muo­ka­ta väit­tä­mää 3b + 2i ≥ 0 yh­tä­pi­tä­vään muo­toon seu­raa­van koh­dan rat­kai­se­mi­sen vä­li­vai­hee­na.

tai

En­nen si­joi­tus­lau­set­ta i := 1 − i pä­ti 3b + 2i ≥ 0. Kir­joi­ta vas­taa­va eh­to, jo­ka pä­tee si­joi­tus­lau­seen jäl­keen.
tai

Pa­lat­kaam­me bi­nää­ri­po­tens­siin. Ri­vin 4 ta­pauk­ses­sa kik­ka tar­koit­taa, et­tä AN = xan muu­te­taan muo­toon, jos­sa n esiin­tyy vain osa­lau­sek­keis­sa muo­toa n − 1. Töi­hin! Olen li­sän­nyt ko­vat su­lut osa­lau­sek­keen n − 1 ym­pä­ril­le ha­vain­nol­li­suu­den vuok­si, mut­ta oi­keas­ti se ei ole tar­peen jos kaa­van si­säl­tö säi­lyy eh­jä­nä il­man­kin.
AN = .
Kun osa­lau­sek­keen n − 1 pai­kal­le lai­te­taan si­joi­tuk­sen koh­tee­na ole­va muut­tu­ja n, saa­daan se min­kä toi­vot­ta­vas­ti sait edel­lä:
AN = .
tai

Ri­vin 5 kä­sit­te­lyä var­ten muu­tam­me tä­män muo­toon, jos­sa x · a on te­ki­jä­nä ja x ei esiin­ny muu­ten:
AN = .
Ri­vin 5 mu­kai­ses­ti x · a kor­va­taan x:llä, jo­ten ri­vin 5 lo­pus­sa AN = .
tai

Seu­raa­vak­si tar­kas­te­lem­me ti­lan­net­ta ri­vin 6 alus­sa. Vaik­ka ri­vin 4 mu­ka­na- tai pois­sa­olo ei muu­ta al­go­rit­min tu­los­ta, al­la ole­viin väit­tei­siin se vai­kut­taa. Ole­tam­me, et­tä ri­vi 4 on mu­ka­na. Näim­me, et­tä jos men­tiin then-haa­ran kaut­ta, niin in­va­riant­ti oli vä­lil­lä pois voi­mas­ta mut­ta as­tui uu­del­leen voi­maan then-haa­ran lo­pus­sa. Jos then-haa­ra ohi­tet­tiin, niin min­kään muut­tu­jan ar­vo ei muut­tu­nut, jo­ten in­va­riant­ti pä­tee kos­ka se pä­ti ri­vin 3 alus­sa. Siis jo­ka ta­pauk­ses­sa in­va­riant­ti pä­tee ri­vin 6 alus­sa.

Muut­tu­jan n ar­vos­ta ri­vin 6 alus­sa tie­de­tään seu­raa­vaa (va­lit­se oi­keat):
n > 0
n ≥ 0
n ≥ −1
tai

Jos men­tiin then-haa­ran kaut­ta, niin n on pa­ri­ton.
Jos men­tiin then-haa­ran kaut­ta, niin n on pa­ril­li­nen.
Jos ei men­ty then-haa­ran kaut­ta, niin n on pa­ri­ton.
Jos ei men­ty then-haa­ran kaut­ta, niin n on pa­ril­li­nen.
n on pa­ri­ton.
n on pa­ril­li­nen.
tai

Ri­vin 6 kä­sit­te­le­mi­sek­si muun­nam­me ri­vin 6 alun ti­lan­teen sel­lai­sek­si, et­tä n esiin­tyy sii­nä vain muo­dos­sa n div 2. Näim­me edel­lä, et­tä in­va­riant­ti pä­tee ri­vin 6 alus­sa. Kos­ka n on pa­ril­li­nen, voim­me so­vel­taa si­tä et­tä n div 2 = n / 2, jo­ten n = 2(n div 2).
AN =
tai

Edel­lä ole­van pe­rus­teel­la ti­lan­ne on seu­raa­va ri­vin 7 alus­sa:
AN = = So­vel­la so­pi­vaa po­tens­si­las­kun la­kia. Nii­tä löy­dät vaik­ka teh­tä­väs­tä Po­tens­si­las­ku..
tai

Tie­ten­kin a2 = a · a. Niin­pä ri­vin 7 lo­pus­sa AN = , ku­ten pi­tää­kin.
tai

Olem­me to­dis­ta­neet, et­tä jos sil­mu­kan var­ta­loon tul­laan ja in­va­riant­ti on voi­mas­sa sen alus­sa, niin se on voi­mas­sa myös sil­mu­kan var­ta­lon lo­pus­sa. Siis vai­he 3 on val­mis.

Al­go­rit­min py­säh­ty­mi­nen

Vai­hees­sa 4 pi­tää to­dis­taa, et­tä al­go­rit­mi lo­pet­taa jos­kus. Täs­sä ei täl­lä ker­taa ole muu­ta vai­keaa kuin et­tä huo­li­mat­to­muus­vir­hei­tä voi sat­tua se­kä oh­jel­moi­jil­le et­tä oh­jel­mis­ta miet­ti­jöil­le. Ote­taan sik­si toi­sen­lai­nen ai­het­ta si­vua­va ky­sy­mys. Py­säh­tyi­si­kö tä­mä al­go­rit­mi, jos sil­muk­ka­eh­to­na oli­si­kin n ≥ 0?
kyl­lä
ei
ky­sy­mys on huo­nos­ti mää­ri­tel­ty
tai

Sil­muk­ka­eh­to­na on kui­ten­kin n > 0, jo­ten al­go­rit­mi py­säh­tyy, kos­ka kun n > 0 pä­tee n div 2 ≤ n / 2 < n, jo­ten n pie­ne­nee sil­mu­kan jo­kai­sel­la kier­rok­sel­la kun­nes se on 0.

Lop­pu­ti­lan­ne

Kun al­go­rit­mi on lo­pet­ta­nut, sil­mu­kan eh­dos­ta ja sii­tä, et­tä n on luon­nol­li­nen lu­ku, voi­daan pää­tel­lä, et­tä n = , jo­ten xan = (il­mai­se pien­ten kir­jain­ten avul­la). Toi­saal­ta in­va­rian­tin vuok­si xan = (il­mai­se suur­ten kir­jain­ten avul­la).
tai

Kos­ka kum­pi­kin kah­teen edel­li­seen laa­tik­koon kir­joit­ta­mis­ta­si lau­sek­keis­ta on yh­tä­suu­ri lau­sek­keen xan kans­sa, ne ovat yh­tä­suu­ret myös kes­ke­nään, jo­ten al­go­rit­min tuot­ta­ma vas­taus on oi­kein. Vai­he 5 ja si­tä myö­ten ko­ko to­dis­tus on val­mis.

Al­go­rit­min no­peus

Tä­mä al­go­rit­mi mo­ti­voi­tiin lu­pauk­sel­la no­peu­des­ta, jo­ten nyt on ai­ka kat­soa kuin­ka no­pea se on. Al­go­rit­min käyt­tä­mis­sä pe­rus­ope­raa­tiois­sa ei ole mi­tään ker­to­las­kua mo­ni­mut­kai­sem­paa. Kol­me­sa­taa­nu­me­rois­ten lu­ku­jen ker­to­las­ku ei ole yh­tä pie­ni hom­ma kuin kym­men­nu­me­rois­ten, jo­ten tar­kas­sa las­kel­mas­sa kiin­ni­tet­täi­siin huo­mio­ta pe­rus­ope­raa­tioi­den hin­taan. Nyt em­me kui­ten­kaan ole niin tark­ko­ja, vaan kat­som­me ai­noas­taan sil­mu­kan kier­ros­ten mää­rää.

Kuin­ka mon­ta kier­ros­ta al­go­rit­mi suo­rit­taa? Jot­ta si­nun ei tar­vit­si­si miet­tiä ja kir­joit­taa hie­man han­ka­laa tark­kaa lau­se­ket­ta, Math­Check tar­kas­taa vain po­si­tii­vi­sil­la n:n ar­voil­la ja hy­väk­syy kai­ken mi­kä poik­keaa vä­hem­män kuin 1 tar­kas­ta ar­vos­ta.
tai

Ai ha­luat yrit­tää tark­kaa­kin lau­se­ket­ta? Tot­ta kai se so­pii, jos in­toa riit­tää!
tai

Ai ha­luat vain näh­dä tar­kan lau­sek­keen ja sen se­li­tyk­sen? Se­kin so­pii. Saat sa­maan hin­taan kak­si vaih­to­eh­tois­ta lau­se­ket­ta.
tai

Kol­me­sa­taa­nu­me­roi­sil­la lu­vuil­la tu­lee siis hiu­kan al­le tu­hat kier­ros­ta. Tie­to­ko­neel­le se on koh­tuul­li­nen työ­mää­rä sii­tä­kin huo­li­mat­ta, et­tä pe­rus­las­ku­toi­mi­tuk­set teh­dään 300-nu­me­roi­sil­la lu­vuil­la.