Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2), страница 12

Переменные П, бе', У; $", Р, Р', .4 и 5 представляют В + П„, В. + К, м К 1о-м ра шоб Х, р„-е шод Х, А„и и шос1 2 соответственно. Всегда будет выполняться неравенство О < у < П < В', поэтому самая высокая точность потребуется только для нахождения чисел Р и Р'.) Е2. (Продвинуть П, Ъ~, Я.] Присвоить Т +- 1; Ъ~ +- А(П' — П) + 1', 1'" +- Т, А +- (С7$'], П' <- П, П +- В' — (П шоб Г'), 5 +- 1 — 5. ЕЗ. (Разложить на множители Ц (В соответствии с результатами упр. 4.5.3 — 12(с) здесь имеем Рз — 1Х1Зе = ( — 1)~Г) ПРисвоить (ео„ем...,е„,) +- (Я,О,...,0), Т с- К Теперь нужно выполнитьследующее.

Для 1 < у < т, если Тшодрэ = О, присвоить Т +- Т/р и е +- е + 1 и повторять этот процесс до тех пор, пока не получится Т шое( р„э~ О. Таблица 1 ПРИМЕР ВЫПОЛНЕНИЯ АЛГОРИТМА Е Н = Гвгтав, Ь = 1, тэ = З, р~ = 2, рэ = 3, Рэ = Э Выход Е4. (Решенне?) Если Т = 1, вывести значения (Р, еэ, е„..., е~), которые составляют решение уравненэя (19). (Еслн получено достаточное число решений, то на этом шаге алгоритм может быть завершен.) Еб. (Продвинуть Р, Р'.) Если т' Р 1, присвоить Т т — Р, Р т- (АР+ Р') шот(№ Р' т- Т н возвратиться к шагу Е2. В противном случае процесс разложения в цепную дробь начинает повторять цикл сначала, за возможным нсключеннем л, н поэтому выполненне алгоритма на этом завершается.

(Обычно данный цикл настолько продолжнтелен, что завершенне не происходит.) 1 В качестве примера применения алгоритма Е к сравнительно малым числам рассмотрнм случай, когда Х = 197209, к = 1, гл = 3, рг — — 2, рэ —— 3, рэ = 5. Начальная часть вычислений представлена в табл. 1. Продолжение вычнсленнй прнводнт к получению за первые 100 итераций 25 выходных данных; другими словами, алгоритм находит решения очень быстро, но некоторые нз ннх трпвнальны. Например, если продолжить вычисления еще на 14 шагов, можно получить 197197э ьз 2~ ° Зэ 5о выходных данных, которые не представляют интереса, поскольку 197197 рл — 12.

Для завершения процесса разложения па простые множители достаточно первых двух решений, полученных выше. Так как получено (159316 133218)т рл (2э. Зз 5')э (по модулю 197209), соотношение (18) выполняется прн х = (159316 133218)шо6197209 = 126308, д = 540. В соответствии с алгоритмом Евклида всб(126308 — 540, 197209) = 199, н получаем изящное разложение 197209 = 199 991. Чтобы понять прнчнны, по которым элгорнтм Е столь успешно выполняет разложение больших чисел на простые множнтелн, рассмотрим эврнстнческнй аналнз времени выполнения алгоритма Е, следуя неопублнкованной идте, высказанной После Е1: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: После Е4: П 1' А 888 1 О 876 73 12 882 145 6 857 37 23 751 720 1 852 143 5 681 215 З 863 656 1 ВВЗ ЗЗ 26 В21 136 б 877 405 2 875 24 36 490 477 1 Р 9 444 О 444 1 5З29 О 32418 1 159316 0 191 734 1 1З1 941 О 193 1ЗО 127871 0 165 232 1 1ЗЗ 218 О 37250 1 93 755 О 73 29 З7 1 159316~ рл+2~ 3 ° 51 143 43 41 11 17 1 133 218~ рл +2 З~ 51 1 37250э и -2э 31 5э 53 автору в 1975 году Р.

Шруппелем (!1. 8сйгоерре!). Положим для определенности, что й = 1. Число выходных данных, необходимых для получения разложения числа Л' на простые множители, пропорционально т — числу выделенных в процессе вычислений малых простых чисел, Каждый раз на выполнение шага ЕЗ затрачивается порядка тп !о8Л' единиц времени, так что общее время выполнения в первом приближении пропорционально величине газ !о8Л!(Р, где Р— вероятность получения очередного результата на каждой итерации.

Предположим, что в течение всего времени выполнения алгоритма величина $' равномерно распределена в интервале от 0 до 2~/У. Тогда вероятность Р равна значению (2~/Х) ', умноженному иа количество целых чисел < 2ъ~Ф, для которых все простые множители принадлежат множеству (р~,...,р ). В упр. 29 приведена нижняя граница для Р, из которой можно заключить, что наибольшее время выполнения алгоритма имеет порядок 2~/Ютз)о8Х ! !о82~Х гдег= ~ гл г/г! )о8 ь ° *.

ь ~ ° ~.ь °, !,~БЗьью, ~щ р = а( ~ ), ~.,IБх7БЪю — ~, д* ° ф р у (ь) упрощается и принимает вид р(иДи7ьЬЮТ.~ оф~м)'~'~~~ р) '"О~Мьахф. Следовательно, при надлежащих прелположеннях ожидаемое время выполнения к р * х < "~, ° ~,ч ~ 'ьБЗ71' х стремится к 0 при Х -+ со. Когда число Л' находится в интервале, чаще всего используемом на практике, нужно быть осторожным и не принимать всерьез такую асимптотическую оценку. Например, если Л! = 10~с, получим Л'т~" = ()8Х)" при о 4.75, ио то же самое соотношение справедливо и для о а 8.42, когда Х = 10юе. Функция Хцм! имеет порядок роста, который представляет собой некоторого рода пересечение Лмз и (!8 Л'), но все три равенства практически одинаковы для чисел Л', не являющихся недопустимо большими.

Многочисленные вычислительные эксперименты, выполненные М. Ч. Вундерлихом (М. С. %цпбег!!сп), показали, что хорошо настроенный вариант алгоритма Е значительно лучше выполняет разложение, чем предусматривается этой оценкой [см, Ъес!иге Хо!ее (и Май. 751 (1979), 328-342); несмотря на * д к=в" ьГЯ7~~и .а, р р . р * множители тысяч чисел в интервале 10'з < Л' < 10эз он получил выражение для времени выполнения, равное приблизительно Л~'~. Попытка выполнить разложение числа Л с помощью алгоритма Е начинается. по существу, с замены Х на йЛ, что выглядит довольно любопытно (если не откровенно глупо).

"Простите, как вы смотрите на то, что перед попыткой разложения числа я умножу его на 37' Тем не менее идея выглядит привлекательной, поскольку некоторые значения /с делают числа 1' потенциально делимыми на меньшие простые числа, и поэтому на шаге ЕЗ полное разложение этих чисел на простые множители может быть выполнено проще. С другой стороны, большое значение числа х сделает числа 1' больше, и тогда их полное разложение на простые множители будет затруднено. Нужно сбалансировать эти тенденции путем соответствующего подбора числа lс.

Рассмотрим, например, делимость чисел 1: на числа, равные степеням 5. На шаге ЕЗ получаем Рэ — !гХ!'„!~ = ( — 1)э1', так что, если 5 делит г, имеем Рэ ш АА (~э (по модулю 5), В данном соответствии число Я не может быть кратным 5, поэтому оно взаимно просто с Р и можно записать (РЯ)э = АХ (по модулю 5). Если предположить, что Р и Я-- случайные взаимно простые числа, такие, что 24 возможные пары чисел (Р щи 5, Я шоб 5) З! (О, 0) равновероятны, вероятность того, что 5 делит 1'.

равна,, таким образом,,~4, зээ, О, О или,ээ в зависимости от того, какие значения принимает число кХ шоб 5: О, 1, 2, 3 или 4. Аналогично вероятность того, что 25 делит г', равна О, ф, О, О, ф соответственно, если только ЙЛ' не кратно 25. В общем случае для данного нечетного простого числа р, для которого (кХ)!" 'Уэ шобр = 1, получаем, что г' кратно р' с вероятностью 2/(р' '(р+ 1)); среднее число р делителей числа Ъ' приближается к 2р/(рэ — 1). Из этого анализа, выполненного Р. 1Пруппелем (К. Яспгоерре!), следует, что лучший выбор числа й— это значение, которое обеспечивает максимум функпии м 1 'Е. '/(р„ю !Ой р3 - - !Оа й, тки где / определена в упр.

28, поскольку, по существу, это ожидаемое значение величины !и(, /Х(Т) при переходе к шагу Е4. Если числа к и гп хорошо подобраны, выполнение разложения по алгоритму Е дает еще лучшие результаты. Выбор подходящего числа гп может быть выполнен экспериментально, так как проведенный выше анализ асимптотического поведения носит незавершенный характер и нельзя быть уверенным в точности полученной информации. Поэтому внесение в алгоритм многочисленных уточнений, связанных с таким выбором гп, может привести к непредсказуемым последствиям.

Например, сравнив выполнение шага ЕЗ с выполнением алгоритма А, можно получить следующее важное усовершенствование. Суть его в том, что процесс разложения иа простые множители можно остановить после нахождения Т щи рз ф 0 и (Т/р!) < рэ, поскольку в этом случае Т будет либо равно 1, либо простым числом. Если Т вЂ” простое число, большее р„, (в таком случае оно будет не больше р~ +р,„— 1), то, учитывая, что получено полное разложение на простые множители, можно вывести в качестве результата (Р, ее,..., е„„Т). На второй фазе алгоритма будут использованы только те выходные данные, для которых все простые числа Т встретятся ие менее двух раз. Эта модификация приводит к образованию намного большего списка простых чисел без дополнительных затрат времени.