Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 92
Текст из файла (страница 92)
Заменяя последовательность //хм..., х„// последовательностью //хм..., х„м х„— 1, 1//, можно управлять формированием знака (-1)». Например, для частичных сумм первого ряда получаем следующие цепные дроби четной длины: //1,1//; //1,1,1,1,0,1// = //1,1,1,2//; //1,1,1,2,1,1,1,1,1,1//; //1,1,1,2,1,1, 1,1,1,1,1,1,0,1,1,1,1,1,2,1,1,1// = //1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,1//. Далее последовательность упорядочивается и подчиняется простой закономерности, Для случая, когда и — 1 = 204+ т при 0 < г < 20, найдем, что частичное отношение а„может быть легко вычислено: если г = 0,2,4,5,6,7,9,10,12,13,14,15,17 или 19; если г = 3 или 16; 1, 2, 1+ (д+ г) шоб 2, если г = 8 или 11; 2 — 8„ если г = 1; 1+6,,„ если г м 18.
42. Предположим, что [[дХ[[ = [дХ вЂ” р[. Можно всегда найти такие целые числа и и», что д = ид„~+»д„и р = ир„~+»р„, где р = К -~(Аз,..., А ), так как 4„р„~ -д„~р„= ж1. При» = 0 результат очевиден. В противном случае должно быть и» < О, т.
е. знак числа и(д„~Х вЂ” р„~) совпадает со знаком числа»(д Л -р„), а [дХ-р[ равно [и[ [д„-~ Х-р ~[+ [»[ [д„Х вЂ” р [. Поскольку и ~ О, доказательство на этом завершается, Обобщение данного результата дается теоремой 6.48. 43, Если число х представимо, оно родственно числу я в дереве Штерна Бр»кота из упр. 40, поэтому представимые числа образуют поддерево бинарного дерева, Положим, что числа (н/и') и (»/»') — соседние представимые числа.
Тогда адно из них является предшественником другого. Пусть, например, число (и/и') явлкется предшественником числа (»/»'), поскольку другой вариант аналогичен. Тогда (и/и') — ближайший левый предшественник для (»/»'), так что асе числа между и/и' и»/»' будут для числа (»/»') его потомками, а этим числом порождается медианное число ((и+»)/(к'+»')). Учнтмвая зависимость между правильной цепной дробью и бинарным деревом, медианное число и все его левые потомки будут иметь в качестве последнего представимого числа р,/д; число (и/и'), в то время как все потомки справа от медианного числа будут иметь в качестве последнего представимого числа р;/ 1; число (»/»'). (Числа р;/д; помечают редишелей узлов "точек превращения" на пути к я.) 44.
Контрпример для Л!' = !т' = 100 выглядит так: (и/и') = 1, (»/»') = Я. Тем не менее в силу уравнения (12) тождество почти всегда справедливо; оно нарушается только тогда, когда и/и' +»/»' очень близко к дроби, более простой, чем (и/и'). 45. При использовании обычного длинного деления для определения таких А и г, чтобы выполнялось равенство и = А» + г при О < г <», требуется О((1 + 1ой А)(!об и)) единиц Здесь Ȅ— "последовательность дракона", определяемая правилами 4> ш 1, с(з„= Ы„, А .~~ = О, И4,+з = 1. Кривая дракона (рассматривалась в упр„4,1-18) поворачивается вправо на к-и шаге тогда и только тогда, когда И„= 1.
Числа Лиувилля при ! > 3 равны //! — 1, !+ 1, ! — 1, 1, 1, !-1, 1~~ — 1, 1, !-2, 1, 1, !т — 1, !+1,!-1, ! — 1,... //. пе частичное отношение а„зависит от последовательности дракона, элементы которой представимы по и пюс(4 в слш0'ющем виде: если и шоб 4 = 1, то частное равно 1-2+4, ~+([и/2) пю64), если н шо64 = 2, то оно равно !+2-6 .~ э — ([и/2) шо64); если и шос) 4 = О, то оно равно 1 или !ькэ Π— 1 в зависимости от того, будет ли 4, = О или 1, где число Ь вЂ” наибольшая степень 2, которае делит и; если и ш»64 = 3, то оно равно ! ' — 1 или 1 в зависимости от того, равно ли И .„~ = 0 или 1, где число Ь— м(ь-1) наибольшая степень 2, которая делит и+ 1. Для ! = 2 применяютсл те же правила, но из рассмотрения исключаются нули; поэтому в зависимости от и шоб 24 получаются более сложные закономерности.. [См.
3. О. ЯЬа(!1Ц Л г!ншЬег Уйеогу 11 (1979), 209-217; А!!овсЬе, ЬвЬич, Мепс)ев Ргапсе, »ап бег Рооггеп, апб ЯЬа1!1ц А»та Агййшег!са 77 (1996), 77-96.) времени. Если частными во время выполнения алгоритма являются Ам Аз, ..., А,, то А~Аз . А < и, так что !обА~+ + )обА < !обе. В силу теоремы 1 имеем также ш = О(!обо). 48. Па, этв граница может быть уменьшена до величины О(п(!об и) ~()об !ой и)), даже если придется вычислять последовательность частичных отношений, которые можно вычислить по алгоритму Евклида, (См. А. ЯсЬбпЬайе, Асса Упйгшас!са 1 (1971), 139-144.) Более того, алгоритм Шензаге (ВсЬопЬабе) является асимптотнчески оптимальным по отношению к выполняемым нм операциям умножения н деления (У, 81гаеееп, ЯСОМР 12 (1983), 1-27]. При не очень больших и на практике лучше применять алгоритм 4.5.2Ь, однако в книге А.
БсЬовЬабе, А. Р. Ч'. Отогеге!4, апб Е. Уегсег Гаег А!яог!1Ьшз (НеЫе!Ьшй: Ярейггнш А)пк)еш)есЬег Уег!аб, 1994), 17.2, приводятся идеи зффективного использования алгоритма для чисел длиной до 1 800 бит. 48. Т. = (К; г(-ам...,— а; ~), К ~(-ац...,— а,-г), Кч-з(о;ем...,о )Я ы ((-1)1К1 з(ам.,.,а ~), ( — Цз""К. г(ац...,о ~), К„,(а,~м...,а,)д). 49. Поскольку Лх~ +,иг~ = ро и Лх ьг + ре ег = -Ли/Ы, существует такое нечетное значение /л что Лх, + ре > 0 и Лх +т+ де!ее < О. Если Лх, + раз > В и Лх ез+ ркзьз < -В: то вышиняется д > В/е, и Л > — В/хз+ь Отсюда следует, что 0 < Лх~+~ + резь~ < Лрхгыху/ — Лдгз~ых,+г/В < 2Лре/В ю 2В, так как для всех 5 выполняется !хьегхе! ж Кь-~(вм ..аь)К„-ь(ее~.м...,а„) < К„~(аз,...,а„) = е/И.
(Н, %. 1епегга, 3г,, Магй. Сшпр. 42 (1984), 331-340.) 60. Положим Ь = ()1/и'!. Если Ьа < 7, то результат равен Ь; в противном случае результат равен ~/((1/а) шоб1,5 — 7 а,й — 0/ц)~ 61. Если ах — тпг = у н х Л у„то имеем х Л нш. Рассмотрим дерево Стерна.Брокота из упр. 40 с заданным дополнительным узлом с меткой О/1. Объединим помеченное значение у = ах — тг с каждым узлом с меткой е/х. Требуется кайти все узлы е/х, для которых у по абсолютной величине не превышает В ж ~/т/2 и для которых знаменатель х тоже < В. Едянственный возможный путь к таким узлам поддерживает положительный маркер влево и отрицательный — вправо.
Это правило определяет единственный путь, который поворачивает вправо, когда маркер положительный, влево — когда маркер отрицательный, и останавливается, когда маркер становится равным нулю. Этот путь неявно полдерживаетсл при выполнении алгоритма 4.5.2Х, когда я = щ и е а, исключая случай, когда алгоритм "прыгает" вперед — он просматривает узлы только перед тем, как маркер меняет знак (родители узлов "точки превращения", как в упр. 43). Пусть е/х — первый узел пути, маркер которого е удовлетворяет условию (у! < В. Если х > В, то решения нет, тшс как соответствующие значения иа пути имеют даже ббльшие знаменатели, В противном случае (хх, жу) является решением, полученным при х Л у.
Легко видеть, что если у = О, то решении не существует, и что если у уе О, то знак маркера на следующем узле пути не будет совпадать со знаком у. Позтому узел х/х будет обработан алгоритмом 4.5.2Х и для некоторого у будет выполняться х = хз * ку-~(аы...,аз-д), р = 91 = ( — 1) к„~(о~+ы...,а„)и, х = аз = к, е(аз,...,аз ~) 0-н (см, упр, 48). Следующим подходящим для решения узлом будет узел с меткой х'/х' = (ху ~ + Йз;)/(хз ~ + Йхт) с маркером у' = ру ~ + 591, где Й настолько мало, что (р'! < В; отсюда у'у < О. Однако теперь нужно увеличить В, иначе будем иметь гп = К~(ам..., а„)Ы = х !у! + х)у! < Вз + Ве = ш и неравенство не будет удовлетворяться.
Эти рассуждения доказывают, что задача может быть аффективно решена путем применения алгоритма 4.5,2Х для случая, когда и = гп и и м а, но при следующей замене операции шага Х2: "Если оз < ~/ш~2, то выполнение шггоритма завершается. Пара (х, у) ((е«), из ибп(о«)) является, следовательно, единственным решением, обеспечивающим х .1. у и х <»/щ/2; в противном случае решения нет".
(Р. Я, 1Чапб, Ьес«иге 7»опп «и Сошр. Яс( 162 (1983), 225-235; Р. Когпеп«р, В, Т. Стеба«у, В/Т 23 (1983), 9-20.) Подобный метод будет работатзь если потребовать, чтобы О < х < В~ и )у! < В«, когда 2В,В, < РАЗДЕЛ 4.$.4 1. Если В» — не простое число, то его простые множители выделяются перед использованием пробного делителя И». 2. Нет; прп такой модификации а случае, когда 𫻠— — р», алгоритм сделает ошибку, выдав а качестве простого множителя едннипу. 3, Можно взять Р равным произаедению первых 108 простых чисел.
(Замечание. Для того чтобы только проаерить, является ли число я простым. наименьший обпгий делитель для 416-разрядного числа Р = 19590... 5910 может быть вычислен значительно быстрее, чем потребуется для выполнения 168 операций деления.) 4. В обозначениях упр. 3.1-11 имеем 1-1 Р( Л) = — ~/(!)П 1 —— и« гп/' и,» 1>!»1 где /(!) = 2 20«~'"О»' »*»!! Если ! = 2"ае при 0 < В < 1, то /(!)=!(3.2 — 2 2 «), где функция 3 2 е — 2 2 ~ достигает максимума «а точке В = !8(4/3) н имеет минимум, равный 1, при В = О н 1. Поэтому среднее значение величины 20з~'"щ'~ь»0 находится между средними значениями величин и+ Л, умноженными на постоянную в ннтераале от 1,0 до 1.125, откуда и следует результат. Замечание.
Ричард Брент (В!с!»агс! Вгепг) заметил, что прн щ -» оо плотность П (1 — Й/гл) = ехр(-!(! — 1)/2т + О(!«/и»«)) стремится к нормальному распределению, поэтому мо«кно положить, что значения В распределены равномерно. Тогда функция 3 2 е — 2 2 «а имеет среднее значение 3/(4 !и 2), а среднее число итераций, необходимых для выполнения алгоритма В, стремится к значению (3/(4 !и 2) + -')»/яй»/2 = 1.98277»/т.
В результате подобного щ«ализа более общего метода, который выполнен в упр. 3,1-7, получен следующий результат: 1,92600»/т, где р ж 2,4771366 выбрано»оптимально" как корень из (р« — 1) !ар = р« — р+ 1 (см, В1Т 20 (1980), 176-184), Алгоритм В представляет собой уточненный алгоритм Полларда (Ро!!агг!), на базе которого было получено решение упр. 3.1-6(Ь) вместо еще не найденного решения упр. 3.1-7. Поллард показал, что минимальное число и, такое, что Х«„ж Х, равно среднему значению (я~/12)Я(щ) ж 1.0308»/т; зта константа я«/12 слепует кз уравнения 4.5.3-(21). Таким образом, общий средний объем вычислений оригинального алгоритма Полларда равен приблизительно 1.03081»/щ — числу операций вычисления наибольших общих делителей (или умножений по модулю гл) и 3.09243»/т операций вычисления квадрата. Это действительно лучше, чем при выполнении алгоритма В в случае, когда затраты на вычисление наибольшего общего делителя больше затрат на вычисление квадрата, умноженных на константу 1.17, как это обычно и случается для больших чисел, Однако Брент обратил внимание на то, что алгоритм В может быть усовершенствован, если при Й > 1/2 из него исключить поиск наибольшего общего,зллптеля; если выполнение шага В4 повторяется до тех пор, пока не станет удовлетворяться неравенство Ь < 1/2, то цикл можно обнаружить и после выполнения последующих Л [К(р)/Л] = 1(/г) — (1(ф) пкн1 Л) итераций.
В этом случае средние затраты приблизительно равны (3/(41п2))ч'хш/2 1.35611~/Б — числу итераций, на которых выполняетсв вычисление квагбгата без вычис- ления наибольшего общего делителя, плюс ((!пя — 7)/(4 !и 2) + -')~/яш/2 ш,88319~/т— число итераций, на которых выполняются обе операции, [См. анализ Генри Колена (Непп( СоЬеп) в А Соиле ш Сошригабола1 А18ебгшс ррпшЬег ТЬеогу (Вег)ш: Ярйпбег, 1993), 58.5.] 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
