1.2 Gweithdrefnau a'r Prosesau a Gynhyrchant

Rydym bellach wedi ystyried elfennau rhaglennu: defnyddiasom weithrediadau rhifyddol cyntefig, cyfunasom y gweithrediadau hyn, a haniaethasom y gweithrediadau cyfansawdd hyn drwy eu diffinio fel gweithdrefnau cyfansawdd. Ond nid yw hynny'n ddigon i'n galluogi i ddweud ein bod yn gwybod sut i raglennu. Mae ein sefyllfa'n debyg i sefyllfa rhywun sydd wedi dysgu'r rheolau ar gyfer symud y darnau mewn gwyddbwyll ond nad yw'n gwybod dim am agoriadau nodweddiadol, tactegau na strategaeth. Fel y chwaraewr gwyddbwyll newydd, nid ydym eto'n gwybod y patrymau defnydd cyffredin yn y maes. Nid oes gennym y wybodaeth am ba symudiadau sy'n werth eu gwneud (pa weithdrefnau sy'n werth eu diffinio). Nid oes gennym y profiad i ragweld canlyniadau gwneud symudiad (gweithredu gweithdrefn).

Mae'r gallu i ddychmygu canlyniadau'r gweithredoedd dan ystyriaeth yn hanfodol i ddod yn rhaglennydd arbenigol, fel y mae mewn unrhyw weithgaredd creadigol sy'n cyfuno elfennau. Wrth ddod yn ffotograffydd arbenigol, er enghraifft, rhaid dysgu sut i edrych ar olygfa a gwybod pa mor dywyll y bydd pob rhan yn ymddangos ar brint ar gyfer pob dewis posibl o amodau dinoethi a datblygu. Dim ond wedyn y gellir rhesymu'n ôl, gan gynllunio fframio, goleuo, dinoethi a datblygu i gael yr effeithiau a ddymunir. Felly hefyd gyda rhaglennu, lle rydym yn cynllunio'r trywydd gweithredu y bydd proses yn ei ddilyn ac yn rheoli'r broses drwy raglen. I ddod yn arbenigwyr, rhaid inni ddysgu dychmygu'r prosesau a gynhyrchir gan amrywiol fathau o weithdrefnau. Dim ond ar ôl datblygu'r sgìl hwn y gallwn ddysgu adeiladu rhaglenni sy'n arddangos yr ymddygiad a ddymunir yn ddibynadwy.

Patrwm ar gyfer esblygiad lleol proses gyfrifiadurol yw gweithdrefn. Mae'n pennu sut yr adeiladir pob cam o'r broses ar y cam blaenorol. Hoffem allu gwneud gosodiadau am ymddygiad cyffredinol, neu fyd-eang, proses y mae gweithdrefn wedi pennu ei hesblygiad lleol. Mae hyn yn anodd iawn yn gyffredinol, ond gallwn o leiaf geisio disgrifio rhai patrymau nodweddiadol yn esblygiad prosesau.

Yn yr adran hon byddwn yn archwilio rhai “siapiau” cyffredin ar gyfer prosesau a gynhyrchir gan weithdrefnau syml. Byddwn hefyd yn ymchwilio i'r cyfraddau y mae'r prosesau hyn yn defnyddio'r adnoddau cyfrifiadurol pwysig, amser a gofod. Mae'r gweithdrefnau y byddwn yn eu hystyried yn syml iawn. Mae eu rôl yn debyg i rôl patrymau prawf mewn ffotograffiaeth: patrymau prototeip sydd wedi'u gorsymleiddio ydynt, yn hytrach nag enghreifftiau ymarferol ynddynt eu hunain.

1.2.1Dychweliad Llinol ac Iteru

