1   while `m != 0` do
2       `k` := `n mod m`
3       `n` := `m`
4       `m` := `k`
`I = J(I \ \text(div) \ J) + I mod J`
`0 <= I mod J < |J|`

Teh­tä­vä:
SYT-al­go­rit­min no­peus

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

Täs­sä teh­tä­väs­sä joh­dam­me ylä­ra­jan mo­der­nin Euk­lei­deen al­go­rit­min ajan ku­lu­tuk­sel­le. Tär­kein ta­voit­teem­me ei kui­ten­kaan ole saa­da ylä­ra­jaa sel­vil­le, vaan har­joi­tel­la oh­jel­mis­ta päät­te­le­mis­tä.

Voit käyt­tää vas­tauk­sis­sa­si ope­raat­to­rei­ta div ja mod se­kä kak­si­kan­tais­ta lo­ga­rit­mia log2. Math­Check tun­tee ne ny­kyi­sin.

SYT-al­go­rit­mi

Ker­taam­me aluk­si hie­man SYT-al­go­rit­miin liit­ty­viä asioi­ta. Jol­lei­vät ker­taa­mis­teh­tä­vät rat­kea tai jos ja­ko­yh­tä­lön käyt­tö ei tun­nu tu­tul­ta, kan­nat­taa en­sin suo­rit­taa teh­tä­vää Suu­rim­man yh­tei­sen te­ki­jän al­go­rit­mi koh­dan ”Apu­tu­lok­sia” lop­puun saak­ka.

Ole­tam­me, et­tä `n` ja `m` ovat luon­nol­li­sia lu­ku­ja. SYT-al­go­rit­mi voi­daan esit­tää pseu­do­koo­di­na seu­raa­vas­ti:

1   while `m != 0` do
2       `k` := `n mod m`
3       `n` := `m`
4       `m` := `k`

Täs­sä on esi­merk­ki SYT-al­go­rit­min käyt­täy­ty­mi­ses­tä:

`n``m` las­ku­toi­mi­tus
4970 `49 mod 70 = 49`
7049 `70 mod 49 = 21`
4921 `49 mod 21 = 7`
21 7 `21 mod 7 = 0`
7 0lo­pe­tus

Mis­sä muut­tu­jas­sa vas­taus on? tai

Jos aluk­si `n=m=0`, niin kuin­ka mon­ta kier­ros­ta SYT-al­go­rit­mi suo­rit­taa? Mi­tä se an­taa vas­tauk­sek­si? On­ko se oi­kein? opet­ta­jan kan­taNol­la on nol­lan ja nol­lan yh­tei­nen te­ki­jä, mut­ta ei suu­rin, kos­ka myös esim. 1 on nii­den yh­tei­nen te­ki­jä. Nol­lal­la ja nol­lal­la ei ole suu­rin­ta yh­teis­tä te­ki­jää. SYT-al­go­rit­min pi­täi­si siis vas­ta­ta ”suu­rin­ta yh­teis­tä te­ki­jää ei ole”, ”vir­heel­li­nen syö­te” tms. Toi­saal­ta voi­daan aja­tel­la, et­tä 0 on koo­di vas­tauk­sel­le ”suu­rin­ta yh­teis­tä te­ki­jää ei ole”. Nol­la on va­paa käy­tet­tä­väk­si näin, kos­ka se ei se­koi­tu mui­hin vas­tauk­siin, kos­ka 0 ei ole min­kään kah­den ko­ko­nais­lu­vun suu­rin yh­tei­nen te­ki­jä.
tai

Jot­ta SYT-al­go­rit­min toi­min­nas­ta oli­si kä­te­väm­pi pu­hua, mer­kit­sem­me `m`:n ja `n`:n ar­vo­ja ri­vin 4 lo­pus­sa isoil­la kir­jai­mil­la `M` ja `N`. Täst­edes, jol­lei toi­sin sa­no­ta, pie­net kir­jai­met `m` ja `n` tar­koit­ta­vat ar­vo­ja ri­vin 1 alus­sa. SYT-al­go­rit­min koo­dis­ta seu­raa, et­tä (il­mai­se vas­tauk­set `n`:n ja/tai `m`:n funk­tioi­na)
`N =` ja `M =` tai

