Анализ алгоритма Евклида

Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи.

Суть последовательности Фибоначчи в том, что начиная с 1,1 следующее число получается сложением двух предыдущих.

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ….

Приступим к анализу алгоритма Евклида. Нас будет интересовать наихудший случай — когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n Î N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F _{n +2} , b = F _{n +1} , где F _k  — k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N Î N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает

é log _Ф ( Ö 5 N ) ù - 2,

где é a ù - верхнее целое a , F = (1 + Ö 5)/2 — больший корень характеристического уравнения последовательности Фибоначчи.

log _Ф ( Ö 5 N ) » 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за é 4,785 · 6 + 1,672 ù - 3 = 31 - 3 = 28 шагов.

Евклидовы кольца

Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.

Примеры

· Кольцо целых чисел Z. Пример евклидовой функции — абсолютное значение .

· Кольцо целых гауссовых чисел Z[i] (где i — мнимая единица, i² = − 1) с нормой d(a + ib) = a² + b² — евклидово.

· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.

· Кольцо многочленов в одной переменной K[x] над полем K. Пример евклидовой функции — степень deg.

· Кольцо формальных степенных рядов K[[x]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).

· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z.

· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C[x].

Аналоги чисел Фибоначчи

Мною были построены аналоги чисел Фибоначчи в кольце многочленов и исследованы некоторые их свойства. Для этих целей я использовала программу Mathematica 5.1.

Определение аналогов чисел Фибоначчи:

; ;

Первые 10 многочленов:

1.

2.

3.

4.

5.

6.

9.

10.

Заключение

Данная работа посвящена расширенному алгоритму Евклида. Алгоритму Евклида более 2000 лет и он традиционно используется для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления.

Со временем алгоритм Евклида стали применять и в диафантовом анализе (для решения уравнений в целых числах), и в механизме цепных дробей (для наилучшего приближения действительных чисел рациональными), используется и для быстрого возведения в степень в компьютерных алгоритмах, и в криптографии.

Как было показано, числа Фибоначчи обладают экстремальным свойствам: при подстановке в алгоритм Евклида чисел Фибоначчи с номерами n и n+1, алгоритм выполняется за n шагов.

В своей работе я нашла многочлены обладающие теми же свойствами. В дальнейшем я планирую исследовать свойства этих многочленов и построить степенные ряды, обладающие теми же свойствами.