Lyhyt MathCheck-ohje (uuteen välilehteen)

Tehtävä:
Suurimman yhteisen tekijän algoritmi

Tässä tehtävässä tarkastellaan kuuluisan Eukleideen algoritmin nykyversiota. Se löytää tehokkaasti kahden luonnollisen luvun suurimman yhteisen tekijän. Luonnolliset luvut ovat `NN = {0, 1, 2, ...}`. Tässä tehtävässä kaikki luvut ovat luonnollisia lukuja, paitsi kun sanotaan toisin.

Algoritmin toiminta tutuksi

Algoritmi käsittelee kahta lukua `n` ja `m` siten, että jokaisella kierroksella `n`:n paikalle tulee `m` ja `m`:n paikalle tulee `n mod m`, kunnes `m=0`. Esimerkki:
`n``m` laskutoimitus
4970 `49 mod 70 = 49`
7049 `70 mod 49 = 21`
4921 `49 mod 21 = 7`
21 7 `21 mod 7 = 0`
7 0lopetus

Sinun vuorosi laskea esimerkki:

`n``m`
6042
tai

Algoritmi voidaan esittää pseudokoodina seuraavasti:

while `m != 0` do
    `k` := `n mod m`; `n` := `m`; `m` := `k`
Mistä muuttujasta vastaus löytyy, kun algoritmi on lopettanut? Valitse oikea vaihtoehto. Voit vaikka kokeilla vaihtoehtoja yksi kerrallaan.
Enkä valitse!
ei mistään
`m`
`n`
`k`
tai

Kuinka monen kierroksen jälkeen algoritmi lopettaa, kun aluksi
`n=60` ja `m=0`?   tai
`n=60` ja `m=13`? tai

Olkoon aluksi `m=6`. Anna mahdollisimman pieni `n` siten, että algoritmi lopettaa tasan `k` kierroksen jälkeen.
`k=1` tai
`k=2` tai
`k=3` tai

Algoritmin nopeus

Tässä osassa johdamme ylä­rajan modernin Eukleideen algoritmin ajan kulutukselle. Tärkein tavoitteemme ei kuitenkaan ole saada ylä­rajaa selville, vaan oppia käsitteitä ja menetelmiä, joita usein käytetään ohjelmista päättelemisessä.

Ensimmäisen kierroksen alussa `n` ja `m` voivat olla mitä tahansa. Mikä seuraavista pätee muitten kierrosten alussa? Oikeita vastauksia on useampia kuin yksi. Vihje: jako­yhtälö.
En vastaa!
`m != 0`
`n != 0`
`m = n`
`m <= n`
`m < n`
tai

Tästä eteenpäin seuraavaan vaaka­viivaan saakka tarkastelemme mitä tahansa kierrosta, jonka alussa `m < n`. Tarkastelemme muunlaiset kierrokset myöhemmin.

Tarkastellaan ensin tapausta `m <= n/2`. Jako­yhtälöstä voidaan päätellä `n mod m <`jotain1, missä ”jotain1” on `n`:n funktio. Kirjoita ”jotain1”. Jos esimerkiksi uskot, että `n mod m < ln n`, kirjoita ln n.
tai

Jäljellä on tapaus, jossa `m <= n/2` ei päde. Silloin `m > n/2` eli `2m > n`. Siksi `n\ text(div)\ m``=``|__n/m__|``<=``n/m``<` eli `n\ text(div)\ m <=` .
tai

Koska oletimme, että `m < n`, pätee `n\ text(div)\ m >=` .
tai

Siis `n\ text(div)\ m` tunnetaan. Siksi `n mod m` voidaan ilmaista `n`:n ja `m`:n funktiona käyttämättä operaattoria `text(mod)`. Tee niin ja sievennä vastauksesi! Vihje: jako­yhtälö.
tai

Kun edellinen vastaus yhdistetään tietoon `m > n/2` saadaan `n mod m <`jotain2, missä ”jotain2” on `n`:n mutta ei `m`:n funktio. Ilmaise ”jotain2” sellaisenaan (siis älä sievennä).
tai

Ilmaise ”jotain2” sievennettynä.
tai
Olemme osoittaneet, että jos `m <= n/2`, niin `n mod m <`jotain1, ja muulloin `n mod m <`jotain2. Nämä yhdistämällä saadaan, että kaikissa tapauksissa
`n mod m <` . tai

Jos jäljellä on ainakin kaksi kierrosta, niin `n`:n arvo kahden kierroksen kuluttua on sama kuin `n`:n ja `m`:n tämän­hetkisillä arvoilla laskettu `n mod m`. Tämän näkee kun katsoo, mihin kierroksen aikana laskettava `n mod m` päätyy kierroksen lopuksi, ja mihin se sieltä kopioituu seuraavalla kierroksella.