Ri­vien 2 ja 3 alus­sa `n`:llä ja `m`:llä on sa­mat ar­vot kuin ri­vin 1 alus­sa.

Jos kier­rok­sen alus­sa `n < m`

Esi­merk­kim­me alus­sa pä­ti `n < m`. En­sim­mäi­sel­lä kier­rok­sel­la SYT-al­go­rit­mi vaih­toi `n`:n ja `m`:n kes­ke­nään. Ta­pah­tuu­ko­han näin ai­na kun `n < m` vai ai­noas­taan toi­si­naan? Jos `n < m`, niin `n mod m =`, jo­ten `N =` ja `M =`. tai

Siis sil­mu­kan kier­ros to­del­la­kin vaih­taa `n`:n ja `m`:n kes­ke­nään, jos sen alus­sa `n < m`.

Jos kier­rok­sen alus­sa `n = m`

Jos kier­rok­sen alus­sa `n=m`, niin mi­tä SYT-al­go­rit­mi te­kee? Vas­tausJos `n=m=0`, niin se lo­pet­taa sa­man­tien. Jos `n=m!=0`, niin se te­kee yh­den kier­rok­sen ja lo­pet­taa. Kum­mas­sa­kin ta­pauks­sa `n`:n ar­vo jää en­nal­leen.

Jos kier­rok­sen alus­sa `n > m`

Esi­mer­kis­sä pä­ti en­sim­mäi­sen kier­rok­sen jäl­keen lop­puun saak­ka `n > m`. Ta­pah­tuu­ko­han näin ai­na vai ai­noas­taan toi­si­naan? Ai­na. Nyt osoi­tam­me, et­tä jos ri­vin 2 alus­sa `n > m`, niin sa­ma pä­tee ri­vin 4 lo­pus­sa. Täy­tyy siis osoit­taa isoin kir­jai­min il­mais­tu­na . Pie­nin kir­jai­min il­mais­tu­na se on `>` . Se on tot­ta, kos­ka …ja­ko­yh­tä­lön mu­kaan `n mod m < |m|`, ja `|m|=m` kos­ka olem­me ra­joit­tau­tu­neet luon­nol­li­siin lu­kui­hin.
tai

Esi­mer­kis­säm­me sen jäl­keen kun `n` ja `m` oli saa­tu jär­jes­tyk­seen `n > m`, ne pie­ne­ni­vät no­peas­ti. Tä­mä­kään ei ole sat­tu­maa. To­dis­tam­me seu­raa­vak­si, et­tä jos jon­kin kier­rok­sen alus­sa `n > m`, niin kah­ta kier­ros­ta myö­hem­min `n` on pie­nen­ty­nyt al­le puo­leen (olet­taen tie­ten­kin, et­tä kier­rok­sia on jäl­jel­lä ai­na­kin kak­si). Tä­mä saa­daan to­dis­ta­mal­la `M < n/2`, kos­ka `n`:n ar­vo kah­den kier­rok­sen jäl­keen on sa­ma kuin `m`:n ar­vo yh­den kier­rok­sen jäl­keen eli `M`. Jaam­me tar­kas­te­lun kah­teen osaan.

Olem­me osoit­ta­neet, et­tä jos `m <= n/2` pä­tee, niin ta­voit­te­le­mam­me asia pä­tee, ja jos `m <= n/2` ei pä­de, niin ta­voit­te­le­mam­me asia pä­tee. Niin­pä ta­voit­te­le­mam­me asia pä­tee kai­kis­sa ta­pauk­sis­sa, jois­sa kier­rok­sen alus­sa `n > m`. (Olem­me yhä ot­si­kon ”Jos kier­rok­sen alus­sa `n > m`” pii­ris­sä.)

Ylä­ra­jan kä­si­te

SYT-al­go­rit­min kier­ros­ten mää­rä pomp­pii ylös ja alas `n`:n ja `m`:n kas­vaes­sa. Jos `n=21`, niin kier­rok­sia on seu­raa­vas­ti `m`:n funk­tio­na:
`m`kier­rok­sia
12
13
14
tai