Dechreuwn drwy ystyried y ffwythiant ffactoraidd, a ddiffinnir gan $$n!=n\cdot <!--\; \cdot \; -->(n-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->(n-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->3\cdot <!--\; \cdot \; -->2\cdot <!--\; \cdot \; -->1.$$ Mae llawer o ffyrdd o gyfrifiannu ffactorialau. Un ffordd yw defnyddio'r sylw fod $n!$ yn hafal i $n$ wedi'i luosi â $(n-<!--\; -\; -->1)!$ ar gyfer unrhyw gyfanrif positif $n$: $$n!=n\cdot <!--\; \cdot \; -->[(n-<!--\; -\; -->1)\cdot <!--\; \cdot \; -->(n-<!--\; -\; -->2)\cdots <!--\; \cdots \; -->3\cdot <!--\; \cdot \; -->2\cdot <!--\; \cdot \; -->1]=n\cdot <!--\; \cdot \; -->(n-<!--\; -\; -->1)!.$$ Felly, gallwn gyfrifiannu $n!$ drwy gyfrifiannu $(n-<!--\; -\; -->1)!$ a lluosi'r canlyniad â $n$. Os ychwanegwn yr amod fod 1! yn hafal i 1, mae'r sylw hwn yn trosi'n uniongyrchol yn weithdrefn:

(define (factorial n)
  (if (= n 1) 
      1 
      (* n (factorial (- n 1)))))

Gallwn ddefnyddio model amnewid 1.1.5 i wylio'r weithdrefn hon ar waith yn cyfrifiannu 6!, fel y dangosir yn Ffigur 1.3.

Gadewch inni bellach edrych ar gyfrifiannu ffactorialau o safbwynt gwahanol. Gallem ddisgrifio rheol ar gyfer cyfrifiannu $n!$ drwy bennu ein bod yn lluosi 1 â 2 yn gyntaf, yna'n lluosi'r canlyniad â 3, yna â 4, ac ati nes cyrraedd $n$. Yn fwy ffurfiol, rydym yn cadw lluoswm cronnus, ynghyd â rhifydd sy'n cyfrif o 1 hyd at $n$. Gallwn ddisgrifio'r cyfrifiad drwy ddweud bod y rhifydd a'r lluoswm yn newid ar yr un pryd o un cam i'r nesaf yn ôl y rheol

product $\leftarrow <!--\; \leftarrow \; -->$ counter * product
counter $\leftarrow <!--\; \leftarrow \; -->$ counter + 1

a phennu mai $n!$ yw gwerth y lluoswm pan fydd y rhifydd yn fwy na $n$.

Unwaith eto, gallwn ail-lunio ein disgrifiad fel gweithdrefn ar gyfer cyfrifiannu ffactorialau:²⁹

(define (factorial n) 
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

Fel o'r blaen, gallwn ddefnyddio'r model amnewid i ddelweddu'r broses o gyfrifiannu 6!, fel y dangosir yn Ffigur 1.4.

Cymharwch y ddwy broses. O un safbwynt, prin y maent yn ymddangos yn wahanol o gwbl. Mae'r ddwy'n cyfrifiannu'r un ffwythiant mathemategol ar yr un parth, ac mae angen nifer o gamau sy'n gyfrannol ag $n$ ar bob un i gyfrifiannu $n!$. Yn wir, mae'r ddwy broses hyd yn oed yn cyflawni'r un dilyniant o luosiadau, gan gael yr un dilyniant o luosymiau rhannol. Ar y llaw arall, pan ystyriwn “siapiau” y ddwy broses, gwelwn eu bod yn esblygu'n dra gwahanol.

Ystyriwch y broses gyntaf. Mae'r model amnewid yn datgelu siâp o ehangu ac yna grebachu, fel y mae'r saeth yn Ffigur 1.3 yn ei ddangos. Mae'r ehangu'n digwydd wrth i'r broses adeiladu cadwyn o weithrediadau gohiriedig (cadwyn o luosiadau yn yr achos hwn). Mae'r crebachu'n digwydd wrth i'r gweithrediadau gael eu cyflawni mewn gwirionedd. Gelwir proses o'r math hwn, a nodweddir gan gadwyn o weithrediadau gohiriedig, yn broses ddychweliadol. Mae cyflawni'r broses hon yn ei gwneud yn ofynnol i'r dehonglydd gadw cofnod o'r gweithrediadau sydd i'w cyflawni'n ddiweddarach. Wrth gyfrifiannu $n!$, mae hyd y gadwyn o luosiadau gohiriedig, ac felly faint o wybodaeth sydd ei hangen i gadw cofnod ohoni, yn tyfu'n llinol ag $n$ (yn gyfrannol ag $n$), yn union fel nifer y camau. Gelwir proses o'r fath yn broses ddychweliadol linol.

Mewn cyferbyniad, nid yw'r ail broses yn tyfu ac yn crebachu. Ar bob cam, y cyfan y mae angen inni gadw cofnod ohono, ar gyfer unrhyw $n$, yw gwerthoedd cyfredol y newidynnau product, counter, a max-count. Galwn hyn yn broses iteru. Yn gyffredinol, proses iteru yw un y gellir crynhoi ei chyflwr gan nifer sefydlog o newidynnau cyflwr, ynghyd â rheol sefydlog sy'n disgrifio sut y dylid diweddaru'r newidynnau cyflwr wrth i'r broses symud o gyflwr i gyflwr, a phrawf terfynu (dewisol) sy'n pennu'r amodau y dylai'r broses derfynu oddi tanynt. Wrth gyfrifiannu $n!$, mae nifer y camau sydd eu hangen yn tyfu'n llinol ag $n$. Gelwir proses o'r fath yn broses iteru linol.

Gellir gweld y cyferbyniad rhwng y ddwy broses mewn ffordd arall. Yn yr achos iteru, mae newidynnau'r rhaglen yn rhoi disgrifiad cyflawn o gyflwr y broses ar unrhyw adeg. Pe baem yn atal y cyfrifiad rhwng camau, y cyfan y byddai angen inni ei wneud i ailddechrau'r cyfrifiad fyddai rhoi gwerthoedd tri newidyn y rhaglen i'r dehonglydd. Nid felly gyda'r broses ddychweliadol. Yn yr achos hwn, ceir rhywfaint o wybodaeth “gudd” ychwanegol, a gedwir gan y dehonglydd ac nad yw wedi'i chynnwys yn newidynnau'r rhaglen, sy'n dangos “ble mae'r broses” wrth fynd drwy'r gadwyn o weithrediadau gohiriedig. Po hiraf y gadwyn, mwyaf o wybodaeth y mae'n rhaid ei chadw.³⁰

Wrth gyferbynnu iteru a dychweliad, rhaid inni fod yn ofalus i beidio â chymysgu'r syniad o broses ddychweliadol â'r syniad o weithdrefn ddychweliadol. Pan ddisgrifiwn weithdrefn yn ddychweliadol, rydym yn cyfeirio at y ffaith gystrawennol fod diffiniad y weithdrefn yn cyfeirio (naill ai'n uniongyrchol neu'n anuniongyrchol) at y weithdrefn ei hun. Ond pan ddisgrifiwn broses fel un sy'n dilyn patrwm sydd, er enghraifft, yn ddychweliadol linol, rydym yn sôn am sut mae'r broses yn esblygu, nid am gystrawen y ffordd yr ysgrifennir gweithdrefn. Gall ymddangos yn annifyr ein bod yn cyfeirio at weithdrefn ddychweliadol megis fact-iter fel un sy'n cynhyrchu proses iteru. Fodd bynnag, proses iteru yw'r broses mewn gwirionedd: mae ei thri newidyn cyflwr yn cofnodi ei chyflwr yn llwyr, a dim ond tri newidyn y mae angen i ddehonglydd gadw cofnod ohonynt er mwyn cyflawni'r broses.

Un rheswm pam y gall y gwahaniaeth rhwng proses a gweithdrefn fod yn ddryslyd yw bod y rhan fwyaf o weithrediadau ieithoedd cyffredin (gan gynnwys Ada, Pascal, a C) wedi'u dylunio fel bod dehongli unrhyw weithdrefn ddychweliadol yn defnyddio swm o gof sy'n tyfu gyda nifer y galwadau gweithdrefn, hyd yn oed pan fo'r broses a ddisgrifir, mewn egwyddor, yn broses iteru. O ganlyniad, dim ond drwy ddefnyddio “cystrawennau dolennu” pwrpasol megis do, repeat, until, for, a while y gall yr ieithoedd hyn ddisgrifio prosesau iteru. Nid yw gweithrediad Scheme y byddwn yn ei ystyried ym Mhennod 5 yn rhannu'r diffyg hwn. Bydd yn cyflawni proses iteru mewn gofod cyson, hyd yn oed os disgrifir y broses iteru gan weithdrefn ddychweliadol. Gelwir gweithrediad â'r briodwedd hon yn ddychweliadol yn y gynffon. Gyda gweithrediad sy'n ddychweliadol yn y gynffon, gellir mynegi iteru drwy fecanwaith arferol galwad gweithdrefn, fel mai dim ond fel siwgr cystrawennol y mae cystrawennau iteru arbennig yn ddefnyddiol.³¹

Ymarfer 1.9: Mae pob un o'r ddwy weithdrefn ganlynol yn diffinio dull ar gyfer adio dau gyfanrif positif yn nhermau'r gweithdrefnau inc, sy'n cynyddu ei harg 1, a dec, sy'n lleihau ei harg 1.

(define (+ a b)
  (if (= a 0) 
      b 
      (inc (+ (dec a) b))))

(define (+ a b)
  (if (= a 0) 
      b 
      (+ (dec a) (inc b))))

Gan ddefnyddio'r model amnewid, dangoswch y broses a gynhyrchir gan bob gweithdrefn wrth werthuso (+ 4 5). Ai prosesau iteru neu brosesau dychweliadol yw'r rhain?

Ymarfer 1.10: Mae'r weithdrefn ganlynol yn cyfrifiannu ffwythiant mathemategol o'r enw ffwythiant Ackermann.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

Beth yw gwerthoedd y mynegiadau canlynol?

(A 1 10)
(A 2 4)
(A 3 3)

Ystyriwch y gweithdrefnau canlynol, lle mai A yw'r weithdrefn a ddiffiniwyd uchod:

(define (f n) (A 0 n))
(define (g n) (A 1 n))
(define (h n) (A 2 n))
(define (k n) (* 5 n n))

Rhowch ddiffiniadau mathemategol cryno o'r ffwythiannau a gyfrifiannir gan y gweithdrefnau f, g, a h ar gyfer gwerthoedd cyfanrif positif o $n$. Er enghraifft, mae (k n) yn cyfrifiannu $5n^2$.

1.2.2Dychweliad Coeden

Gelwir patrwm cyfrifiannu cyffredin arall yn ddychweliad coeden. Er enghraifft, ystyriwch gyfrifiannu dilyniant rhifau Fibonacci, lle mae pob rhif yn swm y ddau sy'n ei ragflaenu:

Yn gyffredinol, gellir diffinio rhifau Fibonacci drwy'r rheol $$\text{Fib}(n)=\{\begin{array}{ll}0& \text{os yw}n=0,\\ 1& \text{os yw}n=1,\\ \text{Fib}(n-<!--\; -\; -->1)+\text{Fib}(n-<!--\; -\; -->2)& \text{fel arall}.\end{array}$$ Gallwn drosi'r diffiniad hwn ar unwaith yn weithdrefn ddychweliadol ar gyfer cyfrifiannu rhifau Fibonacci:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Ystyriwch batrwm y cyfrifiad hwn. I gyfrifiannu (fib 5), rydym yn cyfrifiannu (fib 4) a (fib 3). I gyfrifiannu (fib 4), rydym yn cyfrifiannu (fib 3) a (fib 2). Yn gyffredinol, mae'r broses sy'n esblygu yn edrych fel coeden, fel y dangosir yn Ffigur 1.5. Sylwch fod y canghennau'n rhannu'n ddwy ar bob lefel (heblaw ar y gwaelod); mae hyn yn adlewyrchu'r ffaith fod y weithdrefn fib yn ei galw ei hun ddwywaith bob tro y'i gelwir.

Mae'r weithdrefn hon yn addysgiadol fel prototeip o ddychweliad coeden, ond mae'n ffordd ofnadwy o gyfrifiannu rhifau Fibonacci oherwydd ei bod yn gwneud cymaint o gyfrifiannu diangen. Sylwch yn Ffigur 1.5 fod cyfrifiad cyfan (fib 3)—bron hanner y gwaith—yn cael ei ddyblygu. Yn wir, nid yw'n anodd dangos mai nifer yr adegau y bydd y weithdrefn yn cyfrifiannu (fib 1) neu (fib 0) (nifer y dail yn y goeden uchod, yn gyffredinol) yw $\text{Fib}(n+1)$ yn union. I gael syniad o ba mor wael yw hyn, gellir dangos bod gwerth $\text{Fib}(n)$ yn tyfu'n esbonyddol ag $n$. Yn fwy manwl (gweler Ymarfer 1.13), $\text{Fib}(n)$ yw'r cyfanrif agosaf at ${\mathrm{\phi <!--\; \phi \; -->}}^n/\sqrt{5}$, lle mai $$\mathrm{\phi <!--\; \phi \; -->}=\frac{1+\sqrt{5}}{2}\approx <!--\; \approx \; -->1.6180$$ yw'r gymhareb aur, sy'n bodloni'r hafaliad $${\mathrm{\phi <!--\; \phi \; -->}}^2=\mathrm{\phi <!--\; \phi \; -->}+1.$$ Felly, mae'r broses yn defnyddio nifer o gamau sy'n tyfu'n esbonyddol gyda'r mewnbwn. Ar y llaw arall, dim ond yn llinol gyda'r mewnbwn y mae'r gofod sydd ei angen yn tyfu, oherwydd dim ond pa nodau sydd uwch ein pennau yn y goeden ar unrhyw adeg yn y cyfrifiad y mae angen inni gadw cofnod ohonynt. Yn gyffredinol, bydd nifer y camau sydd eu hangen ar broses ddychweliadol goeden yn gyfrannol â nifer y nodau yn y goeden, tra bydd y gofod sydd ei angen yn gyfrannol â dyfnder mwyaf y goeden.

Gallwn hefyd lunio proses iteru ar gyfer cyfrifiannu rhifau Fibonacci. Y syniad yw defnyddio pâr o gyfanrifau $a$ a $b$, a gychwynnir yn $\text{Fib(1) = 1}$ a $\text{Fib(0) = 0}$, a chymhwyso'r trawsffurfiadau cydamserol canlynol dro ar ôl tro

Nid yw'n anodd dangos, ar ôl cymhwyso'r trawsffurfiad hwn $n$ gwaith, y bydd $a$ a $b$ yn hafal, yn eu trefn, i $\text{Fib}(n+1)$ a $\text{Fib}(n)$. Felly, gallwn gyfrifiannu rhifau Fibonacci drwy iteru gan ddefnyddio'r weithdrefn

(define (fib n) 
  (fib-iter 1 0 n))

(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))

Iteriad llinol yw'r ail ddull hwn ar gyfer cyfrifiannu $\text{Fib}(n)$. Mae'r gwahaniaeth yn nifer y camau sydd eu hangen ar y ddau ddull—un yn llinol ag $n$, a'r llall yn tyfu mor gyflym ag $\text{Fib}(n)$ ei hun—yn enfawr, hyd yn oed ar gyfer mewnbynnau bach.

Ni ddylid casglu o hyn fod prosesau dychweliadol coeden yn ddiwerth. Pan ystyriwn brosesau sy'n gweithredu ar ddata wedi'u strwythuro'n hierarchaidd yn hytrach nag ar rifau, byddwn yn gweld bod dychweliad coeden yn arf naturiol a phwerus.³² Ond hyd yn oed mewn gweithrediadau rhifol, gall prosesau dychweliadol coeden fod yn ddefnyddiol i'n helpu i ddeall a dylunio rhaglenni. Er enghraifft, er bod y weithdrefn fib gyntaf yn llawer llai effeithlon na'r ail, mae'n fwy uniongyrchol, gan nad yw ond ychydig mwy na throsi diffiniad dilyniant Fibonacci i Lisp. Er mwyn llunio'r algorithm iteru, roedd angen sylwi y gellid ail-lunio'r cyfrifiad fel iteriad â thri newidyn cyflwr.

Enghraifft: Cyfrif ffyrdd o roi newid

Dim ond ychydig o ddyfeisgarwch sydd ei angen i feddwl am yr algorithm Fibonacci iteru. Mewn cyferbyniad, ystyriwch y broblem ganlynol: mewn sawl ffordd wahanol y gallwn roi newid am $1.00, o gael darnau arian hanner doler, chwarter doler, deg sent, pum sent, ac un sent? Yn fwy cyffredinol, a allwn ysgrifennu gweithdrefn i gyfrifiannu nifer y ffyrdd o newid unrhyw swm penodol o arian?

Mae ateb syml i'r broblem hon ar ffurf gweithdrefn ddychweliadol. Tybiwch ein bod yn meddwl am y mathau o ddarnau arian sydd ar gael fel rhai sydd wedi'u trefnu mewn rhyw drefn. Yna mae'r berthynas ganlynol yn dal:

Mae nifer y ffyrdd o newid swm $a$ gan ddefnyddio $n$ math o ddarnau arian yn hafal i

• nifer y ffyrdd o newid swm $a$ gan ddefnyddio pob math o ddarn arian heblaw'r cyntaf, ynghyd â
• nifer y ffyrdd o newid swm $a-<!--\; -\; -->d$ gan ddefnyddio pob un o'r $n$ math o ddarnau arian, lle mai $d$ yw gwerth y math cyntaf o ddarn arian.

I weld pam mae hyn yn wir, sylwch y gellir rhannu'r ffyrdd o roi newid yn ddau grŵp: y rhai nad ydynt yn defnyddio unrhyw ddarn o'r math cyntaf, a'r rhai sydd yn gwneud hynny. Felly, mae cyfanswm nifer y ffyrdd o roi newid am ryw swm yn hafal i nifer y ffyrdd o roi newid am y swm heb ddefnyddio unrhyw ddarn o'r math cyntaf, ynghyd â nifer y ffyrdd o roi newid gan dybio ein bod yn defnyddio'r math cyntaf o ddarn arian. Ond mae'r ail nifer yn hafal i nifer y ffyrdd o roi newid am y swm sy'n weddill ar ôl defnyddio un darn o'r math cyntaf.

Felly, gallwn leihau'r broblem o newid swm penodol yn ddychweliadol i'r broblem o newid symiau llai gan ddefnyddio llai o fathau o ddarnau arian. Ystyriwch y rheol leihau hon yn ofalus, ac argyhoeddwch eich hun y gallwn ei defnyddio i ddisgrifio algorithm os pennwn yr achosion dirywiedig canlynol:³³

• Os yw $a$ yn union 0, dylem gyfrif hynny fel 1 ffordd o roi newid.
• Os yw $a$ yn llai na 0, dylem gyfrif hynny fel 0 ffordd o roi newid.
• Os yw $n$ yn 0, dylem gyfrif hynny fel 0 ffordd o roi newid.

Gallwn drosi'r disgrifiad hwn yn hawdd yn weithdrefn ddychweliadol:

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) 
             (= kinds-of-coins 0)) 
         0)
        (else 
         (+ (cc amount (- kinds-of-coins 1))
            (cc (- amount (first-denomination 
                           kinds-of-coins))
                kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(Mae'r weithdrefn first-denomination yn cymryd nifer y mathau o ddarnau arian sydd ar gael yn fewnbwn ac yn dychwelyd gwerth y math cyntaf. Yma rydym yn meddwl am y darnau arian fel rhai sydd wedi'u trefnu o'r mwyaf i'r lleiaf, ond byddai unrhyw drefn yr un mor addas.) Gallwn bellach ateb ein cwestiwn gwreiddiol am newid doler:

(count-change 100)
292

Mae Count-change yn cynhyrchu proses ddychweliadol goeden sydd ag ailadroddiadau diangen tebyg i'r rhai yn ein gweithrediad cyntaf o fib. (Bydd yn cymryd cryn dipyn o amser i gyfrifiannu'r 292 hwnnw.) Ar y llaw arall, nid yw'n amlwg sut i ddylunio algorithm gwell ar gyfer cyfrifiannu'r canlyniad, a gadawn y broblem hon fel her. Mae'r sylw y gall proses ddychweliadol goeden fod yn aneffeithlon iawn ond yn aml yn hawdd ei phennu a'i deall wedi arwain pobl i awgrymu y gellid cael y gorau o'r ddau fyd drwy ddylunio “crynhoydd clyfar” a allai drawsffurfio gweithdrefnau dychweliadol coeden yn weithdrefnau mwy effeithlon sy'n cyfrifiannu'r un canlyniad.³⁴

Ymarfer 1.11: Diffinnir ffwythiant $f$ gan y rheol fod $f(n)=n$ os yw $n<3$, a $f(n)=f(n-<!--\; -\; -->1)+2f(n-<!--\; -\; -->2)+3f(n-<!--\; -\; -->3)$ os yw $n\ge <!--\; \ge \; -->3$. Ysgrifennwch weithdrefn sy'n cyfrifiannu $f$ drwy broses ddychweliadol. Ysgrifennwch weithdrefn sy'n cyfrifiannu $f$ drwy broses iteru.

Ymarfer 1.12: Gelwir y patrwm rhifau canlynol yn driongl Pascal.

         1
       1   1
     1   2   1
   1   3   3   1
 1   4   6   4   1
       . . .

Mae'r rhifau ar ymyl y triongl i gyd yn 1, ac mae pob rhif y tu mewn i'r triongl yn swm y ddau rif uwch ei ben.³⁵ Ysgrifennwch weithdrefn sy'n cyfrifiannu elfennau triongl Pascal drwy broses ddychweliadol.

Ymarfer 1.13: Profwch mai $\text{Fib}(n)$ yw'r cyfanrif agosaf at ${\mathrm{\phi <!--\; \phi \; -->}}^n/\sqrt{5}$, lle mae $\mathrm{\phi <!--\; \phi \; -->}=(1+\sqrt{5})/2$. Awgrym: gosodwch $\mathrm{\psi <!--\; \psi \; -->}=(1-<!--\; -\; -->\sqrt{5})/2$. Defnyddiwch anwythiad a diffiniad rhifau Fibonacci (gweler 1.2.2) i brofi bod $\text{Fib}(n)=({\mathrm{\phi <!--\; \phi \; -->}}^n-<!--\; -\; -->{\mathrm{\psi <!--\; \psi \; -->}}^n)/\sqrt{5}$.

1.2.3Trefnau Twf

Mae'r enghreifftiau blaenorol yn dangos y gall prosesau amrywio'n sylweddol yn y cyfraddau y maent yn defnyddio adnoddau cyfrifiadurol. Un ffordd gyfleus o ddisgrifio'r gwahaniaeth hwn yw defnyddio'r syniad o drefn twf i gael mesur bras o'r adnoddau sydd eu hangen ar broses wrth i'r mewnbynnau fynd yn fwy.

Gadewch i $n$ fod yn baramedr sy'n mesur maint y broblem, ac i $R(n)$ fod yn faint yr adnoddau sydd eu hangen ar y broses ar gyfer problem o faint $n$. Yn ein henghreifftiau blaenorol, cymerasom mai $n$ oedd y rhif yr oedd ffwythiant penodol i'w gyfrifiannu ar ei gyfer, ond mae posibiliadau eraill. Er enghraifft, os mai ein nod yw cyfrifiannu brasamcan o wreiddyn sgwâr rhif, gallem gymryd mai $n$ yw nifer y digidau o gywirdeb sydd eu hangen. Ar gyfer lluosi matricsau, gallem gymryd mai $n$ yw nifer y rhesi yn y matricsau. Yn gyffredinol, mae nifer o briodweddau'r broblem y bydd yn ddymunol dadansoddi proses benodol mewn perthynas â hwy. Yn yr un modd, gallai $R(n)$ fesur nifer y cofrestri storio mewnol a ddefnyddir, nifer y gweithrediadau peiriant elfennol a gyflawnir, ac ati. Mewn cyfrifiaduron sy'n gwneud nifer sefydlog o weithrediadau ar y tro yn unig, bydd yr amser sydd ei angen yn gyfrannol â nifer y gweithrediadau peiriant elfennol a gyflawnir.

Dywedwn fod gan $R(n)$ drefn twf $\mathrm{\Theta <!--\; \Theta \; -->}(f(n))$, a ysgrifennir $R(n)=\mathrm{\Theta <!--\; \Theta \; -->}(f(n))$ (a yngenir “theta o $f(n)$”), os oes cysonion positif $k_1$ a $k_2$ sy'n annibynnol ar $n$ fel bod $k_{1}f(n)\le <!--\; \le \; -->R(n)\le <!--\; \le \; -->k_{2}f(n)$ ar gyfer unrhyw werth digon mawr o $n$. (Mewn geiriau eraill, ar gyfer $n$ mawr, mae'r gwerth $R(n)$ wedi'i wasgu rhwng $k_{1}f(n)$ a $k_{2}f(n)$.)

Er enghraifft, gyda'r broses ddychweliadol linol ar gyfer cyfrifiannu ffactorial a ddisgrifiwyd yn 1.2.1, mae nifer y camau'n tyfu'n gyfrannol â'r mewnbwn $n$. Felly, mae'r camau sydd eu hangen ar y broses hon yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Gwelasom hefyd fod y gofod sydd ei angen yn tyfu fel $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Ar gyfer y ffactorial iteru, mae nifer y camau'n dal yn $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ ond mae'r gofod yn $\mathrm{\Theta <!--\; \Theta \; -->}(1)$—hynny yw, yn gyson.³⁶ Mae'r cyfrifiad Fibonacci dychweliadol coeden yn gofyn am $\mathrm{\Theta <!--\; \Theta \; -->}({\mathrm{\phi <!--\; \phi \; -->}}^n)$ o gamau a gofod $\mathrm{\Theta <!--\; \Theta \; -->}(n)$, lle mai $\mathrm{\phi <!--\; \phi \; -->}$ yw'r gymhareb aur a ddisgrifiwyd yn 1.2.2.

Disgrifiad bras yn unig o ymddygiad proses a ddarperir gan drefnau twf. Er enghraifft, mae gan broses sydd angen $n^2$ o gamau, proses sydd angen $1000n^2$ o gamau, a phroses sydd angen $3n^2+10n+17$ o gamau i gyd drefn twf $\mathrm{\Theta <!--\; \Theta \; -->}(n^2)$. Ar y llaw arall, mae trefn twf yn rhoi arwydd defnyddiol o sut y gallwn ddisgwyl i ymddygiad y broses newid wrth inni newid maint y broblem. Ar gyfer proses $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ (linol), bydd dyblu'r maint yn dyblu'n fras faint yr adnoddau a ddefnyddir. Ar gyfer proses esbonyddol, bydd pob cynnydd unedol ym maint y broblem yn lluosi defnydd yr adnoddau â ffactor cyson. Yng ngweddill 1.2 byddwn yn archwilio dau algorithm y mae eu trefn twf yn logarithmig, fel bod dyblu maint y broblem yn cynyddu'r angen am adnoddau gan swm cyson.

Ymarfer 1.14: Lluniwch y goeden sy'n dangos y broses a gynhyrchir gan weithdrefn count-change 1.2.2 wrth roi newid am 11 sent. Beth yw trefnau twf y gofod a nifer y camau a ddefnyddir gan y broses hon wrth i'r swm sydd i'w newid gynyddu?

Ymarfer 1.15: Gellir cyfrifiannu sin ongl (a bennir mewn radianau) drwy ddefnyddio'r brasamcan $\sin <!--\; \; -->x\approx <!--\; \approx \; -->x$ os yw $x$ yn ddigon bach, a'r unfathiant trigonometrig $$\sin <!--\; \; -->x=3\sin <!--\; \; -->\frac{x}{3}-<!--\; -\; -->4{\sin }^3<!--\; \; -->\frac{x}{3}$$ i leihau maint arg sin. (At ddibenion yr ymarfer hwn, ystyrir ongl yn “ddigon bach” os nad yw ei maint yn fwy na 0.1 radian.) Mae'r gweithdrefnau canlynol yn ymgorffori'r syniadau hyn:

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))