Seuraavaksi laskemme algoritmin suorittamien kierrosten määrälle ylä­rajan siinä tapauksessa, että algoritmin alussa `m < n`. Tämä alku­tilannetta koskeva oletus on voimassa seuraavaan vaaka­viivaan saakka.

Edellä nähtiin, että muiden kierrosten kuin ensimmäisen alussa `m < n`. Niinpä `m < n` pätee jokaisen kierroksen alussa. Edellä päätellystä seuraa, että jos kierroksen alussa `n = n'`, niin tasan kahta kierrosta myöhemmin `n <= (n')/2` (ellei algoritmi lopeta sitä ennen).

Jos algoritmi suorittaa `k` kierrosta kun `n` on aluksi `n'`, niin kuinka monta kierrosta se enintään suorittaa, jos aluksi `n <= 2n'`?
tai

Algoritmi lopettaa, kun `m=` .
tai

Jos aluksi `n=1`, niin kuinka monta kierrosta enintään algoritmi suorittaa?
tai

Kirjoita muihin kuin alimpaan luku siten, että kun `n` on aluksi enintään se, niin algoritmi suorittaa enintään ilmoitetun määrän kierroksia. Alimpaan kirjoita lauseke. Päättele vastaus aikaisemmista vastauksista.
0 tai
2 tai
4 tai
6 tai
8 tai
10 tai
20 tai
`2i` tai
Yllä olevan perusteella, kuinka monta kierrosta enintään tarvitaan, kun `n=1000`? Huomaa, että kierrosten määrän on pakko olla kokonais­luku. Itse asiassa yllä oleva päättely voi tuottaa vain parillisia vastauksia.
tai

Tähänastisen perusteella `2i` kierrosta riittää, kun `n > 0` ja `2^(i-1) < n <= 2^i`. (Alaraja tulee siitä, että kun `n = 2^(i-1)`, niin `2(i-1)` kierrosta riittää.) Tavoit­teenamme on kirjoittaa sellainen `n`:n funktio, että niin monta kierrosta riittää kun `n > 0`. Se tapahtuu ratkaisemalla `i` ja kertomalla tulos 2:lla. Siispä ensin ratkaise `i` eli kirjoita sellainen `n`:n funktio `f(n)`, että `i <= f(n)`.
tai

Jäljellä on enää tuloksen kertominen kahdella. Jos sait edellisen ratkaistua, tämän ei pitäisi olla vaikea!
tai

Huomasitko, että edellä vaihdettiin salaa yksi merkki `<`, `<=`, `>=` tai `>` toiseksi? Jopa kahteen kertaan. Jos huomasit jomman kumman tai molemmat, kerro se lasku­harjoitus­tilaisuudessa. Jos osaat, kerro myös, miksi se ei ollut väärin.


Jäljellä on tapaukset, joissa `m < n` ei päde alussa.

Olkoon alussa `m = n`. Jos `n=0`, niin algoritmi suorittaa kierrosta ja muutoin kierrosta.
tai

Jos aluksi `m > n`, niin joko 0 tai 1 kierrosta riittää, tai `n`:n arvo kahden ensimmäisen kierroksen jälkeen on sama kuin alussa ja `m < n` on astunut voimaan. Kerro lasku­harjoitus­tilaisuudessa, miten tämä seuraa aikaisemmin osoitetuista asioista.

Niinpä kaikissa muissa tilanteissa kuin `n=0` pätevän ylä­rajan saamme tekemällä pienen muutoksen sen tapauksen ylä­rajaan, jossa alussa `m < n`.

tai

Jos `n=0`, tarvitaan enintään 1 kierros.

Koska algoritmi tekee kunkin kierroksen aikana vain perus­operaatioita ja vain vakio­määrän, antaa kierrosten määrä oikean kuvan siitä, miten suoritus­aika kasvaa `n`:n funktiona. Kierrosten määrälle johtamamme ylä­raja ei ole liki­mainkaan paras mahdollinen, mutta silti sen mukaan suoritus­aika kasvaa hitaasti `n`:n funktiona. Eukleideen algoritmin moderni versio on siis hyvin nopea.

Algoritmin oikeellisuus

Tässä osassa osoitamme, että algoritmin vastaus on oikea. Nytkään tärkeintä ei ole loppu­tulos vaan päättelyn harjoitteleminen, tai ainakin päättelyn ymmärtämisen harjoitteleminen.

