Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 105
Текст из файла (страница 105)
Хотя описание здесь было изложено в весьма зашифрованном виде, более поздние комментаторы, например Бхаскара 1 (ВЬйэсвга 1) в б веке, сформулировали правило, названное кп)гака ("куттака" или "распылитель"). (См. В. Вайа, А. 5(. ЙпйЬ, Небогу ог НиЫп Магйегпайсз 2 (1айоге: МоЫа1 Вапага Эаа, 1938), 89-116.) Справедливость алгоритма Х следует из соотиошеиий (16) и того обстгмтельства, что алгоритм идентичен алгоритму А в смысле выполнения операций с числами пз и ез. Подробное доказательство алгоритма Х приведено в разделе 1.2.1.
Гордон Г. Брэдли (Соп1оп Н. Вгаб)еу) заметил, что если исключить пю сз и гз, то можно значительно сократить процесс вычислеиий при выполиеиии алгоритма Х; значение из может быть определено впоследствии из соотношения пи~ + сиз = пз. В упр, 15 показано, что значения )иг~, )пз(, ~с~~ и ~ез! остаются в интервале, ограниченном значениями исходных чисел и и ю. 'Подобным образом может быть обобщен и алгоритм В, который вычисляет наибольший общий делитель, используя свойства чисел, представленных в двоичной системе счисления (упр. 39).
Некоторые поучительные обобщения алгоритма Х представлены в упр. 18 и 19 в разделе 4.6.1. Идеи, лежащие в основе алгоритма Евклида, можно также применить для нахождеиия ойияго целочпслеяиого решения произвольиой системы линейных уравнений с целочисленными козффициеитами. Например, пусть требуется найти все целые числа ю, я, р, з, которые удовлетворяют двум уравнениям: 10ю+ Зя+ Зу+ 8г = 1, бю — 7з — 5г = 2. т. е. 7х + 181~ + 17г = 4.
(20) Теперь, как и ранее, введем в рассмотрение новую переменную х + 21~ + 2э = гэ и исключим з из уравнения (20): 71э+ 41~ + Зэ = 4, (21) Таким же способом можно ввести еще одну новую переменную, чтобы исключить переменную э, имеющую наименьший коэффициент: 2гэ + гт + з = гз. Исключение э из уравнения (21) дает Фэ + Ф~ + Зсз = 4.
(22) Наконец, используя данное уравнение, исключим гэ. После всех этих операций остаются две независимые переменные г~ и гэ. Подставляя их вместо исходных переменных, получаем общее решение: ю = 17 — 51 — 141э, я = 20 — 51~ — 17гз (25) Р = -55+ 191~ + 451з э= -8+ Г,+ 7гэ. Другими словами, все целочисленные решения (ю, х, р, з) исходных уравнений (17) и (18) получаются из уравнений (2З) путем независимой прогонки величии 1~ и гэ через все целые значения.
Общий метод, проиллюстрированный в приведенном примере, основан на сло дующей процедуре. Найдем в системе уравнений ненулевой коэффициент с с наименьшим абсолютным значением, Предположим, что он появляется в уравнении вида схо + с~я~ + " + сьхэ = о; положим также для простоты, что с > О. Если с = 1, то воспользуемся этим уравнением для исключения переменной зо из остальных уравнений системы. Затем повторим эту же процедуру по отношению к оставшимся уравнениям системы. (Если уравнений больше не остается, то вычисления прекращаются и, по существу, получаем общее решение, выражаемое через оставшиеся переменные.) Если с > 1 и если с~ щи с = = сь шой с = О, то проверяем выполнение о щи с = 0: в противном случае целочисленных решений нет.
Затем делим обе части уравнения (24) на с и исключаем яр так же, как и в случае, когда с = 1. В итоге, если с > 1 и не все из с~ шоб с, ..., сь шоб с равны нулю, вводим новую переменную (с/с)зэ+ (с~/с)яг+ . + (сь/с)яь = г, (25) исключаем переменную хэ из других уравнений при помощи Г и заменяем исходное уравнение (24) уравнением сФ+ (с~ щи с)х~ + + (сь шоб с)хь = о. (См. (19) и (21) в рассмотренном выше примере.) Этот процесс должен завершиться, так как в результате выполнения каждого шага уменьшается либо количество урелнений системы, либо величина наименьшего ненулевого коэффициента системы. Если описанную процедуру применить к уравнению пя+ еу = 1 для различных целых чисел и и е, то, по существу, будут выполняться шаги алгоритма Х.
Рассмотренная только что процедура преобразования переменных является простым и достаточно очевидным средством решения систем линейных уравнений с целочисленными коэффициентами, но отнюдь не самым лучшим методом решения такой задачи. Имеются существенные модификации метода, но они выходят за рамки настоящей книги. 1См. Непп' СоЬеп, А Сопгэе 1п Соптригайопа1 А!яебгаус Хишбег ХЬеогу (Хен Уогй: Ярйпйег, 1993), СЬаргег 2.) Возможно использование алгоритма Евклида с Гауссовыми целыми числами и + уи', а также с некоторыми другими квадратичными числовыми полями. (См., например, А. Нцгкчгх, Асса МагЬ.
11 (1887), 187-200; Е. Ка)тоЕеп, Н. Но!1етэсЬеЬ, Магй. Сошр. 53 (1989), б97-720; А. КпорйпасЬег, Л. Кпор6пасЬет, ВУТ 31 (199Ц, 28б-292.) Вычисление с высокой точностью. Если и и е — очень большие целые числа, требующие представления с многократной точностью, то бинарный метод (алгоритм В) служит простым и достаточно эффективным методом вычисления наибольшего общего делителя этих чисел, так как в нем при вычислениях используются только операции вычитания и сдвига. Напротив, алгоритм Евклида представляется значительно менее привлекательным, так как на шаге А2 требуется разделить с многократной точностью число и на число ш Но на самом деле это не является препятствием для применения алгоритма Евклида, поскольку, как будет доказано в разделе 4.5.3, частное 1и/и) почти всегда очень мало.
Например, для случайных входных данных частное 1н/в1 будет меньше 1 000 примерно в 99.855% случаев, Поэтому (иЯ и (и шоб е) почти всегда можно найти при помощи вычислений, выполняемых с однократной точностью в сочетании ср сравнятельно простой операцией вычисления и-ее, где е — число, представленное с однократной точностью. Далее, если окажется, что и намного больше е (к примеру, в таком виде могут задаваться входные данные), трудно представить, что частное й может оказаться большим, так как алгоритм Евклида, если заменить и на и щи е, в этом случае выполняется достаточно успешно. Значительного увеличения скорости выполнения алгоритма Евклида при работе с числами высокой точности можно добиться при помощи метода, предложенного Д. Г.
Лемером (П. Н. 1,еЬшег) (АММ 45 (1938), 227-233]. Оперируя только старшими разрядами болыпих чисел, можно основную часть вычислений выполнять с однократной точностью, значительно сокращая таким образом количество операций, которые необходимо выполнять с многократной точностью. Идея заключается в экономик времени за счет выполнения "виртуальных" вычислений вместо фактических. Например, расслштрим два восьмизначных числа и = 27182818 и в = 10000000, предполагая, что имеется компьютер с четырехразрядвыми словами. Пусть и' = 2718, е' = 1001, и" = 2719, ел = 1000; тогда и'/е' и пл/ев являются приближениями к и/е, причем и'/е' < и/е ~ и"/е", Отношение и/е определяет последовательность частных, полученных в алгоритме Евклида.
Если алгоритм Евклида одновременно выполнять над значениями (и', е') и (й', в") с однократной точностью до тех пор, пока не получим различные частные, то будет нетрудно заметить, что такая же последовательность частных получится, если выполнять алгоритм над числами (и,е) с многократной точностью. Итак, посмотрим, что произойдет, когда алгоритм Евклида применить к (и', ь') и к (и", е"). и' Н О 1000 719 1 281 2 157 1 124 1 зз 3 и" 2718 1001 1001 716 716 285 285 146 146 139 139 7 2 1 2 1 1 19 2719 1000 719 281 157 124 Пять первых частных одинаковы в обоих случаях, так что они должны быть правильными. Но на шестом шаге обнаруживается, что д' ф 4", поэтому вычисления с однократной точностью прекращаются.
Тем самым мы выяснили, что если бы вычисления выполнялись с исходными числами как с числами многократной точности, то это происходило бы так. ио во ио — 2ео — ио + Зво Зио — 8ео -4ио + 11ео ео ио — 2ео -но+ Зво Зио — Зво -4ио + 11ео 7ио — 19во (28) (Следуюцгее частное находится между 3 и 19.) Независимо от количества разрядов чисел и и е до тех пор, пока выполняется (27), первые пять шагов алгоритма Евклида будут такими же, как в (28).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