1. Sawl gwaith y cymhwysir y weithdrefn p wrth werthuso (sine 12.15)?
2. Beth yw trefn twf y gofod a nifer y camau (fel ffwythiant o $a$) a ddefnyddir gan y broses a gynhyrchir gan y weithdrefn sine wrth werthuso (sine a)?

1.2.4Esbonyddu

Ystyriwch y broblem o gyfrifiannu pŵer rhif penodol. Hoffem weithdrefn sy'n cymryd bôn $b$ ac esbonydd cyfanrif positif $n$ yn argiau ac yn cyfrifiannu $b^n$. Un ffordd o wneud hyn yw drwy'r diffiniad dychweliadol $$\begin{array}{l}{b}^n=b\cdot <!--\; \cdot \; -->b^{n-<!--\; -\; -->1},\\ b^0=1,\end{array}$$ sy'n trosi'n rhwydd yn weithdrefn

(define (expt b n)
  (if (= n 0) 
      1 
      (* b (expt b (- n 1)))))

Proses ddychweliadol linol yw hon, sy'n gofyn am $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ o gamau a gofod $\mathrm{\Theta <!--\; \Theta \; -->}(n)$. Yn union fel gyda ffactorial, gallwn lunio iteriad llinol cyfatebol yn rhwydd:

