Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 88
Текст из файла (страница 88)
" В литературе ка русском языке исеольэуетгя аиалогичимя со смыслу терман "представление в остаточных классах". Деды в переводе будет использована терминология оригинала. — Прем, яезее. 42. (зги] Обозначям через Р„ь вероятность гого, что для зздеивмх гл н Ь выполняется ((и~ +" + и,)/Ь") = Гс, где им,, в — случайные и-разрядные целые числа, представленные в системе счисления по основанию Ь.
(Это распределение события ш„в алгоритме сложениЯ в столбик нз УпР. 2,) Покажите, что Р„ь = -~~(, ) + О(Ь "), где ( ь) есть число Эйлера (см, раздел 5.1.5). ь 48. [22) Оттенки серого цвета нзи компоненты цветовой гаммы в цифровом виде обычно представляются 8-битовыми числами и в кнтервале (О., 255), выраженными дробью и/255. По двум таким дробям и/255 и с/255 часто используемые алгоритмы графики приближенно вычисляют и/255, как ближайшее целое к ие/255.
Докажите, что и может быть вычислено по формуле Это равенство следует из основного положения элементарной теории чисел: х пкк1 шу = ршоо ту тогда и только тогда, когдал эз у (по модулю ш,). Далее, если х гн х' и у ьз у', то ху эз х'у' (по модулю шу); отсюда следует (и той т )(и шоб т ) гн ие (по модулю пт ). Основной недостаток модулярного представления состоит в том, что не так просто проверить, является ли (им..., и„) ббльшим, чем (еы..., е„). Трудно также проверить, возникло ли переполнение в результате выполнения операций сложения, вычитания или умножения, но еще сложнее выполнять операцию деления.
При выполнении такого рода операций в сочетании с операциями сложения, вычитания и умножения применение модулярной арифметики оправдано лишь в том случае, если имеются средства быстрого перехода к модулярному представлению и обратно. По этой причине переход от модулярвого представления к позиционным системам счисления и наоборот является одной из основных тем данного раздела. Операции сложения, вычитании и умножения, основанные на формулах (2)-(4), называются арифметикой остатков или модуллрной ерифмешяяей. Область чисел, нед которыми можно выполнять операции мпдулярной арифметики,— зто т = тате... т„(произведение модулей).
Если каждое из шу близко к размеру машинного слова, можно оперировать и-разрядными числами, когда г и. Отсюда следует, что при использовании модулярной арифметики общее время, затрачиваемое на выполнение операций сложения, вычитания и умножения с и-разрядными числами, по существу, пропорционально и (не учитывая время„затрачиваемое на переход к модулярному представлению и обратно). При выполнении операций сложения и вычитания применение модулярной арифметики не дает никаких преимуществ, однако при умножении может быть получена значительная выгода, поскольку время выполнения операции умножения традиционным методом, описанным в разделе 4.3.1, пропорционально пз, Кроме того„на компьютере, в котором предусмотрена возможность параллельного выполнения операцвй, применение модулярной арифметики дает значительное преимущество даже для сложения и вычитания.
Операции, связанные с разными модулями, могут выполняться одновременно, так что получается реальное повышение скорости их выполнения. Поскольку для традиционного метода, описанного в предыдущем разделе, требуется выполнение переноса разрядов, традиционный метод не позволяет достичь подобного сокращения времени реализации арифметических операций. Возможно, когда-нибудь компьютеры с высокой степенью параллелизма позволят сделать одновременное выполнение операций обычным делом, и тогда молулярная арифметика приобретет важное значение для вычислений в реальном времени, т. е. в условиях, когда для конкретной задачи требуется дать быстрый ответ с высокой точностью.
(При работе на компьютерах с высокой степенью параллелизма часто предпочтительнее одновременно выполнять й ошдельнмя программ вместо того, чтобы выполнять одкя программу в я раз быстрее, поскольку последний подход сложнее в реализации, но никакого повышения эффективности использования компьютера не дает.
Вычисления в реальном времени являются тем исключением, при котором параллелизм, присущий молулярной арифметике, приобретает большое значение.) Теперь проанализируем фундаментальное полажение, лежащее в основе модулярного представления чисел. Теорема С (Китайская теорема об остатках). Пусть»пм т», ..., т, — положи- тельные целые попарно простые числа, т. е.
(о) т ~те при» ~Ь. Пусть т = т»тэ...т„н пусть также а, и», из, ..., и„— целые числа. Тогда существует ровно адно целое число и, удовлетворяющее условиям а < и < а + т и и гя и» (по модулю»п;) при 1 <» <».. (6) Доказательство. Если и ьз е (по модулю т.) при 1 < ! < г, то и — е кратно т для всех !. Тогда из условия (5) следует, что и - о кратно т = т»тэ... т„. Значит, уравнение (6) имеет не более одного решения. Для завершения доказательства необходимо показать, что существует»ю меньшей мере одно решение. Это можно сделать двумя простыми способами.
Способ 1 (кНеконструктивное" доказательство). Так как и принимает т различных значений а < и < а + т, наборы из г чисел (итог ты, ..,и пюб т„) также должны принимать т различных значений (поскольку уравнение (6) имеет не болев одного решения). Но имеется ровно т»тэ... т, возможных»-наборов (о»,..., в„), таких, что 0 < в < т,.
Поэтому каждый г-набор должен встречаться точно один раз и должно существовать такое значение и, для которого (ишоб т»,... » и гпо'1 тг) = (и» ~ ° . ~ ~ь) . Способ 2 (" Конструктивное" доказательство). Можно найти числа М при 1 < » < г, такие, что М! эз 1 (по модулю т,) и ЛХ, эз 0 (по модулю ть) для Ь ~1. (7) Действительно, из (5) следует, что т и т/т, взаимно просты, а потому согласно теореме Эйлера (упр. 1.2.4-28) можно взять Иу =(т(т») !™ 1.
(8) Теперь число а+ ((и!М! + изМ2+ "'' + игмг а) шо )т) (9) удовлетворяет всем условиям (6). ! Частнь»й случай этой теоремы был сформулирован китайским математиком Сунь Цу, который предложил правило, названное "тай-йен" (" большое обобщение" ). Дата написания его работы точно не установлена; предположительно — между 280 и 473 г. н.
э. Дальнейшее развитие эта задача получила в работах математиков средневековой Индии„предложивших методы кр»п»лака !Ьи(!айа»' (см. раздел 4.5.2). Однако в общем ви,пе теорема С впервые была сформулирована и доказана Чин Чжу-Шао в работе ВЬп ЯЬп СЫп СЬвпб (1247), в которой рассмотрен также случай, когда модули могут иметь общие множители (как в уир. 3). [См. д. »чеепйаш, Яс!енсе аЫ С!т!)!гвг!оп ш СИпа 3 (СашЬгЫВе 1)шчегэ)су Ргевв, 1959), 33-34, 119-120; У.
11 апд Б. 11и, СЬ!пеэе Ма1Ье»па!!сэ (Ох!ох»1: С!вхепдоп, 1987), 92-94, 105, 161-166; К. БЬеп, .4гсЬ1ге й»г Н!эй»гу ог" Ехасг бс!евсея 38 (1988), 285-305.[ Многочисленные исследования, посвященные этой теории, обобщены Л. Ю. Диксоном (1. Е. П(сйэоп) в книге Н!в!агу ог гЬе ТЬеогу ог ЖпшЪе»э 2 (Сагпеб)е )пэс. ог'ЪЧаэМпйсоп, 1920), 57-64. Как следует из теоремы С, мцлулярное представление можно использовать для чисел в любом соответствующем интервале т = т1тт...т„целых чисел.
Например, можно в (б) взять а = 0 и работать только с неотрицательными целыми числами и, меньшими т. С другой стороны, при вьпюлнепии операций сложения и вычитания, так же, как и умножения, обычно удобнее всего предположить, что все модули тм тз, ..., т„являются нечетными числами, так что и т = т1тз... т,, тоже нечетное, и работать с целыми числами из интервала т т — — <и< —, (10) 2 2' симметричного относительна нуля. Для выполнения основных операций, перечисленных в (2) — (4), иеобходимо вычислить (из+из) шоб т, (и — хз) гпоб т и иге пюб т при 0 < ит, иг < ту. Если глз — число однократной точности, то лучше всего формировать иус9 шоб гпз путем умножеиия н последующего деления.
Что касается операций сложения и вычитания, то здесь ситуация проще„так как не требуется деление; удобно рассматривать следующие формулы: (и, + ву) шод т„= и, + из — ту(из + и, > т,!. (1Ц (и. — иу) пюд т = и — и- + т;(иГ < из]. (12) (См.
раздел 3.2.1.1.) Поскольку желательио, чтобы ю было как можно ббльшим, проще всего принять т1 наибольшим нечетным числом, соответствующим машинному слову, в качестве тз принять наибольшее нечетвое число < тм взаимно простое с тм а в качестве тз — иаиболыпее нечетное число < тт, взаимно простое как с тм так и с тз, и т. д., пока не наберется столько т, сколько будет достаточно д чя образования нужного гп. Способы эффективного определения „являются ли два числа взаимно простыми, рассматриваются в разделе 4.5.2. В качестве простого примера предположим, чтб имеется десятичный компьютер со словом, содержащим дае цифры, так что размер слова равен 100. Тогда в результате только что описанной процедуры получаем т1 =99, газ =97, тз =95, т, =91, ть =89, те =83 (13) и т.
д. При работе иа двоичных компьютерах иногда желательно выбирать модули тг иным образом: т =2" — 1. (14) Другими словами, значение каждого модуля на едипицу меньше очередной степени 2. Такой выбор зиачения модуля т, зачастую упрощает выполнение основных арифметических операций, ибо выполнять вычисления с числами, представленными по модулю 2м — 1, несколько проще, чем с числами, представленными в обратном коде. После того как значения модулей выбраны таким образом, полезно несколько ослабить условие 0 < иу < тЗ и потребовать только, чтобы 0 < и, < 2'~, иу гв и (по модУлю 2еч — 1), (15) Таким образом, значение и = т = 2м — 1 принимается в качестве оптимального вместо иу = О, поскольку это, с одной стороиы, ие влияет на справедливость теоремы С, а с другой — означает, что и, может быть любым е -битовым двоичиым числом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
