Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 56
Текст из файла (страница 56)
РАЗДЕЛ 3.2.1 1. Выберите числа Ле и а четными, а с — нечетным. Тогда Х„будет нечетным при и > О. 2. Пусть Х, является первым повторившимся значением последовательности. Если Х, равно Хь для некоторого А, где 0 < А < г, можно доказать, что Х,-~ = Хь-и так как Х„ единственным образом определяет Х„н где а взаимно просто с гл. Отсюда А = О. 3. Если 4 — наибольший общий делитель а и т, величина аХ может принимать не более т/Ы значений. Возможна даже худшая ситуация; например, если т = 2' н а— четное число, формула (б) показывает, что последовательность в конечном счете являетсл константой. 4.
Индукция по й. 5. Если числа а и ш взаимно простые, то существует число а', для которого аа' ш 1 (по модулю т). Тогда Х„~ ж (а'Մ— а'с) шоб т и в общем случае Х„ь ж ((а') Մ— с(а + . + (а') )) шоб ш = ~(а')'Х, + ((а')" — И5) б гле А > О, и — А > О. Если а и ш не являются взаимно цростымн числами, то определить Х„м когда задано Х„, невозможно; числа, кратные шфбсд(а, гл), могут быть добавлены к Х„~ без изменения величины Х„. (См. также упр. 3.2.1.3-7.) РАЗДЕЛ 3.2.1.1 1.
Пусть с' — решение уравнения ас' ш с по модулю ш. (Так, с' = а'с шог( ти, если а'— число в ответе к упр. 3,2.1-5.) Тогда 50А 1; МВ СР8188: НШ. А Переполнение возможно на операции суммирования. (Из результатов, полученных ниже в этой главе, следует, что, возможно, лучше сберечь единицу времени, положив с = а и заменив операцию АОО операцией "18СА 1".
Затем, если Лэ = О, переполнение не произойдет до конца периода, так что практически его не будет.) Ть ЯАНОМ 871 1ОА НШ. ИЬАХ АОО ОТА 1Н уйбт 1НР ХНАИО СОИ 2Н СОИ ЗН СОИ 1Р ХИАИО йр б ЗР (Или 1ИОА с, если с малб) ХИАИО е-1 Хе а с $ 3. Пусть а' = амшобт и пусть гл' таково, что тт' ш 1 (по модулю ю). Положим у <- !опш!1(а',х), х <- ь!ши!1(а',х), ! <- !оши!1(т',у), и < — ь!п1и!1(т,1). тогда получим т! ш а'х (по модулю ю). Значит, а'х — пп = (х — и)ю и ах ш х — и (по модулю т); отсюда следует, что ах шод т = х — и + [х с и[т. 4. Определим операцию х щи!! 2' = у тогда и только»гда, когда х ги у (по модулю 2') н -2' ч у < 2', Конгруэнтнав последовательность (1„), определенная следующим образом 1е = Хе, щог! 2 К, ~ = (аУ„ч с) щог! 2ш легко вычнслиется на машинах серии Бузсеш/370, так как младшие разряды произведе- ния у н х равны (ух) щог) 2 лчя всех двоичных дополнений чисел у и х; и поскольку прн суммировании не принимается во внимание переполнение, она также представляет результат сравнимым по щой 2з~.
Эта последовательность обладает всеми свойства- ми случайности стандартной линейной конгрузнтной последовательности (Л„), так как У„ш Х„по модулю 2з~. В самом деле, представление в аиде двоичного дополнения У„ идентично двоичному представлению Л„для всех и. [Дж. Марсалья (С. Магэаб!!а) и Т. Л. Брей (Т. А. Вгау) впервые подчеркнули это в САСМ 11 (1968), 787-759,) б.
(а) Вычитание: 1ОА Х; 809 7; 1АИИ ь+2; АОО Н, (Ь) Суммирование: ЬОА Х; 909 Н; АОО Т; 1АИИ в+2 ! АОО Н. (Заметим, что если т больше половины длины слова, то операция "ВОВ Н" должна предшествовать операции "АОО Т",) 6. Этн последовательности мало различаются, так как добавление константы (т — с) дает тот же эффект, что н вычитание константы с. Данная операция должна сочетаться с операцией умножения, так что процесс вычитания имеет небольшие преимущества перед процессом сложения (по крайней мере, для машины Н1Х). Исключение составляет случай, когда необходимо избежать переполнения, 7. Простые делители х — 1 появляются в факторизации х ' — 1. Если г нечетное, то ь ь простые делители я~+1 появляются в факторизации х"'+ 1 и х " — 1 равно (х~ — 1)(я~+ 1).
8. 107 я+1 (Убедитесь, что переполнение выключено.) ЬОА Х НШ А ОТХ ТЕНР АОО ТЕНР Добавить млазшие разрядм к старшим. 1ИОУ я+2 Если > ю, вычесть ю — 1. 1ИСА 1 (Переполнение невозможно на этом шаге.) $ Замечание. Так как суммирование на е-разрядном компьютере с единичным дополненкем производится по пьх! (2' — 1), то можно комбинировать технику из упр. 4 и 8, выполняя и1ервцию (уг) пни! (2' — 1) путем суммирования двух е-разрядных половин произведения ух для всех едяннчно дополненных чисел у и х, не обращая внимания на знак. 9.
(а) Обе части равеэктва совпадают с выражением од[с/д]. (Ь) Положим 1 ь- а(х шод д) — г] х/д), где г ж ш пюб а; константы д я г могут быть вычислены заранее, Тогда ах шоб т = Ф + [1 < 0]ш, так как можно доказать, что 1 > -т. Ясво, что а(х своб 4) < а(д — 1) < гл. Также г[х/д) < г[(па — 1)/д] = г[о + (г — 1)/д) = ги < да < т, если О < г < д; и ат < гл влечет г < а < д.
[Эта методика в неявном виде использована в программе, опубликоваииой Б. А. Викмаиом (В. А. %)сЬщавп) и Я. Д. Хиллом (1. П. Н1П): Аррбес( бсаа 31 (1982), 190.] 10. Если г > д и х = т — 1, то г[х/д] > (9+ 1)(а+ 1) > т. Итак, условие г < д необходимо и достаточно для применения метода из упр. 9, (Ь). Подразумевается, что — — 1 < а < -"'. Пусть 1 = [,/т ]. Интервалы [щ — 1 .. ш] ие пересекаются при 1 < д < 1 и обязательно включают 1 иля 2 целых числа в зависимости от того, будет ли д делителем т. Эти иитервалы дают все решения с а > ~/т; оии также включают случаи для а = Ь если (т/тшоОЦ < —, и а = 1 — 1, если т = 1".
Таким образом, общее число 'удачных" множителей точно равно 2[т/т] + [6(т)/2] — [(~/т щи 1) < -'] — 1, где д(ш) — число делителей т. 11. можио предположить, что а < -'пц1 ииаче можно получить ахпнк1тл из (га — а)х шоп га. Тогда можно представить а = а'а" — а'", где все числа а', а" и а'" меньше ~/т; например, можно взять а' - т/т — 1 и а" = [а/а'].
Следовательно, ахпюдш равно (а'(а"х щи гл) пюб гп — (а"'х шоб т)) пюб т и все три виутреиние операции могут быть заимствованы из упр. 9. Когда т = 2 — 1, можно воспользоваться тем, что гп — 1 имеет 192 делители, для зг определения случаев, в которых ш = д'а'+1. При этом упрощается общий метод, так как г' = 1. Кроме того, 86 из этих делителей ведут к удачным а" и а"', когда а = 62089911.
Наилучшим из этих случаев будет, вероятно, случай, когда а' ж 3641, а" = 17053, уча = 62, потому что гп — 1 делится как па 3641, так и на 62. Это разложение осуществляется по схеме 1 ь- 17053(х щи 125929) — 16410[к/125929], 1 с- 3641(1 шоб 589806) — [1/589806], 1 < — 1 — (62(х шод 34636833) — [х/34636833] ), где "-" обозначает вычитание по модулю га.
Операция сравнения по модулю рассматри- вается как две операции — умножения и вычитания. Поскольку хшобд = х — д[х/д] и операция [х/д] уже выполнеиа, то совершено семь умножений, три деления и семь вычитаний. Заметим. что число 62089911 имеет 24 делителя; оии позволяют получить пять подходящих факторизаций с а"' = О. Например, когда а' м 883 и а" = 70317, достаточно только шести умножений, двух делений, четырех вычжаиий: 1 е- 883(х шоб 2432031) — 274 [х/2432031], «- 70317(1 6 30540) - 2467[1/30540] . [Может ли наихудшее число умножений и делений быть сведено максимум к 11 для всех а и ш, либо 12 является наилучн~ей веркией границей? Другой способ достичь значеияя 12 приведен в упр.
4.3.3 — 19.] 12. (а) Пусть т = 9999998999 = 10'е — 10* — 1, Чтобы умножить (хехз..*хе)~е на 10 по модулю ш, используем тот факт, что 10'ехв ш 10~хе + хе: добавим (хзООО)зе к (хехт ..хесе))е. Чтобы избежать циклических сдвигов, представим, что цифры упорядочены на круге. Добавим цифру высшего порядка хз к цифре хз, переместим иа три позиции влево и рассмотрим хз как новую цифру высшего порядка, Если хе + хз > 10, то перенос совершается влево. И если этот перенос покрывает весь путь влево от хв, ои совершается ие только к позиции хе, но и к позиции хз. Он может распространяться от хз и хг до тех пор, пока процедура не остановится.
(Числа также могут не намного превышать т. Например, 0999999900 переходит в 9999999000 = тп+ 1, которая переходит в 9999999009 = и!+10. Но избыточное представление пе является обязательно пагубным.) (Ь) Это операция деления иа 10, Выполняем процедуру, обратную процедуре (а): перемещаем цифру высшего порядка елена и емчитваем новую цифру высшего порядка от третьей цифры слева, Если результат вычитания отрицателен, выполняем»заимствование» обычным способом (алгоритм 4.3.18), т, е.
умеиыпаем предыдущую цифру на 1. Заимствование может распространяться, как в (а), но не эа позицию цифры высшего порядка. В результате этой операции числа сохраняются неотрицательными и меньшими, чем т. (Таким образом, деление на 10 выполняется проще умножения на 10.) (с) Можно завоз!нить заимствованный бит вместо того, чтобы распространять его, потому что он может быть включен в процесс вычитания на следующем шаге.
Таким образом, есля определить цифру х„и заимствованные биты Ь рекуррентной формулой х» = (х»-те — х»-3 — Ь,) шос) 10 = в»-!е — х»-з -Ь + 10Ь +г, то, используя индукцию по и, можно получить 9999999000" пкн1 9999998999 = Х», где Х» = (х»-тх»-гх»-зх»-зх»-зх»-ех»-тх»+гх»»тх»)та — 1000Ь +з = (х — !я»-г ° ° х»-ге) ге (х»-! !»-гх»-3) те Ь» при начальных условиях Хе = 1. Заметим, что 10Х»+! = (х»х» гх»-гх»-зх»-зх»-зх»-зх»»зх»+гх»+гО)ге — 10000Ь»»з»» тлх» + Х»; следовательно, 0 < Х» < тл для всех и > О. (с() Если 0 < (т' < тл, первая цифра десятичного представления У/тл равна (10бт/т) и последующие цифры являются десятичным представлением (10(/ шод вз)/т (см,, например, метод 2, а в разделе 4.4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