(define (expt b n) 
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))

Mae angen $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ o gamau a gofod $\mathrm{\Theta <!--\; \Theta \; -->}(1)$ ar y fersiwn hon.

Gallwn gyfrifiannu pwerau mewn llai o gamau drwy sgwario'n olynol. Er enghraifft, yn hytrach na chyfrifiannu $b^8$ fel $$b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->(b\cdot <!--\; \cdot \; -->b)))))),$$ gallwn ei gyfrifiannu gan ddefnyddio tri lluosiad: $$\begin{array}{l}{b}^2=b\cdot <!--\; \cdot \; -->b,\\ b^4=b^2\cdot <!--\; \cdot \; -->b^2,\\ b^8=b^4\cdot <!--\; \cdot \; -->b^4.\end{array}$$ Mae'r dull hwn yn gweithio'n iawn ar gyfer esbonyddion sy'n bwerau 2. Gallwn hefyd fanteisio ar sgwario olynol wrth gyfrifiannu pwerau yn gyffredinol os defnyddiwn y rheol $$\begin{array}{ll}{b}^n=(b^{n/2}{)}^2& \text{os yw}n\text{yn eilrif},\\ b^n=b\cdot <!--\; \cdot \; -->b^{n-<!--\; -\; -->1}& \text{os yw}n\text{yn odrif}.\end{array}$$ Gallwn fynegi'r dull hwn fel gweithdrefn:

(define (fast-expt b n)
  (cond ((= n 0) 
         1)
        ((even? n) 
         (square (fast-expt b (/ n 2))))
        (else 
         (* b (fast-expt b (- n 1))))))

lle diffinnir y traethiad i brofi a yw cyfanrif yn eilrif yn nhermau'r weithdrefn gyntefig remainder gan

(define (even? n)
  (= (remainder n 2) 0))

Mae'r broses a gynhyrchir gan fast-expt yn tyfu'n logarithmig ag $n$ o ran gofod a nifer y camau. I weld hyn, sylwch mai dim ond un lluosiad yn fwy na chyfrifiannu $b^n$ sydd ei angen i gyfrifiannu $b^{2n}$ gan ddefnyddio fast-expt. Felly mae maint yr esbonydd y gallwn ei gyfrifiannu yn dyblu (yn fras) gyda phob lluosiad newydd a ganiateir inni. Felly, mae nifer y lluosiadau sydd eu hangen ar gyfer esbonydd o $n$ yn tyfu tua'r un mor gyflym â logarithm $n$ i'r bôn 2. Mae gan y broses dwf $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$.³⁷

Daw'r gwahaniaeth rhwng twf $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ a thwf $\mathrm{\Theta <!--\; \Theta \; -->}(n)$ yn drawiadol wrth i $n$ fynd yn fawr. Er enghraifft, dim ond 14 lluosiad sydd eu hangen ar fast-expt ar gyfer $n$ = 1000.³⁸ Mae hefyd yn bosibl defnyddio'r syniad o sgwario olynol i ddyfeisio algorithm iteru sy'n cyfrifiannu pwerau â nifer logarithmig o gamau (gweler Ymarfer 1.16), er nad yw'n cael ei ysgrifennu mor uniongyrchol â'r algorithm dychweliadol, fel sy'n digwydd yn aml gydag algorithmau iteru.³⁹

Ymarfer 1.16: Dyluniwch weithdrefn sy'n cynhyrchu proses esbonyddu drwy iteru, sy'n defnyddio sgwario olynol a nifer logarithmig o gamau, fel fast-expt. (Awgrym: gan ddefnyddio'r sylw fod $(b^{n/2}{)}^2=(b^2{)}^{n/2}$, cadwch, ynghyd â'r esbonydd $n$ a'r bôn $b$, newidyn cyflwr ychwanegol $a$, a diffiniwch y trawsffurfiad cyflwr fel nad yw'r lluoswm $a{b}^n$ yn newid o gyflwr i gyflwr. Ar ddechrau'r broses cymerir mai 1 yw $a$, a rhoddir yr ateb gan werth $a$ ar ddiwedd y broses. Yn gyffredinol, mae'r dechneg o ddiffinio maint annewidiol sy'n aros yr un fath o gyflwr i gyflwr yn ffordd bwerus o feddwl am ddylunio algorithmau iteru.)

Ymarfer 1.17: Mae'r algorithmau esbonyddu yn yr adran hon yn seiliedig ar gyflawni esbonyddu drwy luosi dro ar ôl tro. Mewn ffordd debyg, gellir lluosi cyfanrifau drwy adio dro ar ôl tro. Mae'r weithdrefn luosi ganlynol (lle tybir mai dim ond adio, ac nid lluosi, y gall ein hiaith ei wneud) yn cyfateb i'r weithdrefn expt:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

Mae'r algorithm hwn yn cymryd nifer o gamau sy'n llinol ag b. Nawr tybiwch ein bod yn cynnwys, ynghyd ag adio, y gweithrediadau double, sy'n dyblu cyfanrif, a halve, sy'n rhannu cyfanrif (eilrif) â 2. Gan ddefnyddio'r rhain, dyluniwch weithdrefn luosi sy'n cyfateb i fast-expt ac sy'n defnyddio nifer logarithmig o gamau.

Ymarfer 1.18: Gan ddefnyddio canlyniadau Ymarfer 1.16 ac Ymarfer 1.17, dyfeisiwch weithdrefn sy'n cynhyrchu proses iteru ar gyfer lluosi dau gyfanrif yn nhermau adio, dyblu, a haneru, ac sy'n defnyddio nifer logarithmig o gamau.⁴⁰

Ymarfer 1.19: Mae algorithm clyfar ar gyfer cyfrifiannu rhifau Fibonacci mewn nifer logarithmig o gamau. Cofiwch drawsffurfiad y newidynnau cyflwr $a$ a $b$ ym mhroses fib-iter 1.2.2: $a\leftarrow <!--\; \leftarrow \; -->a+b$ a $b\leftarrow <!--\; \leftarrow \; -->a$. Galwch y trawsffurfiad hwn yn $T$, a sylwch fod cymhwyso $T$ dro ar ôl tro $n$ gwaith, gan ddechrau ag 1 a 0, yn cynhyrchu'r pâr $\text{Fib}(n+1)$ a $\text{Fib}(n)$. Mewn geiriau eraill, cynhyrchir rhifau Fibonacci drwy gymhwyso $T^n$, sef pŵer $n^{\text{fed}}$ y trawsffurfiad $T$, gan ddechrau â'r pâr (1, 0). Nawr ystyriwch $T$ yn achos arbennig $p=0$ ac $q=1$ mewn teulu o drawsffurfiadau $T_{pq}$, lle mae $T_{pq}$ yn trawsffurfio'r pâr $(a,b)$ yn ôl $a\leftarrow <!--\; \leftarrow \; -->bq+aq+ap$ a $b\leftarrow <!--\; \leftarrow \; -->bp+aq$. Dangoswch, os cymhwyswn drawsffurfiad o'r fath $T_{pq}$ ddwywaith, fod yr effaith yr un fath â defnyddio un trawsffurfiad $T_{p^{\prime }{q}^{\prime }}$ o'r un ffurf, a chyfrifiannwch $p^{\prime }$ a $q^{\prime }$ yn nhermau $p$ a $q$. Mae hyn yn rhoi ffordd benodol inni sgwario'r trawsffurfiadau hyn, ac felly gallwn gyfrifiannu $T^n$ drwy sgwario olynol, fel yn y weithdrefn fast-expt. Rhowch hyn i gyd at ei gilydd i gwblhau'r weithdrefn ganlynol, sy'n rhedeg mewn nifer logarithmig o gamau:⁴¹

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
  (cond ((= count 0) 
         b)
        ((even? count)
         (fib-iter a
                   b
                   ⟨??⟩  ;compute p'
                   ⟨??⟩  ;compute q'
                   (/ count 2)))
        (else 
         (fib-iter (+ (* b q) 
                      (* a q) 
                      (* a p))
                   (+ (* b p) 
                      (* a q))
                   p
                   q
                   (- count 1)))))