Määritelmän mukaan `k` on `I`:n tekijä jos ja vain jos on olemassa `i` siten, että `I = ki`. Jos `k` on myös `J`:n tekijä, niin on olemassa `j` siten, että `J = kj`. Laskemalla `I+J``=``ki + kj``=``k(i+j)` huomaamme, että `k` on myös luvun `I+J` tekijä.

Osoita samalla tavalla, että jos `k` on sekä `I`:n että `J`:n tekijä, niin `k` on myös luvun `I-J` tekijä. Koska MathCheck sallii enintään kolme muuttujaa kerrallaan, kirjoita kaavasta vain se osa, jossa esiintyvät pelkästään `i`, `j` ja `k`.
tai

Nyt oletetaan, että `k` on `I`:n tekijä. Osoita, että `k` on luvun `I J` tekijä. Kirjoita vain se osuus, jossa ei käytetä `I`:tä. Käytä pakotettuja sulkuja #( ja #).
tai
Luku 3 on sekä 12:n että 6:n tekijä, mutta ei ole luvun `12/6 = 2` tekijä. Oletamme, että `k` on `I`:n ja `J`:n tekijä ja `J != 0`. Mikä seuraavista päättely­askelista ei ole oikein?
  1. Olemme osoittaneet, että jos `k` on `I`:n ja `J`:n tekijä, niin `k` ei ole luvun `I\ text(div)\ J` tekijä.
  2. Sen perusteella mitä äsken osoitimme kerto­laskusta, ja koska `I \ text(div)\ J` on kokonais­luku, `k` on luvun `J(I\ text(div)\ J)` tekijä.
  3. Jakoyhtälöstä seuraa, että `I mod J = I - J(I\ text(div)\ J)`.
  4. Sen perusteella mitä äsken osoitimme vähennys­laskusta, `k` on luvun `I - J(I\ text(div)\ J)` tekijä.
  5. Olemme osoittaneet, että jos `k` on `I`:n ja `J`:n tekijä ja `J != 0`, niin `k` on luvun `I mod J` tekijä.
tai

Olkoon `s` alku­peräisten `n`:n ja `m`:n suurin yhteinen tekijä. Osoitamme kahdessa vaiheessa, että `n`:n lopullinen arvo on `s`.

Tiedämme, että `s` on alku­peräisten `n`:n ja `m`:n tekijä. Koska algoritmi ei tee muuta kuin laskee `n mod m` ja siirtelee lukuja muuttujasta toiseen, `s` on joka hetki myös senhetkisten `n`:n ja `m`:n tekijä. Se on siten myös lopullisen `n`:n tekijä. Siksi lopussa `s <= n`.

Seuraavaksi ajattelemme toisinpäin. Oletamme, että `k` on lopullisen `n`:n tekijä, ja haluamme osoittaa, että `k` on myös alku­peräisten `n`:n ja `m`:n tekijä.

Lopussa `m=0`, ja `k` on sen tekijä, koska `0 = k * 0`. Siis lopussa `k` on sekä `n`:n että `m`:n tekijä.

Alamme seurata algoritmin toimintaa taka­perin. Merkitsemme muuttujien arvoja mieli­valtaisen muun kuin ensimmäisen kierroksen alussa `n`:llä ja `m`:llä, ja yhtä kierrosta aikaisempia arvoja `n'`:lla ja `m'`:lla. Algoritmin mukaan `n = m'`. Niinpä `k` on `m'`:n tekijä. Algoritmin mukaan `m = n' mod m'`. Jako­yhtälön mukaan `n'``=``m'(n'\ text(div)\ m') + n' mod m'``=``n(n' \ text(div)\ n) + m`. Koska `k` on `n`:n ja `m`:n tekijä, on `k` myös tämän luvun tekijä. Olemme osoittaneet, että `k` on sekä `m'`:n että `n'`:n tekijä. Tällä lailla voidaan edetä taka­perin alkuun saakka, joten `k` on alku­peräisten `n`:n ja `m`:n tekijä.

Erityisesti lopullinen `n` on alku­peräisten `n`:n ja `m`:n tekijä, joten se on enintään yhtä suuri kuin niiden suurin yhteinen tekijä. Siksi lopussa `s >= n`.

Koska lopussa `s <= n` ja `s >= n`, on lopullinen `n` sama luku kuin `s`.

