AOP_Tom2 (1021737), страница 200
Текст из файла (страница 200)
Для 1 = 2 применяются те же правила, но из рассмотрения исключаются нули; поэтому в зависимости от и шоб 24 получаются более сложные закономерности . [См. Л. О. БЬаПЬ, Х ут'ишбег Тйеогу 11 (1979), 209-217; Л1!овсЬе, 1 пЬ1тг, Мепбеа Ргапсе, тап бег Роогсеп, вам ЯЬа!11Ь Асса Лпейпзебса 77 (1996), 77-96.] 42. Предположим, что ОдХО = )дХ вЂ” р). Можно всегда найти такие целые числа и и е, что д = ид„, +од„и р = ир ~ ч ер„, где р» = К ~ (Ат,..., Аь), так как дьр„~ — д„~ р„= х1.
При х = 0 результат очевиден. В противном случае должно быть их < О, т. е. знак числа и(д„~Х вЂ” р„~) совпадает со знаком числа и(д„Х вЂ” р ), а (дХ-р~ равно ~и!)д ~Х-р ~~+ (о( (д„Х вЂ” р„). Поскольку о ф О, доказательство на этом завершается. Обобщение данного результата дается теоремой 6.48. 43. Если число х представимо, оно родственно числу х в дереве Штерна-Брокота из упр. 40, поэтому представимые числа образуют поддерево бинарного дерева.
Положим, что числа (и/о') и (х/х') — соседние представимые числа. Тогда одно иэ ник является предшественником другого, Пусть, например, число (и/и ) является предшественником числа (х/х'), поскачьку другой вариант аналогичен. Тогда (к/к') — ближайший левый предшественник для (х/х'), так что все чигла между и/и~ и о/х~ будут для числа (х/е') его потомками, а этим числом порождается мелианное число ((и+ х)/(и'+ и')), Учитывая зависимость между правильной цепной дробью и бинарным деревом, медианное число и все его левые потомки будут иметь в качестве последнего представимого чигла р,/д, число (о/и'), в то время как все потомки справа от медианного числа будут иметь в качестве последнего представимого числа р,/д; число (х/е').
(Числа р;/д; помечают родишелей узлов "точек превращения" на пути к х.) 44. Контрпример для М = 1т' = 100 выглядит так: (и/в') = -', (х/х') = ээ. Тем не менее в силу уравнения (12) тождество почти всегда справедливо; оно нару~нается только тогда, когда и/ки + е/х' очень близко к дроби, более простой, чем (и/и'). 45. При использовании обычного длинного деления для определения таких А и г, чтобы выполнялось равенство в = Ах+ г при 0 < г < щ требуется 0((1+ 1обА)(1оби)) единиц времени.
Если частными во время выполнения адгоритма являются Ат, Ат, ..., А, то Ат.4т... Ам < и, так что !обАт + + 1обАм < !ой и. В силу теоремы Ь имеем также тл = 0(!об и). 46. Да, зта граница лтожет быть уменьшена до величины 0(п(!об и) (!ой 1об и)), даже если придется вычислять последовательность частичных отношений, которые можно вычислить по алгоритму Евклида. (См. А. Яс!топ!тайе, Асса 1п/отша!!са 1 (1971), 139-144.) Более того, алгоритм Шенхаге (БсЬопЬайе) является асимптотически оптимальным по отношению к выпалняемым им операциям умножения и деления [Ъ'.
Я!газзеп, ЯСОМР 12 (1983), 1-27]. При не очень больших и на практике лучюе применять алгоритм 4,5.2Ь, однако в книге А. ЯсЬоп!табе, А. Г. Ж. Охоте!е!т), апт( Е, те!тес Еаэ! А!Вопгбшз (Не!с)е!Ьегб: Яре1стгаш Айат!еш!эс!тег Ъ'ег!аб, 1994), 57.2, приводятся идеи эффективного использования алгоритма для чисел длиной до 1 800 бит. 48. Т = (К, т( †,..., †-т), Кт вот(-ат,..., — ат-т), К„-т(атет,...,атт)л) = (( — 1) Кт т(ат,..., ат т), ( — 1)т тКт ,(ат,...,ат т), К„ 1(ат~.т..... а„)4), 49. Поскольку Лхт + дхт = де и Лх„ет + рх„+т — — — Ле/т1, существует такое нечетное знач. Ие 3', что Лхт+дхт > Ои Лхт,т+дхт,т <О, Если Лхт+Ихт > В н Лхт+э+Ихт+т < -В, то выполняется р > В/х и Л > — В/х вз. Отсюда следует, что 0 < Лх +т + рх +т < Лйхт+тхт/ — Лрхт+тхтег/В < 2Лри/В = 2В, так как для всех /т выполняется [хлетхь] = Кь-т(аз,,аь)К*-т(альт,...,а ) < К„т(ат,...,а„) = е/т!.
[Н. %. Ьепэсга, Лг., Магй. Сотр. 42 (1984), 331-340.] бО. Положим /т = [В/а]. Если Аа < 7, то результат равен !т; в противном случае результат равен /т — 1+ """ "" '"" "'1 а б1. Если ах — глх = у и х Ь у, то имеем х Л шх. Рассмотрим дерево Стерна-Брокота из упр. 40 с заданным дополнительным уздам с меткой О/1. Объединим помеченное значение у = ах — тпх с каждым узлам с меткой х/х. Требуется найти все узлы х/х, для которых у по абсолютной величине не превышает В = т/т/2 и для которых знаменатель х тоже < В. Единственный возможный путь к таким узлам поддерживает положительный маркер влево и отрицательный — вправо.
Это правила определяет единственный путь, который поворачивает вправо, когда лтаркер положительный, вдево — когда маркер отрицательный, н останавливается, когда маркер становится равным нулю. Этот путь неявно поддерживаетсл при выполнении алгоритма 4.5.2Х, когда и = тл и е = а, исключая случай, когда алгоритм "прыгает" вперед — он просматривает узлы только перед тем, как маркер меняет знак (родители узлов "точки превращения", как в упр. 43). Пусть х/х — первый узел пути, маркер которого у удовлетворяет условию [у[ < В. Если х > В, то решения нет, так как соответствующие значения на пути имеют даже ббльшие знаменатели. В противном случае (хх, ху) является решением, полученным при х Л. у.
Легко видеть, что если у = О, то решения ие сутцествует, и что если у 'Ф О, то знак маркера на следуютцем узле пути не будет совпадать со знаком у, Поэтому узел х/х будет обработан алгоритмом 4.5.2Х и для некоторого у' будет выполняться х = хт = Кт т (от,..., ат т ), у = у, = ( — 1) тт '~ К, (а„+ т,..., а„) т1, х = х, = К, э (ат,, а, т ) (см. упр. 48). Следующим подходящим для решения узлом будет узел с меткой х'/х' = (хт-т + )тх,)/(хт-т + ттхт) с маркером у = уз т + /ту;т где !т настолько мало, что ]у'[ < В; отсюда у'у < О.
Однако теперь нужно увеличить В, иначе будем иметь тп = Кл(ат,..., а )тт = х ]у]+ х[у ] < Вт + Вз = тп и неравенство ие будет удовлетворяться. Эти рассуждения доказывают, что задача мажет быть эффективно решена путем применения алгоритма 4.5.2Х для случая, когда и = т и е = а, но при следующей замене операции шага Х2: "Если ез < т/т72, то выполнение алгоритма завершается.
Пара (х, у) = (!сз), сз е!бп(сэ)) является, следовательно, единственным ре~пеннем. обеспечивающим х 1 9 и х < л/ш/2; в противном случае решения нет". (Р. Я. %апб, Еессиге №сат!и Сошр. Ясь'. 162 (1983), 225-235; Р. Когпегир, В. Т. Сгебогу, В1Т 23 (1983), 9 — 20.) Подобный метод будет работать, если потребовать, чтобы 0 < х < В~ и !9! < Вю когда 2В~Вэ < т.
РАЗДЕЛ 4.5.4 1. Если Ыл — не простое число, то его простые множители выделяются перед использованием пробного делителя 4». 2. Нет; при такой модификации в случае, когда р~ ~ — — р», алгоритм сделает ошибку, выдав в качестве простого множителя единицу. 3. Можно взять Р равным произведению первых 108 простых чисел. [Замечание.
Для того чтобы только проверять, является ли число и простым, наименьший общий делитель для 416-разрядного числа Р = 19 590 .. 5 910 мсокет быть вычислен значительно быстрее, чем потребуется для выполнения 168 операций деления.] 4. В обозначениях упр. 3.1 — 11 имеем где /(!) = 2, 20вм""От' ~'л1!. Если ! = 2 еэ при 0 < В < 1, то юбл<г /(!)=! (3.2 — 2 2 ~ ), где функция 3 2 э — 2 2 ы достигает максимума э в точке В = !8(4/3) и имеет минимум, равный 1, при В = 0 и 1.
Поэтому среднее значение величины 2цк""щ"х'лд находится между средними значениями величин р+ 1, умноженными на постоянную в интервале ат 1.0 до 1.125, откуда и следует результат. Замечание. Ричард Брент (ВбсЬагд Вгепс) заметил, что при т †> оо плотность П„(1 — /г/т) = ехр( — !(! — 1)/2тл + О(!з/т~)) стремится к нормальному распределению, поэтому можно положить, что значения В распределены равномерно, Тогда функции 3 2 ~ — 2 2 ы имеет среднее значение 3/(4!и 2), а среднее числа итераций, необходимых для выполнения алгоритма В, стремится к значению (3/(4 !и 2) + 1) л/яш/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с > 1/2 из него исключить поиск наибольшего общего делителя; если выполнение шага В4 повторяется до тех пор,пока не станет удовлетвориться неравенство /с < 1/2, то цикл можно обнаружить и после выполнения последующих Л [с(д)/Л] = с(1г) — (с(д) пюс) Л) итераций.
В этом случае средние затраты приблизительно равны (3/(41п2))~/хщ/2 ш 1.35611~/гт — числу итераций, на которых выполняется вычисление квадрата без вычис- ления наибольшего общего делителя, плюс ((!и я — ~)/(4!в 2) + г) ~/кт/2 .88319т/т— число итераций, на которых выполняются обе операции. [См. анализ Генри Кохева (Невп' Собеп) в А Совгзе )и Сотригабова1 А)бебгшс /гитЬег ТЬеогу (Вег!1в: Брппйег, 1993), з8.5.] 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