1.2.5Rhannwyr Cyffredin Mwyaf

Diffinnir rhannwr cyffredin mwyaf (GCD) dau gyfanrif $a$ a $b$ fel y cyfanrif mwyaf sy'n rhannu $a$ ac $b$ heb weddill. Er enghraifft, GCD 16 a 28 yw 4. Ym Mhennod 2, pan ymchwiliwn i sut i weithredu rhifyddeg rhifau cymarebol, bydd angen inni allu cyfrifiannu GCD i leihau rhifau cymarebol i'w ffurf symlaf. (I leihau rhif cymarebol i'w ffurf symlaf, rhaid rhannu'r rhifiadur a'r enwadur â'u GCD. Er enghraifft, mae 16/28 yn lleihau i 4/7.) Un ffordd o ganfod GCD dau gyfanrif yw eu ffactorio a chwilio am ffactorau cyffredin, ond ceir algorithm enwog sy'n llawer mwy effeithlon.

Mae syniad yr algorithm yn seiliedig ar y sylw, os mai $r$ yw'r gweddill pan rennir $a$ ag $b$, fod rhannwyr cyffredin $a$ ac $b$ yn union yr un fath â rhannwyr cyffredin $b$ ac $r$. Felly, gallwn ddefnyddio'r hafaliad

GCD(a,b) = GCD(b,r)

i leihau'r broblem o gyfrifiannu GCD yn olynol i'r broblem o gyfrifiannu GCD parau llai a llai o gyfanrifau. Er enghraifft, mae

GCD(206,40) = GCD(40,6)
            = GCD(6,4)
            = GCD(4,2)
            = GCD(2,0) = 2

yn lleihau GCD(206, 40) i GCD(2, 0), sef 2. Gellir dangos y bydd dechrau ag unrhyw ddau gyfanrif positif a lleihau dro ar ôl tro bob amser yn cynhyrchu, yn y pen draw, bâr lle mae'r ail rif yn 0. Yna'r rhif arall yn y pâr yw'r GCD. Gelwir y dull hwn o gyfrifiannu'r GCD yn Algorithm Euclid.⁴²

Mae'n hawdd mynegi Algorithm Euclid fel gweithdrefn:

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

Mae hyn yn cynhyrchu proses iteru y mae nifer ei chamau'n tyfu fel logarithm y rhifau dan sylw.

Mae perthynas ddiddorol rhwng y ffaith fod gan nifer y camau sydd eu hangen ar Algorithm Euclid dwf logarithmig a rhifau Fibonacci:

Theorem Lamé: Os oes angen $k$ o gamau ar Algorithm Euclid i gyfrifiannu GCD rhyw bâr, yna rhaid i'r rhif lleiaf yn y pâr fod yn fwy na neu'n hafal i rif Fibonacci rhif $k^{\text{fed}}$.⁴³

Gallwn ddefnyddio'r theorem hon i gael amcangyfrif o drefn twf Algorithm Euclid. Gadewch i $n$ fod y lleiaf o ddau fewnbwn y weithdrefn. Os yw'r broses yn cymryd $k$ o gamau, yna rhaid bod $n\ge <!--\; \ge \; -->\text{Fib}(k)\approx <!--\; \approx \; -->{\mathrm{\phi <!--\; \phi \; -->}}^k/\sqrt{5}$. Felly mae nifer y camau $k$ yn tyfu fel logarithm (i'r bôn $\mathrm{\phi <!--\; \phi \; -->}$) $n$. Felly, y drefn twf yw $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$.

Ymarfer 1.20: Mae'r broses a gynhyrchir gan weithdrefn, wrth gwrs, yn dibynnu ar y rheolau a ddefnyddir gan y dehonglydd. Er enghraifft, ystyriwch y weithdrefn iteru gcd a roddwyd uchod. Tybiwch ein bod yn dehongli'r weithdrefn hon drwy werthuso yn y drefn arferol, fel y trafodwyd yn 1.1.5. (Disgrifir rheol gwerthuso yn y drefn arferol ar gyfer if yn Ymarfer 1.5.) Gan ddefnyddio'r dull amnewid (ar gyfer y drefn arferol), dangoswch y broses a gynhyrchir wrth werthuso (gcd 206 40) a nodwch y gweithrediadau remainder a gyflawnir mewn gwirionedd. Sawl gweithrediad remainder a gyflawnir mewn gwirionedd wrth werthuso (gcd 206 40) yn y drefn arferol? Ac wrth werthuso yn y drefn gymhwysol?

1.2.6Enghraifft: Profi a yw Rhif yn Gysefin

Mae'r adran hon yn disgrifio dau ddull ar gyfer gwirio a yw cyfanrif $n$ yn gysefin, un â threfn twf $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$, ac algorithm “tebygolrwydd” â threfn twf $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$. Mae'r ymarferion ar ddiwedd yr adran hon yn awgrymu prosiectau rhaglennu sy'n seiliedig ar yr algorithmau hyn.

Chwilio am rannwyr

Ers yr hen oesoedd, mae problemau ynghylch rhifau cysefin wedi swyno mathemategwyr, ac mae llawer o bobl wedi gweithio ar y broblem o bennu ffyrdd o brofi a yw rhifau'n gysefin. Un ffordd o brofi a yw rhif yn gysefin yw canfod rhannwyr y rhif. Mae'r rhaglen ganlynol yn canfod rhannwr cyfanrif lleiaf (mwy nag 1) rhif penodol $n$. Mae'n gwneud hyn mewn ffordd uniongyrchol, drwy brofi a yw $n$ yn rhanadwy â chyfanrifau olynol gan ddechrau â 2.

(define (smallest-divisor n)
  (find-divisor n 2))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) 
         n)
        ((divides? test-divisor n) 
         test-divisor)
        (else (find-divisor 
               n 
               (+ test-divisor 1)))))

(define (divides? a b)
  (= (remainder b a) 0))

Gallwn brofi a yw rhif yn gysefin fel a ganlyn: mae $n$ yn gysefin os a dim ond os mai $n$ yw ei rannydd lleiaf ei hun.

(define (prime? n)
  (= n (smallest-divisor n)))

