Највећи заједнички делилац¶

Алгоритам смањивања за по 1¶

Једно, алгоритамски веома лоше решење, било би да редом испробавамо природне бројеве почевши од \(min(a, b)\) наниже као могуће НЗД, док не наиђемо на број који је делилац и од \(a\) и од \(b\). Први заједнички делилац на који наиђемо је уједно и највећи број са том особином, па је то НЗД.

У графичкој илустрацији алгоритма која следи, свака слика одговара једној итерацији алгоритма. Квадрат се смањује све док се и ширина и висина правоугаоника не уклопе у мрежу квадрата.

Опишите један посебно неповољан улаз за алгоритам смањивања за по 1, тј. вредности \(a\) и \(b\) за које је алгоритму потребан посебно велики број операција.

Можете ли да процените време рада алгоритма у случају неповољних 64-битних вредности (тј. вредности типа long)?

Није тешко приметити да је за алгоритам смањивања за по 1 (у смислу броја потребних операција) неповољно када су вредности \(a\) и \(b\) веома велике и међусобно блиске, јер је тада вредност НЗД сразмерно веома мала. Екстреман пример би био \(a=2^{63}-1, b=2^{63}-2\). У овом случају једини заједнички делилац бројева \(a\) и \(b\) је један (зашто?), тј. ови бројеви су узајамно прости. Због тога је број операција потребних да се на описани начин дође до резултата реда \(2^{63} \approx 10^{19}\), а за то је, као што већ знамо, данашњим рачунарима потребно више стотина година.

Алгоритам истовремене факторизације¶

Поступак који се учи у основној школи је да се дати бројеви раставе на просте чиниоце, а затим се у факторизацијама датих бројева пронађу прости чиниоци који су заједнички. Производ тих заједничких простих чинилаца је тражени НЗД. На пример, \(60 = 2 \cdot 2 \cdot 3 \cdot 5, 42 = 2 \cdot 3 \cdot 7\), заједнички прости чиниоци су 2 и 3, па је НЗД једнак \(2 \cdot 3 = 6\). Уобичајено је да се бројеви чији НЗД тражимо факторишу истовремено, користећи запис као на следећој слици. Са десне стране црте пишемо све чиниоце којима је дељив бар један од бројева са леве стране, а оне са којим су дељива оба броја посебно означимо и на крају помножимо.

Поступак налажења НЗД факторизацијом два броја (заједнички фактори су заокружени).¶

Из поступка факторизације знамо да потенцијалне просте делиоце \(d\) броја \(a\) треба да тражимо све док је \(d \leq \sqrt a\), а делиоце броја \(b\) док је \(d \leq \sqrt b\). Пошто се делиоци оба броја налазе истовремено, услов за останак у петљи је да за бар један од бројева \(a, b\) претрага није завршена. Овај услов може формално да се искаже на неколико логички равноправних начина, нпр:

Ево и програма за поступак одређивања НЗД истовременом факторизацијом:

Које вредности су посебно неповољне за алгоритам налажења НЗД помоћу факторизације?

Колико операција, односно времена може у најнеповољнијем случају да буде потребно овом алгоритму за вредности из опсега типа long?

Алгоритам налажења НЗД помоћу факторизације је веома сличан поступку факторизације, тј. растављања једног датог броја на просте чиниоце. Због тога је и број операција, као и код алгоритма факторизације, у најгорем случају сразмеран корену из већег од бројева \(a, b\). Као што смо раније видели, неповољан случај су велики прости бројеви, а за такве бројеве може да буде потребно око \(2^{30}\) операција, тј. неколико секунди.

Еуклидов алгоритам¶

Еуклидов алгоритам се заснива на једноставној идеји, познатој од давнина. Да бисмо ту идеју представили на што јаснији начин, вратимо се графичкој интерпретацији проблема, у којој је потребно да се правоугаоник прекрије што већим (међусобно једнаким) квадратима странице \(d\). Нека су \(a\) и \(b\) странице правоугаоника и нека је \(a \geq b\). Пошто квадрат странице \(d\) треба да прекрије правоугаоник, његова страница се цео број пута садржи у страници \(b\). Самим тим, мада још не знамо колико је \(d\), знамо да ћемо квадратима величине \(d \cdot d\) лако покрити квадрат величине \(b \cdot b\). Зато од полазног правоугаоника можемо да одбацимо квадрат величине \(b \cdot b\) и наставимо да тражимо највећи квадрат којим може да се покрије преостали правоугаоник величине \((a-b) \cdot b\).

Ово размишљање можемо да понављамо све док преостали правоугаоник не постане квадрат, када је одговор очигледан. Описани поступак овако изгледа на примеру \(a=60, b= 42\):