Em­me ole kiin­nos­tu­neet tä­män pomp­pi­mi­sen yk­si­tyis­koh­dis­ta. Em­me myös­kään ole kiin­nos­tu­neet sel­lai­sis­ta ta­pauk­sis­ta kuin `n=2000` ja `m=1000`, jois­sa kier­rok­sia tu­lee poik­keuk­sel­li­sen vä­hän. Ha­luam­me hel­pos­ti ym­mär­ret­tä­vän lau­sek­keen, jos­ta saa käyt­tö­kel­poi­sen ylä­ra­jan kier­ros­ten mää­räl­le, kun `n` ja `m` tun­ne­taan.

Sa­na ”ylä­ra­ja” tar­koit­taa, et­tä to­del­li­nen lu­kuar­vo on enin­tään se, mut­ta voi ol­la vä­hem­män­kin. Hy­vin pal­jon to­del­lis­ta lu­kuar­voa suu­rem­pi ylä­ra­ja on yleen­sä help­po to­dis­taa pä­te­väk­si, mut­ta sa­mas­ta syys­tä se ei an­na hyö­dyl­lis­tä in­for­maa­tio­ta.

Luen­noi­ja on `x` vuot­ta van­ha. Mit­kä seu­raa­vis­ta ovat pä­te­viä ylä­ra­jo­ja lu­vul­le `x`? Ko­kei­le yk­si ker­ral­laan.
1000
100
70
60
50
10
tai

Teh­tä­väs­sä Suu­rim­man yh­tei­sen te­ki­jän al­go­rit­mi osoi­tet­tiin, et­tä `m` pie­ne­nee jo­kai­sel­la kier­rok­sel­la. Kos­ka oh­jel­ma lo­pet­taa kun `m=0`, täs­tä seu­raa, et­tä kier­rok­sia on kor­kein­taan yh­tä pal­jon kuin `m`:n ar­vo on alus­sa. Siis `m` on pä­te­vä ylä­ra­ja kier­ros­ten mää­räl­le. Se on kui­ten­kin isoil­la `m` niin pal­jon to­del­lis­ta kier­ros­ten mää­rää suu­rem­pi, et­tä se ei ole ko­vin hyö­dyl­li­nen ylä­ra­ja. Esi­mer­kik­si jos `m=1000000` se an­taa ylä­ra­jak­si 1 000 000, vaik­ka tark­ka ar­vo on vain 25.

Joh­dam­me ylä­ra­jan, jo­ka on isoil­la `n` ja `m` noin 44% suu­rem­pi kuin pa­ras mah­dol­li­nen sel­lai­nen ylä­ra­ja, jo­ka ei pouk­koi­le ylös alas. Näin tark­ka ylä­ra­ja an­taa hy­vän ku­van SYT-al­go­rit­min suo­ri­tu­sa­jas­ta huo­noim­mas­sa ta­pauk­ses­sa eli sel­lai­sil­la `n` ja `m`, jot­ka osu­vat ylös alas pouk­koi­lun ylä­koh­tiin. Tä­tä tar­kem­man ylä­ra­jan joh­ta­mi­nen ei toi­si pal­joa li­säar­voa, mut­ta vaa­ti­si pal­jon enem­män ma­te­ma­tiik­kaa.

Va­lit­se oi­keat vaih­toeh­dot.
Kun `n` ja `m` kas­va­vat, niin myös tark­ka kier­ros­ten mää­rä ai­na kas­vaa.
Kun `n` ja `m` kas­va­vat, niin tark­ka kier­ros­ten mää­rä ai­na py­syy en­nal­laan tai pie­nen­tyy.
Tark­ka kier­ros­ten mää­rä on ai­na enin­tään sen ver­ran kuin ylä­ra­ja sa­noo.
Tark­ka kier­ros­ten mää­rä on ai­na vä­hem­män kuin ylä­ra­ja sa­noo.
Ylä­ra­jaa ei il­mais­ta lu­ku­na vaan `n`:n ja/tai `m`:n funk­tio­na.
tai