Mae'r prawf terfynu ar gyfer find-divisor yn seiliedig ar y ffaith, os nad yw $n$ yn gysefin, fod yn rhaid iddo gael rhannydd sy'n llai na neu'n hafal i $\sqrt{n}$.⁴⁴ Mae hyn yn golygu mai dim ond rhannwyr rhwng 1 ac $\sqrt{n}$ y mae angen i'r algorithm eu profi. O ganlyniad, bydd gan nifer y camau sydd eu hangen i adnabod $n$ yn gysefin drefn twf $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$.

Prawf Fermat

Mae'r prawf cysefinrwydd $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ yn seiliedig ar ganlyniad o ddamcaniaeth rhifau a elwir yn Theorem Fach Fermat.⁴⁵

Theorem Fach Fermat: Os yw $n$ yn rhif cysefin ac os yw $a$ yn unrhyw gyfanrif positif sy'n llai nag $n$, yna mae $a$ wedi'i godi i'r pŵer $n^{\text{fed}}$ yn gyfath ag $a$ modwlo $n$.

(Dywedir bod dau rif yn gyfath modwlo $n$ os oes gan y ddau yr un gweddill wrth eu rhannu ag $n$. Cyfeirir hefyd at weddill rhif $a$ wrth ei rannu ag $n$ fel gweddill $a$ modwlo $n$, neu'n syml fel $a$ modwlo $n$.)

Os nad yw $n$ yn gysefin, yna, yn gyffredinol, ni fydd y rhan fwyaf o'r rhifau $a<n$ yn bodloni'r berthynas uchod. Mae hyn yn arwain at yr algorithm canlynol ar gyfer profi cysefinrwydd: o gael rhif $n$, dewiswch rif ar hap $a<n$ a chyfrifiannwch weddill $a^n$ modwlo $n$. Os nad yw'r canlyniad yn hafal i $a$, yna yn sicr nid yw $n$ yn gysefin. Os yw'n $a$, yna mae'n bur debygol fod $n$ yn gysefin. Nawr dewiswch rif arall ar hap $a$ a'i brofi drwy'r un dull. Os yw hwn hefyd yn bodloni'r hafaliad, yna gallwn fod yn fwy hyderus fyth fod $n$ yn gysefin. Drwy roi cynnig ar ragor a rhagor o werthoedd $a$, gallwn gynyddu ein hyder yn y canlyniad. Gelwir yr algorithm hwn yn brawf Fermat.

I weithredu prawf Fermat, mae angen gweithdrefn sy'n cyfrifiannu pŵer rhif modwlo rhif arall:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder 
          (square (expmod base (/ exp 2) m))
          m))
        (else
         (remainder 
          (* base (expmod base (- exp 1) m))
          m))))

Mae hyn yn debyg iawn i weithdrefn fast-expt 1.2.4. Mae'n defnyddio sgwario olynol, fel bod nifer y camau'n tyfu'n logarithmig gyda'r esbonydd.⁴⁶

Cyflawnir prawf Fermat drwy ddewis ar hap rif $a$ rhwng 1 ac $n-<!--\; -\; -->1$, gan gynnwys y ddau ben, a gwirio a yw'r gweddill modwlo $n$ o bŵer $n^{\text{fed}}$ rhif $a$ yn hafal i $a$. Dewisir y rhif ar hap $a$ gan ddefnyddio'r weithdrefn random, y tybiwn ei bod wedi'i chynnwys yn Scheme fel gweithdrefn gyntefig. Mae Random yn dychwelyd cyfanrif annegyddol sy'n llai na'i mewnbwn cyfanrif. Felly, i gael rhif ar hap rhwng 1 ac $n-<!--\; -\; -->1$, galwn random â mewnbwn o $n-<!--\; -\; -->1$ ac ychwanegwn 1 at y canlyniad:

(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random (- n 1)))))

Mae'r weithdrefn ganlynol yn rhedeg y prawf nifer penodol o weithiau, fel y pennir gan baramedr. Mae ei gwerth yn wir os yw'r prawf yn llwyddo bob tro, ac yn anwir fel arall.

(define (fast-prime? n times)
  (cond ((= times 0) true)
        ((fermat-test n) 
         (fast-prime? n (- times 1)))
        (else false)))

Dulliau tebygolrwyddol

Mae prawf Fermat yn wahanol ei natur i'r rhan fwyaf o algorithmau cyfarwydd, lle cyfrifiannir ateb y gwarentir ei fod yn gywir. Yma, dim ond yn debygol o fod yn gywir y mae'r ateb a geir. Yn fwy manwl, os bydd $n$ byth yn methu prawf Fermat, gallwn fod yn sicr nad yw $n$ yn gysefin. Ond nid yw'r ffaith fod $n$ yn pasio'r prawf, er ei bod yn arwydd eithriadol o gryf, yn warant fod $n$ yn gysefin. Yr hyn yr hoffem ei ddweud yw y gellir gwneud tebygolrwydd gwall yn ein prawf cysefinrwydd mor fach ag y dymunwn os, ar gyfer unrhyw rif $n$, cyflawnwn y prawf ddigon o weithiau a chanfod bod $n$ bob amser yn ei basio.

Yn anffodus, nid yw'r haeriad hwn yn hollol gywir. Mae rhifau sy'n twyllo prawf Fermat yn bodoli: rhifau $n$ nad ydynt yn gysefin ond sydd eto â'r briodwedd fod $a^n$ yn gyfath ag $a$ modwlo $n$ ar gyfer pob cyfanrif $a<n$. Mae rhifau o'r fath yn hynod brin, felly mae prawf Fermat yn eithaf dibynadwy yn ymarferol.⁴⁷

Mae amrywiadau ar brawf Fermat na ellir eu twyllo. Yn y profion hyn, fel yn null Fermat, profir cysefinrwydd cyfanrif $n$ drwy ddewis cyfanrif ar hap $a<n$ a gwirio rhyw amod sy'n dibynnu ar $n$ ac $a$. (Gweler Ymarfer 1.28 am enghraifft o brawf o'r fath.) Ar y llaw arall, yn wahanol i brawf Fermat, gellir profi, ar gyfer unrhyw $n$, nad yw'r amod yn dal ar gyfer y rhan fwyaf o'r cyfanrifau $a<n$ oni bai fod $n$ yn gysefin. Felly, os yw $n$ yn pasio'r prawf ar gyfer rhyw ddewis ar hap o $a$, mae'r tebygolrwydd fod $n$ yn gysefin yn fwy na hanner. Os yw $n$ yn pasio'r prawf ar gyfer dau ddewis ar hap o $a$, mae'r tebygolrwydd fod $n$ yn gysefin yn fwy na 3 o bob 4. Drwy redeg y prawf â rhagor a rhagor o werthoedd $a$ a ddewisir ar hap, gallwn wneud tebygolrwydd gwall mor fach ag y dymunwn.

Mae bodolaeth profion y gellir profi bod eu tebygolrwydd o wall yn mynd mor fach ag y mynnir wedi ennyn diddordeb mewn algorithmau o'r math hwn, a elwir bellach yn algorithmau tebygolrwydd. Mae llawer iawn o waith ymchwil yn y maes hwn, a chymhwyswyd algorithmau tebygolrwydd yn llwyddiannus i lawer o feysydd.⁴⁸

Ymarfer 1.21: Defnyddiwch y weithdrefn smallest-divisor i ganfod rhannydd lleiaf pob un o'r rhifau canlynol: 199, 1999, 19999.

Ymarfer 1.22: Mae'r rhan fwyaf o weithrediadau Lisp yn cynnwys gweithdrefn gyntefig o'r enw runtime sy'n dychwelyd cyfanrif sy'n pennu faint o amser y mae'r system wedi bod yn rhedeg (wedi'i fesur, er enghraifft, mewn microeiliadau). Pan elwir y weithdrefn timed-prime-test ganlynol â chyfanrif $n$, mae'n argraffu $n$ ac yn gwirio a yw $n$ yn gysefin. Os yw $n$ yn gysefin, mae'r weithdrefn yn argraffu tair seren ac yna faint o amser a ddefnyddiwyd i gyflawni'r prawf.

(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) 
                       start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elapsed-time))