Исту идеју можемо да искажемо и формално. Нека је \(d\) заједнички делилац бројева \(a, b\), тј. нека је \(a=m \cdot d, b=n \cdot d\). Без губљења општости можемо да претпоставимо \(a \geq b\). Тада је \(d\) делилац и броја \(a-b\) јер \(a-b = (m-n) \cdot d\). Важи и обрнуто, ако је \(d\) заједнички делилац бројева \(a-b\) и \(b\), онда је \(d\) делилац и броја \(a\). Одавде закључујемо да је скуп заједничких делилаца бројева \(a\) и \(b\) исти као и скуп заједничких делилаца бројева \(a-b\) и \(b\). Два иста скупа имају и исти максимум, што значи да је \(nzd(a, b) = nzd(a-b, b)\).

Овим је оправдан приступ који се користи у Еуклидовом поступку за одређивање НЗД, тј. ово је суштина доказа да је поступак коректан. Запишимо поступак и помоћу програма:

Пре него што пређемо на анализу, уочимо да поступак може додатно да се оптимизује тако што узастопна одузимања \(b\) од \(a\) заменимо рачунањем остатка при дељењу. На пример, од правоугаоника величине \(18 \times 42\), одузимањем \(42-18=24\) прелазимо на правоугаоник \(18 \times 24\), а затим одузимањем \(24-18=6\) на правоугаоник \(18 \times 6\). Када од неког броја \(p \in \mathbb{N}\) узастопно одузимамо број \(q \in \mathbb{N}\) док год је \(p \geq q\), на крају као резултат добијамо остатак при дељењу \(p\) са \(q\). Према томе, претходно описани поступак можемо још да побољшамо (убрзамо), тако што уместо \((a-b)\) користимо \((a \bmod b)\). Након ове поправке, кораци поступка изгледају овако:

Ово може да буде значајна уштеда када је један од бројева \(a, b\) веома велики, а други веома мали.

Ево и програма за оптимизовану верзију Еуклидовог алгоритма, који уместо одузимања користи остатак при дељењу:

Покушајте да пронађете вредности \(a\) и \(b\), за које би Еуклидовом алгоритму био потребан што већи број итерација. Да бисте дошли до таквог пара бројева, предлажемо вам да кренете од вредности за \(a\) и \(b\) у последњој итерацији, затим у претпоследњој итд. ка почетним вредностима. Наравно, број итерација које на овај начин можемо да извршимо уназад, ограничен је опсегом 64-битних променљивих које користимо у овим алгоритмима.

Пошто желимо да максимизирамо број итерација, најбоље је да почнемо од најмањег могућег завршног пара вредности, а то је \(a=1, b=1\). Да бисмо у датом опсегу могли да изведемо што већи број итерација уназад, вредности \(a\) и \(b\) ћемо повећавати штедљиво, тј. тако да ове вредности што спорије расту у свакој од итерација. Према томе, тражимо прво најмањи пар бројева који у једној итерацији доводи до пара \(a=1, b=1\), а то је пар \(a=2, b=1\). Да бисмо направили следећи корак уназад, потребан нам је што мањи број \(a\), који при дељењу са 2 даје остатак 1, а то је 3. Тако добијамо претходни пар \(a=3, b=2\). Настављајући поступак, добијамо следеће парове:

a = 1, b = 1 -> 0 iteracija
a = 2, b = 1 -> 1 iteracija
a = 3, b = 2 -> 2 iteracije
a = 5, b = 3 -> 3 iteracije
a = 8, b = 5 -> 4 iteracije
a = 13, b = 8 -> 5 iteracija
a = 21, b = 13 -> 6 iteracija
a = 34, b = 21 -> 7 iteracija
a = 55, b = 34 -> 8 iteracija
a = 89, b = 55 -> 9 iteracija
a = 144, b = 89 -> 10 iteracija
a = 233, b = 144 -> 11 iteracija
a = 377, b = 233 -> 12 iteracija
a = 610, b = 377 -> 13 iteracija
a = 987, b = 610 -> 14 iteracija
a = 1597, b = 987 -> 15 iteracija
a = 2584, b = 1597 -> 16 iteracija
a = 4181, b = 2584 -> 17 iteracija
a = 6765, b = 4181 -> 18 iteracija
a = 10946, b = 6765 -> 19 iteracija
a = 17711, b = 10946 -> 20 iteracija
a = 28657, b = 17711 -> 21 iteracija
a = 46368, b = 28657 -> 22 iteracije
a = 75025, b = 46368 -> 23 iteracije
a = 121393, b = 75025 -> 24 iteracije
a = 196418, b = 121393 -> 25 iteracija
a = 317811, b = 196418 -> 26 iteracija
a = 514229, b = 317811 -> 27 iteracija
a = 832040, b = 514229 -> 28 iteracija
a = 1346269, b = 832040 -> 29 iteracija
a = 2178309, b = 1346269 -> 30 iteracija
...
a = 259695496911122585, b = 160500643816367088 -> 83 iteracije
a = 420196140727489673, b = 259695496911122585 -> 84 iteracije
a = 679891637638612258, b = 420196140727489673 -> 85 iteracija
a = 1100087778366101931, b = 679891637638612258 -> 86 iteracija
a = 1779979416004714189, b = 1100087778366101931 -> 87 iteracija
a = 2880067194370816120, b = 1779979416004714189 -> 88 iteracija
a = 4660046610375530309, b = 2880067194370816120 -> 89 iteracija
a = 7540113804746346429, b = 4660046610375530309 -> 90 iteracija
a = 12200160415121876738, b = 7540113804746346429 -> 91 iteracija

