Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 96
Текст из файла (страница 96)
(См. 1ЕЕЕ Тгапзасс!опз 1Т-26 (1980), 726-729,] 36. Согласно выражению (4) тп-е простое число равно т !п т+ т !п1пт — т+ т!п1пт/!и рп — 2тп/!и т+ 0(т(!ой !обт)з(!обт) з), хотя для решения поставленной задачи достаточно более слабой оценки р = т !и рп + 0(т1о61ойт).
(Полагаем, что р является т-и простым числом, учитывая прелположе- 1 Р ....Р..., )Р . бр. б,' Ьрб.бб Р Р,„. с = 0(Ц, получим ,=,-', Р РТР ОР- - -'О Р ! РТР Р бб-б,-'РР Т,РТР,Р,б ОРОР Р бТЕУР. Оценка (22) времени выполнения алгоритма Е нескатько неожиданно упрощается; р(РР.,РРОБЯБР о+О(ЄРбоб), где функция /(с, !р') = с+ (1 — (1+ 1п 2) !п1п !Тт)с ', Значение числа с, минимизирующего функцию /(с,!Тр), равно 1 — 1+ п2 и и!Тр. Таким образом, получаем оценку ~(Р Л' РББУ РГ-ОРБР7~РР РРРРРчб боа Для»У = 1Ою эта оценка дает е(»У) .ЗЗ, что по-прежнему существенно превышает результаты наблюдений за поведением процесса.
Замечакие. Поведение частичных отношений числа ~/В подчиняется распределению, полученному в разделе 4.5.3 для случайных вещественных чисел. Например, первый миллион частичных отношений для числа 10'э+ 314159 содержит точно (4Г5 236, 169 719, 93 180, 58606) случаев, когда А соответствует (1, 2, 3, 4). Более того, в соответствии с результатом упр. 4.5.3-12(с) и уравнением 4.5.3-(12) имеем $'„~.» = ]р~ — 279~] = 2ч'»»д~]р — ~Ю9„] + О(9„~). Поэтому гледуег ожидать, что поведение величины гЬ/2»Ф будет, по существу, аналогично поведению величииы 9 (х) м 9„]р„— к9,], где х — случайное вещественное числа Для случайной перемеииой д„известна приближенная плотность распределения ш!п(1,6 '-Ц/!п 2 для 0 < 6 < 1, равиомерная при 9 < 1/2 (см.
Божиа, Забег, %!е»Ц!», 1в»йщ. МаГ!». 4$ (1983), 281-299]. Таким образом, при обнаружении иеприемлемой эффективности алгоритма Е необходимо, кроме размера величии 'г„, принимать во внимание какие-то дополнительные условия. 37. Примените к числу ~/В+В результат упр. 4,5.3-12, чтобы увидеть, начинается ли сразу же периодическая часть дроби, и затем проверьте свойство палиндромности, вычигляя период в обратном порядке. (Отсюда следует, что вторая часть периода дает те же зиачеиия 1', что и первая, и выполнекие алгоритма Е может прекратиться раньше, при выполнении шага Е5, когда (/ = 1!' или $' = Ъ".
Однако в общем случае этот период настолько длинен, что не удается добраться до его половины; поэтому для дополиительиого усложнения алгоритма оснований нет.»» 38. Пусть г = (1Ою — 1)/9. Тогда Ре = 10»е + 9; Р» = г + 3 10»е; Рз = 2г + 3 10»г + 7; Рз = Зг+2 ° 10»э; Р» = 4г+2 ° 10»з — 3; Рэ = Зг+3 ° 10»э+4; Ре — бг+2 10»е+3; Рт = 7г+ 2 1Оы (прекрасно!); Ре = Вг+ 10»е — 7; Ре = 9г — 8000, 39. Заметим, что в случае, когда число 4 — 1 имеет 2 и р в качестве простых миожптелей, легко доказать, что 9 есть простое число. Преемниками числа 2 являются числа Ферма, а одной из наиболее известных нерешенных задач теории чисел для этого случал является существоваиие или отсутствие шестого простого числа Ферма.
Поэтому мы, возможно, никогда ие узнаем, как определить, имеет ли произвольное целое число каких-либо прг».мкиков. Тем не менее э некоторых случаях зто возможно; иапример, в 1962 голу Джон Селфридж (ЛоЬп Яе!7г!»(Ве) доказал, что числа 78557 и 271129 таких преемников не имеют (см. АММ 70 (1963), 101-102]. Позже В. Серпиньский (Ж, 8!егршзЬ!) доказал существование бесконечного количества нечетных чисел без преемников (Е!ешепге»!ег МагЬ. 15 (1960). 73-74]. Возможно, число 78 557 является самым маленьким из иих, хотя в настоящее время уже известно 69 претендентов на эту роль благодаря исследованиям, выполнениым в 1983 галу Г.
Йешке (С. ЗаеесЬЬе) и У. Келлером (%. Кейег) (МагЬ, Сошр. 40 (1983), 381-384, 661-673; 4$ (1985), 637]. Сведения о более традиционной форме цепочек простых чисел (форме Каиииигэма (Сапшпййаш)), в которых переходами являются р -е 2р Ь 1, приведены в статье Гюнтера .Чоха (Сбпгег ЬоЬ) МагЬ.
Сошр. $3 (1989), 751-759. В частности, ои нашел, что число 554 688278 430 . 2" — 1 является простым при 0 < Ь < 12. 40. ]1пб Ргос. Ьеггегз 8 (1979), 28-31.] Заметим, что в таком абстрактном автомате х шо»! у = х — р (х/у] может быть легко вычислено, в результате чего получим просто константы вида 0 = х — я, 1 = (г/х], 2 = 1+ 1. Убедиться в выполиении условия я > О можно, проверив, будет ли х = 1 или (х/(х — 1)] Р О. (а) Сначала за 0(!обо) шагов вычислим ! ш (!Вп] путем повторного делеиия на 2; одновременно вычислим Ь = 2' и А = 2зсю за О(!об и) циклов путем повторного присвоеиия Ь»- 2Ь, А»- А~.
Прежде чем выполнять основные вычисления, предположим, что известны значения ! = А, в м (А+ 1) и о = гп!. Теперь можно выполнить присвоения т ~.— ги+1, г +- АГ, и г- (А+ 1)в, о+- ит, увеличив таким образом значение га на 1; кроме того, можно удвоишь значение т путем присвоения т +- 2т, и +- из, ь +- (!(и/Г) гпог! А)ьз, г е- гг, учитывая, что число А является достаточно большим. (Подумайте над вариантом, когда число в представлено в системе счисления по основанию А; при этом А должно быть больше, чем (з ).) Далее, если и = (аг...ао)з, положим и, = (аь..аг)г; если т = и н !г = 2з при / > О, то можно уменьшить / на 1, присвоив !г +- [Ь/2), т г- 2га+ ([и/Ь) шоб 2).
Следовательно, можно вычислить число ей! для ! = 1, ! — 1, ..., 0 за О(!оба) циклов, [Джулия Робинсон (до!!а ВоЬ1пеоп) предложила другое решение, а именно: вычисеять и! = [В"/(~)) тогда, когда В > (2и)"е' (см. АММ 80 (1973), 250-2Ы, 266).) 2~'~ з (Ь) Сначала, как и в (а), вычисаяем А и 2, затем находим наименьшее й > О, такое, что 2~+'! шоб и = О. Если 8<г!(и, 2~!) Ге 1, полагаем 1(и) равным этому значению; обратите внимание, что этот наибольший общий делитель может быть вычислен при помощи алгоритма Евклида за 0(1оби) циклов.
Если бсг1(и,2"!) = 1, можно найти наименьшее целое число ги, такое, что (, ) тоби = О, н положить 1(зг) = 8<г!(т,и). (Учтите, что в этом случае 2" < ги < 2~е', следовательно, [га/2) < 2" и [т/2) ! взаимно просто с числом гг, поэтому („) шоб и = 0 тогда и только тогда., когда га! гпог1 и = О.
В дальнейшем и р' 4.) При ограниченном количестве регистров для вычисления ги можно использовать числа Фибоначчи (см, алгоритм 6.2.1Г). Предположим, известно, что з = Р', з' = Р;.гг, г = А~г, !' = А"~н', и = (А+ 1)зг', в' = (А+ 1)'г+', и = А, ш = (А+ 1)з, (' ) шаг[ ое 0 н (ц '~Ю) шог! и = О. Этого можно легко достичь при га = 3~ ьг для достаточно больших/ за О(!ой и) циклов; более того, А будет больше, чем 2ц +М.
Если з = 1, присваиваем 1(и) = боб(2т+ 1, и) илн боб(2т+ 2, и), выбирая то из ннх, которое ф 1. Выполнение алгоритма па этом завершается. В противном случае уменьшаем 1 на 1 следующим образом: сначала присваиваем г г — з, з г- з' — з, з +- г, г < — г, г +- [г'/г), г' г- г, г +- и, н <- [г//и), и' +- г, затем, если ([ши/ег! шоб А) шог! и Зе О, присваиваем ги +- т + з, ш +- ши, о е- щ. (Можно ли решить эту задачу за менее чем 0(1об и) операций? Можно ли вычислить наименьший или наибольший простой множитель числа и за 0(1об и) операций?[ 41. (а) Очевидно, что гг(х) и гг(га) + /г(х,т) = гг(га) + 1(х,ги) — /о(х,т) — /г(х,т)— /з(х,т) — при 1 < ги < х. Присвоим х = Лг~, т = Л' и учтем, что 1ь(Лз, Л') = О прий>2. (Ь) Пагучаем /з(Л Л) 2 л« [Ре<Л [ = 2 ч« <лзгг(х(Л /р) х(р) + 1) 2 я<„, зго я(Г' /р) — ( ~ ') + (ж ~), где р и 9 определены на множестве простых чисел.
С до е о, 1 (1000,10) = ( — „) + (-П-) + (-Яй) + ( —,) + ( —,) + (-24-) + ,г(пню) (<Гзц) Ь ( Оо!) 24 4 21+ 16-1-15.!. 144-11 4-11 — 55 Ч-б = 63. (с) Приведенное в указании тохгдестэо просто означает, что ру-долгожитель есть р„г-долгожитель, который не кратен р~.. Очевидно, что 1(Лгз, Л') = 1(Лгз,р„,гя!). Применяем э'го тохгдество до тех пор, пока не получим значения 1(х,р ), где либо 1 ж О, либо х < Л".
Найдем результат; л-1 Лз гл! Л.з 1(Л Л') = ~, гз(")1( — „,1/г — ~~~ ~' , 'и(!г)1( —,рз г)[й — рз-долгожитель[. ь г !=г кгрг<о<л )грг' ' Дааее, 1(х, 1) = (х1, поэтому первая сумма равна 1 000 — 500 — 333 — 200 + 166 — 142 = — 9 (при Лг = 10).
Вторая сумма такова; -1(',о,1) — 1( — ',~,1) — 1('~~,2) — 1('о,,2)— 1('заем,3) = -100 — 71 — 33 — 24 — 9 = -237. Отсюда 1(1000,10) = -9+ 237 = 228 и гг(1 000) = 4+ 228 — 1 — 63 = 168. (сЦ Если Лг < 2, можно сформировать массив, в котором элементы аг ге„= [и+1 есть ру-долгожитель] для 1 < и < Лг представляют решето после ! проходов, а а аь + аэ ег для 1 < и < 2 . Затем, если х < !г'э, легко вычислить функцию /(х,р ) за 0(гп) шагов и удалить из решета числа, кратные р, за 0(дгэпг/р) шагов.
Общее время вычисления функции /(гзэ,)г!) будет равно О(!ээ!о897!об!ойдо)г так как 2.,",",' 1/р» = О(!оВ !оВ Ь'). Требования к объему памяти могут быть снижены от значения 2гэг~гл до 2Ьгт, если разбить решето на Ьг фрагментов размером !гг каждое н работать с каждым из них отдельно. Могут пригодиться вспомогательные таблицы значений р для 1 < / < я(йг) и д(Ь), а также наименьших простых множителей чисел Й, 1 < Ь < )у, которые можно просто сформировать перед выполнением основных вычислений. [См.
МагЬ. Сошр. 44 (1985), 537-560. Впервые подобный метод был предложен Д, Ф. Э. Мейселем (Э. Г. Е, Ме!ээе1, МасЬ. Аппйел 2 (1870), 636-642; 3 (1871), 523-525; 21 (1883), 304; 26 (1885), 251-257. Д. Г. Лемер (П. Н, 1.ейшег) опубликовал в журнале 102пом Х МагЬ. 3 (1959), 381-388, ряд уточнений этого метода. Но ни Мейсель, ни Лемер не нашли правила, по которому рекуррентная процедура останавливалась бы с той же эффективностью, что в описанном выше методе. Кроме того, Лагарнас (! аВапаэ) и Одлыжко (06!узйо), используя принципы аналитической теории чисел, разработали совершенно нное приближение, посредством которого величина к(дг) может быть вычислена за 0(гг'~гам) шагов (см. А А!Вопэйшэ 8 (1987), 173-191), При помошд уточненного метода, выполняющего вычисления за 0(Ьг эгэ+г) шагов, Делеглиз (Пе!48)!эе) и Рива (Н!эас) [Масй, Сошр.
66 (1996), 235 — 245[ установили мировой рекорд вычисления простых чисел: 10эо) 2 220 819602 560 918 840 42. Ы. [Начальная установка.[ Найти г, такое, что гт ш 1 (по модулю в); затем присвоить г' +- пгщобэ, и +- г'гшог)э, и +- э, чг г- (и — гг')г/эшог! в, В +- (з/гтгг/э), (иг, цз) +- (1, н), (ог, еэ) +- (О, е). (Задача заключается в поиске всех пар целых чисел (Л, д), таких, что (Лэ+ г)(па+ г") = !г': отсюда следует, что Лв+ д ш кг (по модулю э) и г/Лде < В. Алгоритм 4.5.2Х будет выполняться без учета величин !э, иэ, еэ', отношения Л!э+д!г ш м!г, Лез+ диг ш миг, Лез+пег ш эгег (по модулю э) остаются ннвариантными.) Ь2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