Valitse todet väittämät. Vastauksesi hyväksytään vain jos valinnat ovat täysin oikein. Voit halutessasi tilata joukon vihjeitä tai .
Luku ei voi olla itseään pienemmän luonnollisen luvun tekijä. Päättelyn askel `s <= n` perustuu tähän.
Jos algoritmi tekee `k` kierrosta syötteellä `n` ja `m`, niin se tekee `k` kierrosta myös syötteellä `6n` ja `6m`.
Jos algoritmi tekee ainakin yhden kierroksen, niin sekä lopullinen että yhtä kierrosta vaille lopullinen `n` ovat alku­peräisen `n`:n tekijöitä.
Lopputuloksesta voi päätellä alku­peräiset `n` ja `m`.
Jos alussa `n = m = 0`, niin algoritmin tuottama tulos ei ole `n`:n ja `m`:n suurin yhteinen tekijä.
Jos lasketaan yhteen-, vähennys- ja kerto­laskuja luvuilla, joiden viimeinen numero on 0, niin myös loppu­tuloksen viimeinen numero on 0. Kerto­laskuissa riittää, että toisen kerrottavan viimeinen numero on 0. ”`k` on tekijä” -jutussa on kyse samasta asiasta.
tai

Eukleideen versio

Eukleideen versio oli tällainen:
while `m != 0` do
    `k` := maksimi`(n,m)`; `m` := minimi`(n,m)`; `n` := `k-m`
Kuinka monta kierrosta siinä enintään tarvitaan, kun `n=1000` ja `m <= 1000`?
tai

Edellä totesimme, että modernille versiolle riittää 20. Moderni algoritmi on korvannut Eukleideen version, koska …
Minimin ja maksimin laskeminen tietokoneella on hidasta.
Nykyihmiset eivät arvosta antiikin kreikkalaisten saavutuksia.
Moderni algoritmi on paljon nopeampi, jos `n` on iso.
En vastaa tähän!
tai

Toteutus tieto­kone­ohjelmana

Alla on Eukleideen algoritmin modernin version toteutus tieto­kone­ohjelmana. Se toimii hieman toisin kuin edellä kuvattiin. Kumpaakaan lukua ei kopioida sellaisenaan toisen paikalle, vaan silmukan alussa n1 on `n`:n ja n2 `m`:n roolissa ja silmukan lopussa toisin­päin. Tämä toden­näköisesti nopeuttaa ohjelmaa. Luonnollisten lukujen sijaan on käytetty etu­merkittömiä kokonais­lukuja unsigned.

unsigned gcd( unsigned n1, unsigned n2 ){
  while( true ){
    if( !n2 ){ return n1; }
    n1 %= n2;
    if( !n1 ){ return n2; }
    n2 %= n1;
  }
}
Valitse oikea vaihtoehto.
Enkä valitse!
unsigned sisältää kaikki kokonaisluvut nollasta alkaen.
unsigned sisältää kokonais­luvut nollasta alkaen johonkin ylä­rajaan saakka.
unsigned sisältää kaikki kokonaisluvut ykkösestä alkaen.
unsigned sisältää kokonaisluvut ykkösestä alkaen johonkin ylärajaan saakka.
tai
Valitse oikea vaihtoehto.
Enkä valitse!
!n2 tarkoittaa, että n2:een viimeksi sijoitettu arvo syntyi jakamalla nollalla, ja on siksi käyttö­kelvoton.
!n2 tarkoittaa samaa kuin n2 <= 0.
!n2 tarkoittaa samaa kuin n2 == 0.
tai
Missä tapauksessa n1 %= n2 laskee n1`mod`n2 ja sijoittaa tuloksen n1:een? Nyt oletamme että n1 ja n2 ovat mitä tahansa samaa kokonais­luku­tyyppiä, joka ei välttämättä ole unsigned.
Jätän tämän tehtävän väliin.
Aina.
Kun n2 ≠ 0.
Kun n2 > 0.
Kun n1 ≥ 0.
Kun n1 ≥ 0 ja n2 ≠ 0.
tai

Yllä olevan ohjelman toiminnasta on hankala puhua sillä tavalla kuin edellä tehtiin algoritmin nopeutta ja oikeellisuutta tarkasteltaessa, koska muuttujien roolit vaihtuvat toistuvasti. Siksi kirjallisuudessa ei yleensä tarkastella sitä, vaan versiota, jonka esitimme pseudo­koodina. On kuitenkin helppo nähdä, että ohjelma on vain pseudo­koodin tehostettu toteutus, jonka yksi kierros vastaa kahta pseudo­koodin kierrosta. Siksi ohjelma toimii oikein ja nopeasti.

Toivottavasti tästä jää mieleesi, että algoritmeja ei välttämättä kannata toteuttaa juuri sellaisina kuin ne esitetään kirjoissa jne. Kirjassa on voitu valita tapa, joka helpottaa algoritmin selittämistä mutta ei ole muuten paras.