Можда изненађујуће, видимо да после свега неколико десетина итерација долазимо до граница опсега 64-битне променљиве. Нагласимо још једном да су ово, према начину на који су добијени, парови бројева за које је Еуклидовом алгоритму потребан највећи број итерација. Прецизније речено, не постоје мањи парови бројева за које је Еуклидовом алгоритму потребан исти или већи број итерација.

Одавде следи важан закључак: за било који пар бројева из опсега 64-битног целобројног типа, Еуклидовом алгоритму је довољно стотинак итерација да дође до резултата. Према томе, Еуклидов алгоритам је далеко, далеко ефикаснији од алгоритма факторизације, коме би за просте бројеве са границе опсега 64-битног целобројног типа биле потребне милијарде итерација.

Резимирајмо закључке до којих смо дошли током анализе различитих алгоритама за одређивање НЗД:

• Налажење НЗД алгоритмом смањивања за 1 је очигледно веома споро, тако да никоме не пада на памет да овај поступак користи при ручном одређивању НЗД. Једини разлог што се он понекад виђа као програм је што се веома лако записује у облику програма. Међутим, сасвим кратка и једноставна анализа показује да је налажење НЗД овим приступом бесмислено арчење рачунарских ресурса (као и код ручног рачунања). За веће вредности аргумената, алгоритам је практично неупотребљив.

• Алгоритам истовремене факторизације два броја се ослања на од раније познат алгоритам факторизације једног броја. Тај поступак јесте најефикаснији познат начин за одређивање простих чинилаца датог броја, међутим у проблему НЗД он одређује више него што се тражи. Због тога је број операција за налажење НЗД алгоритмом истовремене факторизације ипак непотребно висок.

• Еуклидов алгоритам је толико ефикасан, да би веома брзо (у делићу секунде) нашао НЗД и за бројеве од више хиљада цифара. За остале поменуте алгоритме о томе нема ни помисли.

Рачунање најмањег заједничког садржаоца¶

Са појмом највећег заједничког делиоца, тесно је повезан појам најмањег заједничког садржаоца. Подсетимо се и њега:

Најмањи заједнички садржалац (НЗС) два природна броја је најмањи природан број који је дељив са оба дата броја без остатка.

На пример, НЗС бројева 60 и 42 је 420, јер 420 је дељив и са 60 и са 42, а при томе не постоји мањи број са овом особином.

За ефикасно израчунавање најмањег заједничког садржаоца можемо да искористимо једнакост \(nzd(a, b) \cdot nzs(a, b) = a \cdot b\). Да бисмо разумели зашто ова једнакост важи, размотримо пажљиво шта се дешава при поступку дељења простим чиниоцима, којим на папиру налазимо НЗД и НЗС.

Прости чиниоци који деле оба броја са леве стране (на слици заокружени), користе се и у рачунању НЗД и НЗС, а они који деле само један од бројева са леве стране, учествују само у производу за НЗС. Према томе, прости чиниоци који учествују два пута у производима на левој страни, учествују два пута и на десној, а они који учествују само једном на левој страни, учествују једном и на десној (само у НЗС). Према томе, производ свих простих чинилаца, при чему заокружене бројимо два пута, једнак је и са \(a \cdot b\) и са \(nzd(a, b) \cdot nzs(a, b)\), па су ова два израза међусобно једнака.

Једнакост \(nzd(a, b) \cdot nzs(a, b) = a \cdot b\) може да се докаже и формалније, посматрањем факторизација бројева \(a\) и \(b\). Нека је:

Тада је:

Сада имамо:

Захваљујући овој једнакости, можемо да искористимо Еуклидов алгоритам и за ефикасно израчунавање НЗС. Ради тога је довољно да прво израчунамо \(nzd(a, b)\), а затим НЗС добијамо из \(nzs(a, b) = a \cdot (b / nzd(a, b))\). При овом рачунању је потребно да се пази и на редослед операција. Мада је тај редослед математички гледано небитан, у програму редослед може да утиче на резултат. Погледајмо, на пример, шта се дешава за бројеве \(a=1~000~000~000~000\) и \(b=2~000~000~000~000\). Еуклидовим алгоритмом добијамо \(nzd(a, b) = 1~000~000~000~000\). Ако бисмо сада НЗС рачунали као nzs = a * b / nzd, добили бисмо погрешан резултат због прекорачења (a * b излази ван опсега 64-битне променљиве), док бисмо наредбом nzs = a * (b / nzd) добили тачан резултат. Проверите ово малим варијацијама следећег програма.