Gan ddefnyddio'r weithdrefn hon, ysgrifennwch weithdrefn search-for-primes sy'n gwirio cysefinrwydd odrifau olynol mewn amrediad penodol. Defnyddiwch eich gweithdrefn i ganfod y tri rhif cysefin lleiaf sy'n fwy na 1000; yn fwy na 10,000; yn fwy na 100,000; ac yn fwy na 1,000,000. Nodwch yr amser sydd ei angen i brofi pob rhif cysefin. Gan fod gan yr algorithm profi drefn twf $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$, dylech ddisgwyl i brofi rhifau cysefin o gwmpas 10,000 gymryd tua $\sqrt{10}$ gwaith cymaint o amser â phrofi rhifau cysefin o gwmpas 1000. A yw eich data amseru yn cadarnhau hyn? Pa mor dda y mae'r data ar gyfer 100,000 a 1,000,000 yn cefnogi'r rhagfynegiad $\mathrm{\Theta <!--\; \Theta \; -->}(\sqrt{n})$? A yw eich canlyniad yn gyson â'r syniad fod rhaglenni ar eich peiriant yn rhedeg mewn amser sy'n gyfrannol â nifer y camau sydd eu hangen ar y cyfrifiad?

Ymarfer 1.23: Mae'r weithdrefn smallest-divisor a ddangoswyd ar ddechrau'r adran hon yn gwneud llawer o brofi diangen: ar ôl gwirio a yw'r rhif yn rhanadwy â 2, nid oes diben gwirio a yw'n rhanadwy ag unrhyw eilrifau mwy. Mae hyn yn awgrymu na ddylai'r gwerthoedd a ddefnyddir ar gyfer test-divisor fod yn 2, 3, 4, 5, 6, …, ond yn hytrach yn 2, 3, 5, 7, 9, …. I weithredu'r newid hwn, diffiniwch weithdrefn next sy'n dychwelyd 3 os yw ei mewnbwn yn hafal i 2, ac sydd fel arall yn dychwelyd ei mewnbwn ynghyd â 2. Addaswch y weithdrefn smallest-divisor i ddefnyddio (next test-divisor) yn lle (+ test-divisor 1). Gyda timed-prime-test yn cynnwys y fersiwn addasedig hon o smallest-divisor, rhedwch y prawf ar gyfer pob un o'r 12 rhif cysefin a ganfuwyd yn Ymarfer 1.22. Gan fod yr addasiad hwn yn haneru nifer y camau profi, dylech ddisgwyl iddo redeg tua dwywaith mor gyflym. A gadarnheir y disgwyliad hwn? Os na, beth yw'r gymhareb a welir rhwng cyflymderau'r ddau algorithm, a sut rydych yn egluro'r ffaith ei bod yn wahanol i 2?

Ymarfer 1.24: Addaswch weithdrefn timed-prime-test Ymarfer 1.22 i ddefnyddio fast-prime? (dull Fermat), a phrofwch bob un o'r 12 rhif cysefin a ganfuwyd gennych yn yr ymarfer hwnnw. Gan fod gan brawf Fermat dwf $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$, sut y byddech yn disgwyl i'r amser i brofi rhifau cysefin ger 1,000,000 gymharu â'r amser sydd ei angen i brofi rhifau cysefin ger 1000? A yw eich data'n cadarnhau hyn? A allwch egluro unrhyw anghysondeb a ganfyddwch?

Ymarfer 1.25: Mae Alyssa P. Hacker yn cwyno inni wneud llawer o waith ychwanegol wrth ysgrifennu expmod. Wedi'r cyfan, meddai, gan ein bod eisoes yn gwybod sut i gyfrifiannu pwerau, gallem fod wedi ysgrifennu'n syml

(define (expmod base exp m)
  (remainder (fast-expt base exp) m))

A yw hi'n gywir? A fyddai'r weithdrefn hon yr un mor addas ar gyfer ein prawf cysefinrwydd cyflym? Eglurwch.

Ymarfer 1.26: Mae Louis Reasoner yn cael cryn anhawster wrth wneud Ymarfer 1.24. Mae ei brawf fast-prime? i'w weld yn rhedeg yn arafach na'i brawf prime?. Mae Louis yn galw ei ffrind Eva Lu Ator draw i helpu. Wrth archwilio cod Louis, maent yn canfod ei fod wedi ailysgrifennu'r weithdrefn expmod i ddefnyddio lluosiad penodol, yn hytrach na galw square:

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder 
          (* (expmod base (/ exp 2) m)
             (expmod base (/ exp 2) m))
          m))
        (else
         (remainder 
          (* base 
             (expmod base (- exp 1) m))
          m))))

“Nid wyf yn gweld pa wahaniaeth y gallai hynny ei wneud,” meddai Louis. “Rwyf i'n gweld.” meddai Eva. “Drwy ysgrifennu'r weithdrefn fel yna, rwyt wedi trawsffurfio'r broses $\mathrm{\Theta <!--\; \Theta \; -->}(\log <!--\; \; -->n)$ yn broses $\mathrm{\Theta <!--\; \Theta \; -->}(n)$.” Eglurwch.

Ymarfer 1.27: Dangoswch fod y rhifau Carmichael a restrir yn Nhroednodyn 47 yn twyllo prawf Fermat mewn gwirionedd. Hynny yw, ysgrifennwch weithdrefn sy'n cymryd cyfanrif $n$ ac yn profi a yw $a^n$ yn gyfath ag $a$ modwlo $n$ ar gyfer pob $a<n$, a rhowch gynnig ar eich gweithdrefn gyda'r rhifau Carmichael a roddwyd.

Ymarfer 1.28: Gelwir un amrywiad ar brawf Fermat na ellir ei dwyllo yn brawf Miller–Rabin (Miller 1976; Rabin 1980). Mae hwn yn dechrau â ffurf amgen ar Theorem Fach Fermat, sy'n datgan, os yw $n$ yn rhif cysefin ac os yw $a$ yn unrhyw gyfanrif positif sy'n llai nag $n$, yna bod $a$ wedi'i godi i'r pŵer $(n-<!--\; -\; -->1)$ yn gyfath ag 1 modwlo $n$. I brofi cysefinrwydd rhif $n$ drwy brawf Miller–Rabin, dewiswn rif ar hap $a<n$ a chodwn $a$ i'r pŵer $(n-<!--\; -\; -->1)$ modwlo $n$ gan ddefnyddio'r weithdrefn expmod. Fodd bynnag, pryd bynnag y cyflawnwn y cam sgwario yn expmod, gwiriwn a ydym wedi darganfod “gwreiddyn sgwâr o 1 nad yw’n ddibwys modwlo $n$,” hynny yw, rhif nad yw'n hafal i 1 nac $n-<!--\; -\; -->1$ y mae ei sgwâr yn hafal i 1 modwlo $n$. Gellir profi, os oes gwreiddyn sgwâr o 1 nad yw’n ddibwys o'r fath yn bodoli, nad yw $n$ yn gysefin. Gellir hefyd brofi, os yw $n$ yn odrif nad yw'n gysefin, yna, ar gyfer o leiaf hanner y rhifau $a<n$, y bydd cyfrifiannu $a^{n-<!--\; -\; -->1}$ fel hyn yn datgelu gwreiddyn sgwâr o 1 nad yw’n ddibwys modwlo $n$. (Dyma pam na ellir twyllo prawf Miller–Rabin.) Addaswch y weithdrefn expmod i roi signal os yw'n darganfod gwreiddyn sgwâr o 1 nad yw’n ddibwys, a defnyddiwch hyn i weithredu prawf Miller–Rabin gyda gweithdrefn sy'n cyfateb i fermat-test. Gwiriwch eich gweithdrefn drwy brofi amrywiol rifau y gwyddys eu bod yn gysefin neu'n anghysefin. Awgrym: un ffordd gyfleus o wneud i expmod roi signal yw gwneud iddi ddychwelyd 0.

(define (factorial n)
  (define (iter product counter)
    (if (> counter n)
        product
        (iter (* counter product)
              (+ counter 1))))
  (iter 1 1))