1   while m ≠ 0 do
2       k := n mod m
3       n := m
4       m := k
I = J(I 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ä:

nm 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

Edel­lä ol­leen esi­mer­kin 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­pauk­ses­sa n:n ar­vo jää en­nal­leen.

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

Edel­lä ol­lees­sa 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

Edel­lä ol­lees­sa esi­mer­kis­sä 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:
mkier­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­tus­ajas­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 x, niin kuin­ka mon­ta kier­ros­ta on enin­tään jäl­jel­lä, jos n ≤ 2x?
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 sel­lai­nen lu­ku, 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. Nyt ei hae­ta tark­kaa ar­voa vaan ylä­li­ki­ar­voa, jon­ka voi pää­tel­lä 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 sel­lai­nen ko­ko­nais­lu­ku, et­tä n ≤ 2i. 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.