Бабенко - Основы численного анализа (947491), страница 9
Текст из файла (страница 9)
Пусть И вЂ” —. НОД (т, и); тогда из формулы (3) вытекает, что ш — Юь(чм, Чь) и — — Мь-з(Чж, Чь). (Ж 2. Нисла Фибоначчи. Сделаем небольшое отступление и введем так называемые числа Фибоначчи. Эти числа получаются как решения простейшего разностного уравнения второго порядка: (5) Р~, я = Е,ьз + Е), 1 = О, 1,. при начальных условиях Ее = О, Р~ = 1.
В п. 3 з'4 будет показано, что 1 Е~ = — (С1 — ( — 1)~Оо ) 1= О. 1 .. Чй (О) где 4 = (1+ ~/5)/2. Число р называется золотым сечением илн золотим отношением. Сравнивая формулы (2) и (5), замечаем, что (у) Яи(1,...,1)=Ео и п=0,1, Этих фактов достаточно для нашего исследования алгоритма Евклида. Указании 1. Разделить ш на п, и пусть г остаток; переходить к указанию 2, Указании 2. Если г = О, то работа заканчивается: НОД равен п. В противном случае переходить к указанию 3.
Указании 3. Произвести замену: т заменить на и, а п на г; возвратиться к указанию 1. В качестве элементарной операции в приведенном выше описании алгоритма Евклида используется операция деления с остатком„которая в свою очередь может быть расчленена на более элемептарнью. Ниже мы будем отступать от такого способа записи алгоритмов и записывать их еще более неформально. 3.
Сравнение двух алгоритмов. Учитывая соотношения (1), можно записать алгоритм Евклида отыскания НОД (т, п) в виде следующего предписания. Алгоритм Евклида. Глава 1. Постановка оадач «целен»»ого ав лава Если требуется вьгшслить НОД 1т, и) для больших т„п, когда число их разрядов превосходит число разрядов чисел, используемых в ЭВЫ, то потребуется использование арифметики многократной точности. Существует красивый способ избежать этой трудности см. 155).
Ясно, что время работы алгоритма Евклида определяется числом Т1пт, и) операций деления, которые нужно выполнить для нахождения НОД !т, и). Конечно, операцию деления можно заменить на операцию вычитания., по такая замена не приводит, вообще говоря, к уменыпению времени работы алгоритма.
Однако в этой идее есть скрытый резерв, и мы опишем еще один алгоритм вычисления НОД, который может конкурировать с алн горитмом Евклида. Приведем этот алгоритм для случая нечетных т, и. Он основан на следующих очевидных соотношениях; 1) НОД 1к, 1) —. = НОД!к — 1, 1); 2) 11с — 1 < шах!15 1) 1й > О, 1 > О); 3) если й четно, 1 нечетно, то НОД (Ь, 1) = НОД (Й,~2. 1). Этот алгоритм наиболее эффективен при бинарном представлении чисел. Ниже будем пользоваться следующими обозначениями. Запись а — Ь означает, что значение переменной а должно быть залшнено текущим значением переменной Ь; запись а — «формула» означает, что значение переменной и должно быть заменено величиной, полученной с покцлцью вычислений по формуле при текущих значепнях входящих в нее переменных; запись и "' Ь озна ~лет, что нужно совершить взаимный обмен указанных переменных.
Б н н а р н ы й а л г о р н т м в ы ч н с л е н я я НОД. Уклзлник 1. Вычесть и из т и 1 — т — и,. Если Ь < О, то п -- т; если 1 = О, работа заканчивается н НОД равен и. Укл:злиик 2. Разделить 1 на 2 и 1 -- 11'2. Уклзлник 3.
Если Ь четно., возвратиться к указанию 2; в противном случае и» вЂ”,1~ и возвратиться к указанию 1. Нетрудно освободиться от ограни ~ения на т, ц и расширить этот алгоритм на общий случай. Если оба алгоритма реализовать в виде программ на ЭВУ!, то можно сравнить времена их выполнения. Такое сравнение было сделано в 155) применительно к гипотетической машине У!1Х и показало, что бинарный алгоритм выполняется примерно на 15 то быстрее.
Это довольно неожиданный результат, и он является яр ед о с т е р еж е н нем, что в вопросе конструирования вычислительных алгоритмов нельзя полагаться на традиции я устоявшиеся представления. 4. Время работы алгоритма Евклида. Для того чтобы оценить эффективность или время работы алгоритма Евклида, нужно уметь оценивать величину Т1 гав и), равную числу операций деления.
Эта арифметическая функция имеет очень сложное поведение, и пока поддается исследованию пе она сама, а лишь ее некоторые средние. Такой вреднее величиной может быть (1' — 1 т п~ мр1пО)= — ~ ~Те1т, и) ~, р — 1, 2, 1т :.л 37 84, Примеры лгаритмаа; ана иг алгаритмае Асимптотика функции м(т) при т '! оо будет характеризовать среднее поведение Т(т, п), и при р = 1 мы получим асимптнгнку среднего времени выполнения алгоритма Евклида. Интересен вопрос о росте шах Т(т, п~и 1« Доклзлтнльство.
Из формул (4) следует, что при заданной длине непрерывной дроби для т(п числитель будет минимааьным, если д = 1 и 91 = ... — — уя 1 =- 1, уь = '2, поскольку коэффициенты многочлена Ць(ссм..., яь) положительные, Но если увеличить длину дроби на 1 и записать ее в виде 1;1,...,1,2 =(1;1,...,1,Ц, то получим т = Оьтг(1, ..., 1), п = сгь(1, ..., Ц или, учитывая (7), найдем сп — Рь.ьг и = Еь -1 отсюда й (~ г, П Следствие.
Допустим, чта и < т ( йс. Тогда 1 шах шахТ(т, и) = — !п(ч'5Х) —.7, = (4,784971...)!8г1 —.зн, (8) <и < ' 1пф где 2 + сн < Зн < 3 + шн, а гн, шн — 0 при Я ": сю. Доклзлтьльство. Найдем такое Й, что Гь < Х < Рьн ь По теореме Ламе Т(т, п) ( к — 2, причем знак равенства достигается, осли т = Ры и = Рь Логарифмируя соотношение (6), получим при 1 = й й =-.
!н(ч'5 Ра) — дь, 1 раф (9) где бь — 0 при й 1 со. Из последнего соотношения вытекает, что й ( < 1п(иб Я1)7'!пф —; дь, а делая в с)гормуле (9) подстановку 5 е- У -!- 1, попучим й > !п(ч75%),1 !и ф бь ьг — 1. Из последних двух неравенств вытекает соотношение (8). П Теорема 2 (Г,Хейльбронн) (135). Имает место асимптотическое со- отношение м1(М) =- — ~ Т(М, и) =- !и_#_ —:О(т",(йй)) = 1, 12!п2 (10) = (1,940540...) 18 77 -!- О(а 1(Ж)), где а г(Л') = 2„д', нричслс суммирование асдстся по сссм делителям д -1 агн числа Х.
Мы довольно подробно рассмотрели алгоритм Евклида для того, чтобы показать, какие интересные н трудныс задачи возннквлот при анализе эффективности алгоритмов. Сделаем ение одно замечание. Пусть в коммутативном кольце Л без делителей нуля определено отображение у: 1( -ч Е+ такое, что для любых элементов а, 6 ф 0 д(аЬ) > д(а). Теорема 1 (Г.Ламе). Если н < т, т ( Р'„тг, та Т(т, и) ( т и знак рааснстеа имама мсспга при пс = ),'„+л и = !ф.ы. Глава Е Постановка оадач числеп~ого а11алиоа Если в этом кольца определен ю2горитм деления с остатком, т.е. для любых элементов а ф О и 6 существует представление 6 = ад+ г заков, что д(г) < УЕ(а) либо г — —.
О, то в таком качьце (называемом авклпдовмм) действует алгоритм Евклида отыскания НОД. В частности, если à — поле, то кольцо многочленов 11Ц, очевидно, будет евклиловым, и, следовательно, НОД двух многочленов отыскивается с помощью алгоритма Евклида. 3 а д а ч н. 1. Обобщите бинарный апгаритм вычисления НОД (т, п) на произвольные числа. 2. Опишите алгоритм, который вычисляет не только НОД (т, и), но одновременно два таких целых числа х, у, что хт ' уп = НОД (т, и). ° 5. Вычисление целой степени.
Рассмотрим одну из простейших задач численного анализа - задачу о вычислении х" для заданного х и целого и, в предположении, что умножение ассоциативно. Уже на самых простых примерах мы убеждаемся, что вычисление степеней по правилу последовательного умножения х~ —.- (х~ ~)х неэффективно. В самом дело, чтобы вычислить хв, не нужно семь умножений, 2 а достаточно вычислить х, х4, хв„т.е. нужны три умножения.
В случае произвольного показателя и, можно поступить следующим образом. ПрЕдСтаВИМ П В ДВОИЧНОМ ВИдв: П = 2 + Е22 +... т ЕЬ 22 — ' ГЬ, Гдс ь 6-1 = О, 1(д = 1, 2, ..., й) и вычислим х2, х4, ...., 22 последовательным возведением в квадрат.
После этого получим '11 / 21 16е1 2 .П .-, ( . )Е1-1, ЕЕ причем сомножители, для которых = О, в этом произведении должны быть опущены. Таким бинарным методом можно вычислить х" за 1оов и'1 -е а1(п) — 1 умножений, где ~1а) —. наибольшее целое число, меньшее или равное а, а2(ге) . число единиц в двоичном представлении числа и. Этот метод можно оформить более изящно, причем не запоминая промежуточных результатов.
Можно производить умножения по следующей схеме: Е1 2 ЕЕ ЕŠ— 1 У2 = т х ', У2 = У2х "..., Уь 4 = уг. 2х ' ', уь = УЕ. хе'. В самом деле, последовательно исключая у ~д' = 1, 2,..., У. - 1),. получим уь=х Приведем м н е м он и ч еское п р а в ил о (оно же служит основой алгоритма) для возведения в степень. В двоичном разложении числа и, = (во...есь)2, ее =.. 1, нужно каждую единицу заменить слогом )гу, а каждый нуль -" буквой )4. В полученном слове первый слог )су зачеркнуть, а затем, читая слово слева направо.
интерпретировать букву 11 как команду возведения в квадрат предыдущего результата, а букву у как команду умножения на х. Например, если требуется найти т22, 23 = (10111) 1, то получим слово 1су)с)суйу)су и после удаления первого слога )су слово )4)су)су)су, согласно которому вычисляем ряд промежуточй 2 л .5 1 ю 1гм 22, 23 39 'э 4, Примеры лгоритмов; оно ив алгоритмов Однако не всегда бннарньш метод является оптимальным методом. Для того же показателя п = 23 мы можем найти несколько иную последовательность промежуточных степеней, которая позволяет вычислить хгз за шесть умножений: хг, хз, х~, х'е, х~~, х-з. Из этой последовательности легко увидеть, что она строится по следующему правилу: находится последовательность целых чисел 1 = по < пг « ...
пс = и такая, что и, = и, т пь (Й < у < г', 1 = 2, 3,, г). Такие последовательности называются аддьипивнмми цвпочкалви, и задача оптимального вычисления х," сводится к построению аддитивной цепочки минимальной длины гу которую будем обозначать 1(п). Учитывая, что и, < 21 (у = 1, 2, ..., г), получим г = 1(п) ) 1ойв и., и егли обозначить через (а наименьшее целое число, большее а, то 1(п) > !ока п1 С другой стороны, учитывая число умножений в бинарном методе, получим 1(п) < (!ойз и.
+ иг(п) — 1. (12) Получение точных оценок снизу. для 1(п) очень трудная задача. 'Георема 3 [128]. !1пэ(1(п)гг!одп) = 1. Отметим, что при больших и выполняется неравенство 1(и,) <1ойоп — +О 1ойвп . (13) !ок п г 1ойз!окт1ойвпу ойз ойо и (!Ойв ойв и Гипотеза А. Шольца об алдитивных попочках гласит 1(2и — 1) < п, -- 1 — 1(и). Это неравенство проверено при и < 23, но не доказано в общем случае. Мы видим и на примере этой задачи, что элементарная задача численного анализа о вычислении степеней неожиданно приводит к очень трудпон задаче комбинаторики, как только мы пытаемся построить оптимальный алгоритм. 3 в д а ч н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