Ylä­ra­jaa joh­det­taes­sa voi syn­tyä han­ka­lia lau­sek­kei­ta, jois­ta ha­lu­taan pääs­tä hel­pom­piin. Mi­tä temp­pu­ja saa teh­dä?
Lau­sek­keen saa ai­na kor­va­ta var­mas­ti vä­hin­tään yh­tä­suu­rel­la.
Jos las­kel­ma ja­kau­tuu kah­teen ta­pauk­seen (esim. `x < 0` ja `x >= 0`), niin kun ta­pauk­set yh­dis­te­tään, on nii­den tuot­ta­mat lau­sek­keet las­ket­ta­va yh­teen.
Jos las­kel­ma ja­kau­tuu kah­teen ta­pauk­seen jois­ta tu­lee sa­ma lau­se­ke lop­pu­tu­lok­sek­si, niin si­tä saa käyt­tää sel­lai­se­naan kun ta­pauk­set yh­dis­te­tään.
Jos `f <= g` ja `a` on ko­ko­nais­lu­ku, niin `af`:n saa kor­va­ta `ag`:llä.
tai

Ylä­ra­ja kier­ros­ten mää­räl­le, jos alus­sa `n > m`

Seu­raa­vak­si las­kem­me jäl­jel­lä ole­vien kier­ros­ten mää­räl­le ylä­ra­jan sii­nä ta­pauk­ses­sa, et­tä ol­laan jon­kin kier­rok­sen alus­sa ja täl­lä het­kel­lä `n > m`. Edel­lä pää­tel­tiin täs­tä ole­tuk­ses­ta kä­sin kak­si hyö­dyl­lis­tä asiaa.

Jos jäl­jel­lä on `k` kier­ros­ta kun `n` on `n'`, niin kuin­ka mon­ta kier­ros­ta on enin­tään jäl­jel­lä, jos `n <= 2n'`?
tai

SYT-al­go­rit­mi lo­pet­taa, kun `m=` .
tai

Jos `n=1`, niin kuin­ka mon­ta kier­ros­ta on enin­tään jäl­jel­lä?
tai

Kir­joi­ta mui­hin kuin alim­paan lu­ku si­ten, et­tä jos `n` on enin­tään se, niin jäl­jel­lä on enin­tään il­moi­tet­tu mää­rä kier­rok­sia. Alim­paan kir­joi­ta lau­se­ke. Päät­te­le vas­taus ai­kai­sem­mis­ta vas­tauk­sis­ta.
 0 tai
 2 tai
 4 tai
 6 tai
 8 tai
10 tai
20 tai
`2i` tai

Yl­lä ole­van pe­rus­teel­la, kuin­ka mon­ta kier­ros­ta enin­tään tar­vi­taan, kun `n=1000`? Huo­maa, et­tä kier­ros­ten mää­rän on pak­ko ol­la ko­ko­nais­lu­ku. It­se asias­sa yl­lä ole­va päät­te­ly voi tuot­taa vain pa­ril­li­sia vas­tauk­sia.
tai

Siis `2i` kier­ros­ta riit­tää, mis­sä `i` on pie­nin ko­ko­nais­lu­ku si­ten, et­tä `n <= 2^i`. Rat­kai­se täs­tä `i` `n`:n funk­tio­na. Älä ota huo­mioon si­tä, et­tä `i`:n on pak­ko ol­la ko­ko­nais­lu­ku.
`i ~~` tai

Edel­li­nen tu­los ei ole ko­ko­nais­lu­ku, jos `n` ei ole kah­den po­tens­si. Se saa­tai­siin pä­te­väk­si ko­ko­nais­lu­vuk­si pyö­ris­tä­mäl­lä ylös­päin ns. kat­to­funk­tiol­la. Em­me kui­ten­kaan tee niin, kos­ka kat­to­funk­tio on han­ka­la las­kuis­sa. Sen si­jaan li­sääm­me tu­lok­seen lu­vun, jo­ka kas­vat­taa tu­los­ta var­mas­ti ai­na­kin yh­tä pal­jon kuin mi­tä ylös­päin pyö­ris­tys ko­ko­nais­lu­vuk­si voi enim­mil­lään kas­vat­taa. Ne­lo­nen oli­si täl­lai­nen lu­ku, mut­ta se ei ole pie­nin mah­dol­li­nen, sil­lä ylös­päin pyö­ris­tys ko­ko­nais­lu­vuk­si ei kos­kaan kas­va­ta ne­lo­sen ver­ran ei­kä edes kol­mo­sen ver­ran. Mi­kä on pie­nin täl­lai­nen lu­ku?
tai

