AOP_Tom2 (1021737), страница 105
Текст из файла (страница 105)
Используем новое уравнение (19) для исключения ю, тогда (18) примет внд 6(1 — Зс! — 2г) — 7х — 5г = 2 Поэтому решение имеет вид 337 40902 — 571. 24140 = 34 = Вод(40902, 24140). История алгоритма Х восходит к трактату АгуаЬЬассуа (499 г. н. э.), авторство которого принадлежит Арнабхата (АгуаЬЬаса), жившему в северной Индии.
Хотя описание здесь было изложено в весьма зашифрованном виде, более поздние комментаторы, например Бхаскара 1 (ВЬвзсага 1) в 6 веке, сформулировали правило, названное !си!Сола ("куттака" нли "распылитель"). (Сс!. В. Пагга, А. Ь'. В!пВЬ, НЫсогу о! Нспби МасЬетаскл 2 (ЕаЬоге: Мосс!ш Вапагз! Паэ, 1938), 89 — 116.] Справедливость алгоритма Х следует нз соотношений (16) н того обстоятельства, что алгоритм идентичен алгоритму А в смысле выполнения операций с числами из и из. Подробное доказательства алгоритма Х приведено в разделе 1.2.1.
Гордая Г. Брэдли (Согбен Н. Втаб!еу) заметил, что если исключить иг, ог и сг, то можно значительно сократить процесс вычислений при выполнении алгоритма Х; значение иг может быть определено впоследствии из соотношения ии! + ииг = из. В упр. 15 показано, что значения !ис(, !иг), (ис( и (ог) остаются в интервале, ограниченном значениями исходных чисел и и ш Подобным образом может быть обобщен и алгоритм В, который вычисляет наибольший общий делитель, используя свойства чисел, представленных в двоичной системе счнсленин (упр.
39). Некоторые поучительные обобщения алгоритма Х представлены в упр. 18 и 19 в разделе 4.6.1. Идеи, лежащие в основе алгоритма Евклида, можно также применить для нахождения общего целочисленного решения произвольной системы линейных уравнений с целочисленными коэффициентами. Например, пусть требуется найти все целые числа ю, х, у, г, которые удовлетворяют двум уравнениям: 10ю+ Зх+ Зу+ Вг = 1, 6со — 7х — 5г = 2. т. е. (20) 7х + 1811 + 17г = 4.
Теперь, как и ранее, введем в рассмотрение новую переменную х + 211 + 2г = Зг и исключим х из уравнения (20): 71з + 411 + Зг = 4. (21) Таким же способом можно ввести еще одну новую переменную, чтобы исключить переменную г, имеюшую наименьший коэффициент: 21 + 11 + г = зз. Исключение г из уравнения (21) дает (22) зг + зз + Ззз = 4. Наконец, используя данное уравнение, исключим зг.
После всех этих операций остаются две независимые переменные 11 и гз. Подставляя их вместо исходных переменных, получаем общее решение: ю = 17 — 511 — 14гз, х = 20 — 511 — 171з, у = — 55+ 1911 + 45зз, -8+ З + 71з. (23) (24) схв+с1хз+ +сьхг = и'; положим также для простоты, что с > О.
Если с = 1, то воспользуемся этим уравнением для исключения переменной хв из остальных уравнений системы. Затем повторим зту же процедуру по отношению к оставшимся уравнениям системы. (Если уравнений больше не.остается, то вычисления прекращаются н, по существу, получаем общее решение, выражаемое через оставшиеся переменные.) Если с > 1 и если сз шоц с = .
= сь шоб с = О, то проверяем выполнение Ншод с = О; в противном случае целочисленных решений нет. Затем делим обе части уравнения (24) на с н исключаем хв так же, как и в случае, когда с = 1. В итоге, если с > 1 и не все из с1 шоб с, ..., сг шоб с равны нулю, вводим новую переменную (с/с)хо+ (с~/с)х1+... + (сг/с)хг = 1, (2о) исключаем переменную хе из других уравнений при помощи 1 и заменяем исходное уравнение (24) уравнением сз+ (с1 пюб с)х1+ . + (сь шод с)хь = Н. (26) (См.
(19) и (21) в рассмотренном выше примере.) Другими словами, все целочисленные решения (ш, х, у, г) исходных уравнений (17) и (18) получаются из уравнений (23) путем независимой прогонки величии г1 и зз через все целые значения. Общий метод, проиллюстрированный в приведенном примере, основан иа следующей процедуре. Найдем в системе уравнений ненулевой коэффициент с с наименьшим абсолютным значением. Предположим, что он появляется в уравнении вида Этот процесс должен завершиться, так как в результате выполнения каждого шага уменьшается либо количество уравнений системы, либо величина наименьшего ненулевого коэффициента системы. Если описанную процедуру применить к уравнению из + иу = 1 для различных целых чисел и и и, то, по существу, будут выполняться шаги алгоритма Х. Рассмотренная только что процедура преобразования переменных является простым и достаточно очевидным средством решения систем линейных уравнений с целочисленными коэффициентами, но отнюдь не самым лучшим методом решения такой задачи.
Имеются существенные модификации метода, но они выходят за рамки настоящей книги. (См. Непй СоЬеп, А Саигзе !и Сошрпгаг!опа! А!яеЬга!с ЕзншЬег ТЬеогу (Кезг Уогй: Яргшйег, 1993), СЬаргег 2.) Возможно использование алгоритма Евклида с Гауссовыми целыми числами и + Еи', а также с некоторыми другими квадратичными числовыми полями. (См., например, А. Ннгнйэ, Асса МагЬ.
11 (1887), 187 — 200; Е. Кайо(еп, Н. На!1егэсЬей, МаГЬ. Сашр. 53 (1989), 697 — 720; А. КпорйпасЬег, Л. Кнор(шасЬег, НЕТ 31 (1991), 286-292.) Вычисление с высокой точностью. Если и и и — очень большие целые числа, требующие представления с многократной точностью, то бинарный метод (алгоритм В) служит простым и достаточно эффективным методом вычисления наибольшего общего делителя этих чисел, так как в нем при вычислениях используются только операции вычитания и сдвига.
Напротив, алгоритм Евклида представляется значительно менее привлекательным, так как на шаге А2 требуется разделить с многократной точностью число и на число и. Но на самом деле эта не является препятствием для применения алгоритма Евклида, поскольку, как будет доказано в разделе 4.5.3, частное (и/и) почти всегда очень малб. Например, для случайных входных данных частное (и/и) будет меньше 1 000 примерно в 99.856Я случаев. Поэтому (и/и! и (и шоб и) почти всегда можно найти при помощи вычислений, выполняемых с однократной точностью в сочетании ср сравнительно простой операцией вычисления и-ди, где г! — число, представленное с однократной точностью.
Далее, если окажется, что и намного больше и (к примеру, в таком виде могут задаваться входные данные), трудно представить, что частное 9 может оказаться большим, так как алгоритм Евклида, если заменить и на и шайи, в этом случае выполняется достаточно успешно. Значительного увеличения скорости выполнения алгоритма Евклида при работе с чнсламн высокой точности можно добиться при помощи метода, предложенного Д. Г. Лемером (П.
Н. ЕеЬшег) (АММ 45 (1938), 227 — 233). Оперируя только старшими разрядами больших чисел, можно основную часть вычислений выполнять с однократной точностью, значительно сокращая таким образом количество операций, которые необходимо выполнять с многократной точностью. Идея заключается в зкономии времени за счет выполнения "виртуальных" вычислений вместо фактических. Например, рассмотрим два восьмизначных числа и = 27182818 и и = 10000000, предполагая, что имеется компьютер с четырехразрядными словами. Пусть и' = 2718, в' = 1001, и" = 2719, ил = 1000; тогда и'/и' и и"/ги являются приближениями к и/е, причем и'/е' < и/е < и '/е .
(27) Отношение и/е определяет последовательность частных, полученных в алгоритме Евклида. Если алгоритм Евклида одновременно выполнять над значениями (и', е') и (и", е") с однократной точностью до тех пор, пока не получим различные частные, то будет нетрудно заметить, что такая же последовательность частных получится, если выполнять алгоритм над числами (и,е) с многократной точностью. Итак, посмотрим, что произойдет, когда алгоритм Евклида применить к (и', е') н к (и", е"). и е 1000 2 719 1 281 2 157 1 124 1 ЗЗ 3 и' Ф е 2718 1001 2 2719 1001 716 1 1000 716 285 2 719 285 146 1 281 146 139 1 157 139 7 19 124 Пять первых частных одинаковы в обоих случаях, так что они должны быть правильными.
Но на шестом шаге обнаруживается, что д' ф д", поэтому вычисления с однократной точностью прекращаются. Тем самым мы выяснили, что если бы вычисления выполнялись с исходными числами как с числами многократной точности, то это происходило бы так, ив ее ио — 2ео — ио + Зев Зив — 8ев -4ио + 11ео ев ив — 2еа — ио + Зев Зио — 8ео — 4ио + 11ео 7ив — 19ев (28) (Следующее частное находится между 3 и 19.) Независимо от количества разрядов чисел и и е до тех пор, пока выполняется (27), первые пять шагов алгоритма Евклида будут такими же, как в (28). Поэтому вычисления с однократной точностью можно выполнять на первых пяти шагах, а операции с многократной точностью— только при вычислении значений — 4ию + 11ее и 7ив — 19ев. В этом случае получаем и = 1268728, е = 279726; дальнейшие вычисления можно продолжить подобным же образом с числами и' = 1268, е' = 280, и" = 1269, е" = 279 и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
