Teh­tä­vä:
Suu­rim­man yh­tei­sen te­ki­jän al­go­rit­mi

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

Täs­sä teh­tä­väs­sä tar­kas­tel­laan kuu­lui­san Euk­lei­deen al­go­rit­min ny­ky­ver­sio­ta. Se löy­tää te­hok­kaas­ti kah­den luon­nol­li­sen lu­vun suu­rim­man yh­tei­sen te­ki­jän. Luon­nol­li­set lu­vut ovat `NN = {0, 1, 2, ...}`. Täs­sä teh­tä­väs­sä kaik­ki lu­vut ovat luon­nol­li­sia lu­ku­ja, pait­si kun sa­no­taan toi­sin.

SYT-al­go­rit­min toi­min­ta tu­tuk­si

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`

Kos­ka `0 = 7*0` ja `0 = 123*0`, ovat se­kä 7 et­tä 123 nol­lan te­ki­jöi­tä. It­se asias­sa jo­kai­nen luon­nol­li­nen lu­ku on nol­lan te­ki­jä, sil­lä `0 = h*0` pä­tee jo­kai­sel­la `h`. Sik­si, jos alus­sa `n=m=0`, niin suu­rin­ta yh­teis­tä te­ki­jää ei ole ole­mas­sa.

Apu­tu­lok­sia

Te­ki­jän mää­ri­tel­mä on seu­raa­va. Ko­ko­nais­lu­ku `h` on `I`:n te­ki­jä jos ja vain jos on ole­mas­sa ko­ko­nais­lu­ku `i` si­ten, et­tä `I = hi`.

Tu­lem­me tar­vit­se­maan vii­si apu­tu­los­ta. To­dis­tam­me ne täs­sä.

1. Jos `h` on `I`:n te­ki­jä ja `J`:n te­ki­jä, niin `h` on myös lu­vun `I+J` te­ki­jä.
   Te­ki­jän mää­ri­tel­män mu­kaan on ole­mas­sa ko­ko­nais­lu­vut `i` ja `j` si­ten, et­tä `I = hi` ja `J = hj`. Pää­sem­me ta­voit­tee­seen löy­tä­mäl­lä ko­ko­nais­lu­vun `x` si­ten, et­tä `I+J = hx`. Täl­lai­nen lu­ku löy­tyy hel­pol­la sie­ven­nyk­sel­lä:
   `I+J =` ok_text Oi­kein! hide_expr f_nodes 7 h i + h j = + = end_of_answer arithmetic hide_expr f_top_opr #* f_nodes 5 h i + h j =
   tai
2. Jos `h` on `I`:n te­ki­jä ja `J`:n te­ki­jä, niin `h` on myös lu­vun `I-J` te­ki­jä.
   To­dis­tus on hy­vin sa­man­lai­nen kuin äs­ken. Help­po sie­ven­nys on seu­raa­va:
   ok_text Oi­kein! hide_expr f_nodes 3 I-J = = end_of_answer arithmetic hide_expr f_nodes 7 h i - h j = = end_of_answer arithmetic hide_expr f_top_opr #* f_nodes 5 h i - h j =
   tai
3. Jos `h` on `I`:n te­ki­jä, niin `h` on myös lu­vun `IJ` te­ki­jä.
   ok_text Oi­kein! hide_expr f_nodes 3 I J = = end_of_answer arithmetic hide_expr f_nodes 3 h i= () end_of_answer arithmetic hide_expr f_nodes 1 J= = end_of_answer arithmetic hide_expr f_nodes 1 h= end_of_answer arithmetic hide_expr f_nodes 3 i J= ()
   tai
   Nyt A-koh­das­sa mai­ni­tun `x`:n roo­lis­sa on ok_text Oi­kein! hide_expr f_nodes 3 i J =
   tai
4. Jos `J != 0` ja `h` on `I`:n ja `J`:n te­ki­jä, niin `h` on myös lu­vun `I mod J` te­ki­jä.

   Math­Check ei tun­ne sym­bo­lei­ta `text(div)` ja `text(mod)`, mut­ta `n \ text(div) \ m` saa­daan kir­joit­ta­mal­la |_n/m_|.

   Ja­ko­yh­tä­lön mu­kaan ok_text Oi­kein! only_no_yes_on hide_expr f_nodes 1 I = = end_of_answer only_no_yes_off arithmetic hide_expr f_nodes 6 J|_I/J_|= + end_of_answer arithmetic hide_expr only_no_yes_on f_nodes 1 I= `mod` end_of_answer arithmetic hide_expr f_nodes 1 J= .
   tai
   Täs­tä saa­daan `I mod J` = ok_text Oi­kein! hide_expr f_nodes 8 I - J |_I / J_|= , jo­ten väi­te seu­raa apu­tu­lok­sis­ta end_of_answer arithmetic only_no_yes_on hide_expr f_nodes 3 C+B= ja + .
   tai
5. Jos `J != 0` ja `h` on lu­ku­jen `J` ja `I mod J` te­ki­jä, niin `h` on myös `I`:n te­ki­jä.
   `I` = ok_text Oi­kein! hide_expr f_nodes 6 J|_I/J_|= + end_of_answer arithmetic hide_expr only_no_yes_on f_nodes 1 I= `text(mod)` end_of_answer arithmetic hide_expr f_nodes 1 J= , jo­ten väi­te seu­raa apu­tu­lok­sis­ta end_of_answer arithmetic hide_expr f_nodes 3 C+A= ja + .
   tai

SYT-al­go­rit­min oi­keel­li­suus

Täs­sä osas­sa osoi­tam­me, et­tä jos alus­sa `n != 0` tai `m != 0` niin SYT-al­go­rit­min vas­taus on oi­kea. Tär­kein­tä ei ole lop­pu­tu­los vaan päät­te­lyn har­joit­te­le­mi­nen, tai ai­na­kin päät­te­lyn ym­mär­tä­mi­sen har­joit­te­le­mi­nen. Ta­pauk­ses­sa `n=m=0` suu­rin­ta yh­teis­tä te­ki­jää ei ole ole­mas­sa, jo­ten jä­täm­me sen tut­ki­mat­ta.

Jot­ta al­ku­pe­räis­ten `n`:n ja `m`:n suu­rim­mas­ta yh­tei­ses­tä te­ki­jäs­tä oli­si hel­pom­pi pu­hua, an­nam­me sil­le ni­mek­si `s`. Ta­voit­teem­me on osoit­taa, et­tä `n`:n lo­pul­li­nen ar­vo on `s`.

SYT-al­go­rit­mi koos­tuu yh­des­tä sil­mu­kas­ta. 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. Tä­mä saat­taa vaa­tia luo­vuut­ta. Va­lit­tua väi­tet­tä kut­su­taan in­va­rian­tik­si.
2. Osoi­te­taan, et­tä in­va­riant­ti pä­tee sil­mu­kan alus­sa. Tä­mä on yleen­sä help­poa.
3. Osoi­te­taan, et­tä sil­mu­kan var­ta­lon suo­ri­tus ei voi saa­da in­va­riant­tia pois voi­mas­ta pait­si kor­kein­taan ti­la­päi­ses­ti. Täs­mäl­li­sem­min sa­not­tu­na: osoi­te­taan, et­tä jos in­va­riant­ti pä­tee sil­mu­kan var­ta­lon alus­sa, niin se pä­tee myös var­ta­lon lo­pus­sa (mut­ta saa ol­la pois voi­mas­ta kes­kel­lä var­ta­loa). Kos­ka sil­mu­kan var­ta­lo voi ol­la iso, tä­mä on usein työ­läs­tä, mut­ta täl­lä ker­taa ei ole. Täs­sä to­dis­tuk­ses­sa saa käyt­tää sil­mu­kan eh­toa.
4. Osoi­te­taan, et­tä sil­mu­kan suo­ri­tus lop­puu jos­kus. Tä­mä on usein hy­vin help­poa, mut­ta jos­kus erit­täin vai­keaa.
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. Tä­mä­kin on yleen­sä help­poa.

Tä­mä me­net­te­ly on pä­te­vä seu­raa­vas­ta syys­tä. Käy­täm­me SYT-al­go­rit­min ri­ve­jä esi­merk­ki­nä.

• Koh­ta 2 ker­too, et­tä kun ri­vin 1 alus­sa ol­laan en­sim­mäi­sen ker­ran eli sil­muk­kaa on kier­ret­ty nol­la kier­ros­ta, niin in­va­riant­ti pä­tee.
• Jos täl­löin `m=0` niin SYT-al­go­rit­mi lo­pet­taa. Muus­sa ta­pauk­ses­sa suo­ri­te­taan sil­mu­kan var­ta­lo si­ten, et­tä in­va­riant­ti pä­ti kun var­ta­lon suo­ri­tus al­koi. Koh­ta 3 ker­too, et­tä in­va­riant­ti pä­tee myös ri­vin 4 lo­pus­sa. Ri­vin 4 lo­pus­ta jou­du­taan uu­del­leen ri­vin 1 al­kuun, jo­ten kun ri­vin 1 alus­sa ol­laan toi­sen ker­ran, niin in­va­riant­ti pä­tee.
• Jos täl­löin `m=0` niin SYT-al­go­rit­mi lo­pet­taa. Muus­sa ta­pauk­ses­sa suo­ri­te­taan sil­mu­kan var­ta­lo si­ten, et­tä in­va­riant­ti pä­ti kun var­ta­lon suo­ri­tus al­koi. Koh­ta 3 ker­too, et­tä in­va­riant­ti pä­tee myös ri­vin 4 lo­pus­sa. Ri­vin 4 lo­pus­ta jou­du­taan uu­del­leen ri­vin 1 al­kuun, jo­ten kun ri­vin 1 alus­sa ol­laan kol­man­nen ker­ran, niin in­va­riant­ti pä­tee.
• Sa­mal­la ta­val­la voi­daan pää­tel­lä, et­tä kun ri­vin 1 alus­sa ol­laan nel­jän­nen, vii­den­nen, kuu­den­nen jne. ker­ran, niin in­va­riant­ti pä­tee. Siis in­va­riant­ti pä­tee ai­na kun suo­ri­tus on ri­vin 1 alus­sa.
• Koh­dan 4 pe­rus­teel­la sil­mu­kan suo­ri­tus lop­puu jos­kus. Äs­ken pää­tel­lyn pe­rus­teel­la in­va­riant­ti pä­tee sil­loin. Koh­das­ta 5 seu­raa, et­tä myös lop­pu­tu­lok­sel­ta ha­lut­tu asia pä­tee.

Käy­täm­me tä­tä me­ne­tel­mää to­dis­taak­sem­me, et­tä SYT-al­go­rit­min sil­muk­ka lo­pet­taa ja sil­loin `n=s`.

1. Va­lit­sem­me in­va­rian­tik­si väit­teen ”`s` on `n`:n ja `m`:n suu­rin yh­tei­nen te­ki­jä”.
2. Mie­ti en­sin it­se mik­si koh­ta 2 pä­tee, ja kat­so sit­ten opet­ta­jan se­li­tys täs­tä.Pi­tää osoit­taa, et­tä kun ol­laan sil­mu­kan alus­sa, niin `s` on `n`:n ja `m`:n suu­rin yh­tei­nen te­ki­jä. Tä­mä seu­raa vä­lit­tö­mäs­ti sii­tä, min­kä mer­ki­tyk­sen an­noim­me ai­kai­sem­min sym­bo­lil­le `s`. Me­hän pää­tim­me, et­tä se on ni­mi al­ku­pe­räis­ten `n`:n ja `m`:n suu­rim­mal­le yh­tei­sel­le te­ki­jäl­le.
3. Teh­tä­vä­nä on osoit­taa, et­tä jos ri­vin 2 alus­sa `s` on `n`:n ja `m`:n suu­rin yh­tei­nen te­ki­jä, niin myös ri­vin 4 lo­pus­sa `s` on `n`:n ja `m`:n suu­rin yh­tei­nen te­ki­jä. Apu­na saa käyt­tää tie­toa `m != 0`.
   Jou­dum­me pu­hu­maan sa­mo­jen muut­tu­jien `n` ja `m` ar­vois­ta kah­des­sa eri koh­das­sa, ni­mit­täin ri­vin 2 alus­sa ja ri­vin 4 lo­pus­sa. Tä­mä hel­pot­tuu, kun pää­täm­me mer­ki­tä ar­vo­ja ri­vin 4 lo­pus­sa `M`:llä ja `N`:llä, ja käy­täm­me `m`:ää ja `n`:ää tar­koit­ta­maan vain ar­vo­ja ri­vin 2 alus­sa. Sil­loin ei me­ne se­kai­sin, kum­paa koh­taa tar­koi­tam­me. Ri­vien 2, 3 ja 4 vuok­si
   only_no_yes_on ok_text Oi­kein! modulo 19 hide_expr f_nodes 3 N=m <=> = = ja end_of_answer arithmetic hide_expr f_nodes 1 M = = end_of_answer arithmetic hide_expr f_nodes 1 n = `mod`end_of_answer arithmetic hide_expr f_nodes 1 m =.
   tai

   Jo­kai­nen `n`:n ja `m`:n yh­tei­nen te­ki­jä on myös `N`:n te­ki­jä, kos­ka …`n`:n ja `m`:n yh­tei­nen te­ki­jä on `m`:n te­ki­jä ja `N=m`.

   Jo­kai­nen `n`:n ja `m`:n yh­tei­nen te­ki­jä on myös `M`:n te­ki­jä, kos­ka …`M=n mod m` ja edel­lä osoi­tet­tua väit­tä­mää D voi so­vel­taa niin, et­tä `I`:n pai­kal­la on only_no_yes_on ok_text Oi­kein! hide_expr f_nodes 1 n= ja `J`:n pai­kal­la on end_of_answer arithmetic hide_expr f_nodes 1 m=.
   tai

   Näis­tä yh­teen­sä seu­raa, et­tä `n`:n ja `m`:n suu­rin yh­tei­nen te­ki­jä on myös `N`:n ja `M`:n yh­tei­nen te­ki­jä. Vie­lä tar­vit­see osoit­taa, et­tä se on `N`:n ja `M`:n yh­tei­sis­tä te­ki­jöis­tä suu­rin. Teem­me sen osoit­ta­mal­la, et­tä jo­kai­nen `N`:n ja `M`:n yh­tei­nen te­ki­jä on myös `n`:n ja `m`:n te­ki­jä. Kun saam­me sen teh­tyä, on osoi­tet­tu, et­tä `n`:n ja `m`:n yh­tei­set te­ki­jät ovat sa­mat kuin `N`:n ja `M`:n yh­tei­set te­ki­jät, jol­loin toi­sen pa­rin suu­rin on myös toi­sen pa­rin suu­rin.

   Jo­kai­nen `N`:n ja `M`:n yh­tei­nen te­ki­jä on myös `m`:n te­ki­jä, kos­ka …`N`:n ja `M`:n yh­tei­nen te­ki­jä on `N`:n te­ki­jä ja `N=m`.

   Jo­kai­nen `N`:n ja `M`:n yh­tei­nen te­ki­jä on myös `n`:n te­ki­jä seu­raa­vas­ta syys­tä. Si­joit­ta­mal­la `N` ja `M` nii­den kans­sa yh­tä­suu­rien `n`:n ja/tai `m`:n avul­la il­mais­tu­jen osa­lau­sek­kei­den pai­kal­le saa­daan
   `n = m(n\ \text(div)\ m) + n mod m =`ok_text Oi­kein! var4 hide_expr f_nodes 8 N|_n/N_| + M = , jo­ten väi­te seu­raa apu­tu­lok­sis­ta end_of_answer arithmetic only_no_yes_on hide_expr f_nodes 3 C+A= ja + .
   tai

   Tar­vit­tiin­ko tie­toa `m != 0` mi­hin­kään?Kyl­lä. Apu­tu­lok­set D ja E vaa­ti­vat, et­tä `J != 0`. Kos­ka `J`:n roo­lis­sa oli `m`, tar­vit­tiin `m != 0`.

4. Käy­täm­me kir­jai­mia `n`, `m`, `N` ja `M` ku­ten koh­das­sa 3. Ja­ko­yh­tä­lö ker­too, et­tä (kir­joi­ta suu­ruus­ver­tai­lu) only_no_yes_on ok_text Oi­kein! modulo 19 hide_expr f_nodes 3 M < m <=> . Se tar­koit­taa, et­tä `m`:n ar­vo pie­ne­nee sil­mu­kan jo­kai­sel­la kier­rok­sel­la. Kos­ka `m`:n ar­vo on luon­nol­li­nen lu­ku, se voi pie­nen­tyä enin­tään niin mon­ta ker­taa kuin `m`:n ar­vo oli SYT-al­go­rit­min suo­ri­tuk­sen alus­sa. Sil­muk­ka lo­pet­taa kier­ret­tyään kor­kein­taan niin mon­ta ker­taa.
   tai
5. Pi­tää to­dis­taa, et­tä jos in­va­riant­ti pä­tee ja `m != 0` ei pä­de, niin `n=s`. Tä­mä on mel­ko help­poa.Kos­ka `m != 0` ei pä­de, pä­tee `m=0`. Kos­ka in­va­riant­ti pä­tee, on `s` lu­ku­jen `n` ja 0 suu­rin yh­tei­nen te­ki­jä. Ei voi ol­la `n=0`, kos­ka muu­toin `n`:llä ja nol­lal­la ei oli­si suu­rin­ta yh­teis­tä te­ki­jää, mi­kä oli­si vas­toin si­tä tie­toa, et­tä `s` on nii­den suu­rin yh­tei­nen te­ki­jä. Sik­si `n` on it­sen­sä suu­rin te­ki­jä. Kos­ka jo­kai­nen ko­ko­nais­lu­ku on nol­lan te­ki­jä, on `n` nol­lan te­ki­jä. Niin­pä lu­ku­jen `n` ja 0 suu­rin yh­tei­nen te­ki­jä on `n`. Sik­si `s=n`.

Euk­lei­deen ver­sio

Euk­lei­deen ver­sio oli täl­lai­nen:

while `m != 0` do
    `k` := maksimi`(n,m)`
    `m` := minimi`(n,m)`
    `n` := `k-m`

Siis mo­du­lo-ope­raa­tio oli kor­vat­tu sil­lä, et­tä suu­rem­mas­ta vä­hen­net­tiin pie­nem­pi.

Mi­ten se käyt­täy­tyy, kun aluk­si `n=49` ja `m=70`?

Mi­ten se käyt­täy­tyy, kun aluk­si `n=1000` ja `m=1`? Tut­kim­me vain jon­kin mat­kaa al­kua.

Euk­lei­deen ver­sio toi­mii joil­la­kin syöt­teil­lä no­peas­ti (ko­kei­le vaik­ka `m=n=1000`), mut­ta on ole­mas­sa lo­put­to­mas­ti syöt­tei­tä, joil­la se toi­mii hi­taas­ti (esi­mer­kik­si ai­na kun `n` on iso ja `m=1`). Mo­der­ni SYT-al­go­rit­mi ei ole mil­lään syöt­teel­lä to­del­la hi­das. Sen no­peu­den tut­ki­mi­nen on oman teh­tä­vän­sä ar­voi­nen asia.