Kir­joi­ta edel­lis­ten pe­rus­teel­la kier­ros­ten mää­räl­le ylä­ra­ja `n`:n funk­tio­na.
tai

Lau­se­ke an­taa hul­lun tu­lok­sen, jos `n=0`. Mut­ta `n` ei voi ol­la 0, kos­ka …olem­me yhä ta­pauk­ses­sa `n > m`, ja `m >= 0` kos­ka se on luon­nol­li­nen lu­ku.

Ylä­ra­ja ylei­ses­sä ta­pauk­ses­sa

Jäl­jel­lä on ta­pauk­set, jois­sa `n > m` ei pä­de alus­sa. Edel­lä to­det­tiin, et­tä jos `n = m` niin SYT-al­go­rit­mi te­kee kor­kein­taan yh­den kier­rok­sen, ja jos `n < m` niin SYT-al­go­rit­mi te­kee yh­den kier­rok­sen ja sen jäl­keen jat­kaa ku­ten ta­pauk­ses­sa `n > m`. Nyt `n` voi ol­la nol­la, mut­ta unoh­dam­me tä­män on­gel­man het­kek­si. Kir­joi­ta `n`:n funk­tio­na ylä­ra­ja, jo­ka pä­tee kai­kis­sa ta­pauk­sis­sa pait­si ta­pauk­ses­sa `n=0`.
tai

Lau­se­ke voi­tai­siin saa­da toi­mi­maan myös kun `n=0` te­ke­mäl­lä sii­tä mo­ni­mut­kai­sem­pi. Tie­to­jen­kä­sit­te­ly­tie­tees­sä on kui­ten­kin ta­pa­na jät­tää se te­ke­mät­tä, kos­ka kiin­nos­tuk­sen koh­tee­na on suo­ri­tus­ai­ka isoil­la syöt­teil­lä.

Olem­me sel­vit­tä­neet ylä­ra­jan kier­ros­ten mää­räl­le `n`:n funk­tio­na. En­tä jos ha­luam­me­kin sen `m`:n funk­tio­na? …En­sim­mäi­nen kier­ros ko­pioi `m`:n ar­von `n`:n pai­kal­le ja sen jäl­keen SYT-al­go­rit­mi jat­kaa ikään kuin se ar­vo oli­si ol­lut al­ku­pe­räi­nen `n`:n ar­vo. Li­säk­si en­sim­mäi­nen kier­ros saat­taa eh­don `n > m` voi­maan. Saa­daan siis yk­si plus ta­pauk­sen `n > m` ylä­ra­ja si­ten, et­tä `n`:n pai­kal­la on `m`. Se on sa­ma kuin ylei­sen ta­pauk­sen ylä­ra­ja si­ten, et­tä `n`:n pai­kal­la on `m`.

Kos­ka SYT-al­go­rit­mi te­kee kun­kin kier­rok­sen ai­ka­na vain pe­ru­so­pe­raa­tioi­ta ja vain va­kio­mää­rän, an­taa kier­ros­ten mää­rä oi­kean ku­van sii­tä, mi­ten suo­ri­tus­ai­ka kas­vaa `n`:n (tai `m`:n) funk­tio­na. Kier­ros­ten mää­räl­le joh­ta­mam­me ylä­ra­ja ei ole pa­ras mah­dol­li­nen, mut­ta sil­ti sen mu­kaan suo­ri­tus­ai­ka kas­vaa hi­taas­ti `n`:n funk­tio­na. Se riit­tää to­dis­ta­maan, et­tä SYT-al­go­rit­mi eli Euk­lei­deen al­go­rit­min mo­der­ni ver­sio on no­pea.