AOP_Tom2 (1021737), страница 88
Текст из файла (страница 88)
[25] (Д. Бейли (П. Вю!еу), П. Борвейн (Р. Вогве!и) н С Плуфф (Я. Р!аиде), 1996.) Поясните, как вычислить и-й бит двоичного представления чигла я, не зная предыдущих и — 1 бит, используя тождество "=Е 1 4 2 1 1 ь>е 16" (8/с -Ь 1 8/с+ 4 8/с+ 5 8/с-!-6) и выполняя 0(п 1о8 и) арифметических операций над О(!об и)-битовыми целыми числами. (Полагаем, что двоичные разряды числа я не содержат слишком длинных строк из нулей нли единиц.) 40. [М24] Иногда возникает необходимость в делении числа и на число о, когда заранее известно, что деление выполнится без остатка. Покажите, что если и есть 2п-разрядное число и о является и-разрядным числом, таким, что и шоб о = О, то можно сэкономить около 75% объема вычислений в алгоритме П, вычислив сначала половину частного, начиная слева направо, а затем другую половину — справа налево. ° 41.
[М20] Во многих приложениях арифметики с высокой точностью требуются повторные вычиглення основания и-разрядного числа в, которое изначально было представлено па основанию Ь. Эти вычисления могут быть ускорены при помощи приема, предложенного Петером Л, Монтгомери (Расее Е. Моасбошегу) [Магб.
Сашр. 44 (1985), 519 — 521]. Он выполнял вычисление остатка справа налево вместо общепринятого направления вычислений слева направо. а) Для заданных чисел и = ш(и ъ„ь., иьис)ь, в = (в ш ..вьвс)ь и чигла в „такого, что всв' шос! Ь = 1, покажите, как вычислить с = х(о„ь...
о~ ос)ь, чтобы выполнялось соотношение Ь~о шос! в = и шод в. Ь) Для заданных и-разрядных целых чисел со знаком и, о и и~ с [и[, [о[ < ш и заданного в~, как в алгоритме (а), покажите, как вычислить и-разрядное целое число 1, такое, что ]с] < в н Ь" С щ ио (по модулю в). с) Как алгоритмы (а) и (Ь) упрощают выполнение арифметических операций по модулю ш? С = ие+ 128, ш ж (((С/256) + С)/255). в4.3.2. Модулярная арифметика Еще один интересный метод выполнения арифметических действий нзд большими целыми числами основан на простых положениях теории чисел.
Идея этого метода состоит в том, чтобы оперировать не непосредственна числом и, а его "остатками" и пюй гпс, и шой гпз,..., и пюй т„, где гпс, тз, ..., т„— "модули", не содержащие общих делителей (т. е. они взаимно просты). Примем для удобства везде в этом разделе следующие обозначения; иг - -и щой тг, ..., и, = и шой гпг. (1) ис = и шайгпс, Числа (ис,из,...,и,) можно легко вычислить путем деления числа и на простые целые числа еь. Важно отметить, что при этом нет никакой потери информации (при условии, чта и не очень велико), так как всегда, зная (ис, из,..., и„), можно восстановить и.
Напрньсер, если 0 < и < е < 1000, нельзя получить (и шой 7, и спой 11, ишой13), которое равнялось бы (епюс17, ешой11, ешой13). Это следствие китайской теоремы об остатках, рассматриваемой ниже. Поэтому (ис,из,...,и,) можно рассматривать как новый тип представления в компьютере — "модулярное представление" целого числа и". Преимущество модулярнога представления заключаетсн в том, что операции сложения, вычитания и умножения выполняются очень просто: (н„...,и„) + (ес,...,е,) = ((и, +ос) гпайтс, ..., (и, +е„) спой то), (и„ ...,и,) — (ес, , е„) = ((и, — ес)пюс1тс, ..., (и, — е„)пюй т„), (им...,и„) х (ем...,е„) = ((ис х ес) гпос1тс,..., (и„х е,) той т„). (2) (3) (4) Для доказательства, к примеру, (4) достаточно показать, что для каждого модуля гп выполняется равенство ие пюй тз = (и шай т/)(е пюс1 т ) пюс1 т .
ь В литературе нв русском языке нсоользувтсв аналогичный по смыслу термин "орвдсгавленнв в остаточных классах". Далее в переводе будет использована терминология оригинала. — Прим, нерво. 42. (НИХ) Обозначим через Р„ь вероятность того, что для заданных гп н Ь выполняется ((ис + -+ и )/Ь") = Ь, где им ..., и — случайные п-рвзрндные целые числа, представленные в системе счисления по основанию Ь.
(Это распределение события ш„в алгоритме сложения в столбик из упр. 2.) Покажите, что Р„ь = — ',(™) + 0(Ь "), где ( ) есть число Эйлера (см. раздел 5.1.3). в 48. (82] Оттенки серого цвета нлн компоненты цветовой гаммы в цифровом виде обычно представляются 8-бнтовымн числами и в интервале (О .. 255), выраженными дробью и/255. По двум таким дробям и/255 н е/255 часто используемые алгоритмы графики приближенно вычисляют ш/255, как ближайшее целое к ие/255. Докажите, что и может быть вычислено по формуле Это равенство следует из основного положения элементарной теории чисел: х шод т, = у пюс1 т, тогда и только тогда, когда х = у (по модулю т ).
Далее, если х ив з х' н у = у', то ху = х'у' (по модулю т;); отсюда следует (и шод т.)(о шод т,) = ии (по модулю т,). Основной недостаток модулярного представления состоит в том, что не так просто проверить, является ли (им..., и„) ббльшим, чем (ом..., о„). Трудно также проверить, возникло ли переполнение в результате выполнения операций сложения, вычитания или умножения, но еще сложнее выполнять операцию деления.
При выполнении такого рода операций в сочетании с операциями сложения, вычитания и умножения применение модулярной арифметики оправдано лишь в том случае, если имеются средства быстрого перехода к модулярному представлению и обратно. По этой причине переход от модулярного представления к позиционным системам счисления н наоборот является одной из основных тем данного раздела.
Операции сложения, вычитания и умножения, основанные на формулах (2)-(4), называются арифметикой остатков или модуляриой арифметикой. Область чисел, над которыми можно выполнять операции модулярной арифметики,— это т = т1тг .. т„(произведение модулей). Если каждое из тэ близко к размеру машинного слова, можно оперировать п-разрядными числами, когда г в и.
Отсюда следует, что при использовании модулярной арифметики общее время, затрачиваемое на выполнение операций сложения, вычитания и умножения с и-разрядными числами, по существу, пропорционально и (не учитывая время, затрачиваемое на переход к модулярному представлению и обратно). При выполнении операций сложения и вычитания применение модулярной арифметики не дает никаких преимуществ, однако при умножении может быть получена значительная выгода, поскольку время выполнения операции умножения традиционным методом, описанным в разделе 4.3.1, пропорционально пэ. Кроме того, на компьютере, в котором предусмотрена возможность параллельного выполнения операций, применение модулярной арифметики дает значительное преимущество даже для сложения и вычитания.
Операции, связанные с разными модулями, могут выполняться одновременно, так что получается реальное повышение ско~юсти их выполнения. Поскольку для традиционного метода, описанного в предыдущем разделе, требуется выполнение переноса разрядов, традиционный метод не позволяет достичь подобного сокращения времени реализации арифметических операций. Возможно, когда-нибудь компьютеры с высокой степенью параллелизма позволят сделать одновременное выполнение операций обычным делом, и тогда модулярная арифметика приобретет важное значение для вычислений в реальном времени, т.
е. в условиях, когда для конкретной задачи требуется дать быстрый ответ с высокой точностью. (При работе на компьютерах с высокой степенью параллелизма часто предпочтительнее одновременно выполнять и отдельных программ вместо того, чтобы выполнять одну программу в )с раз быстрее, поскольку последний подход сложнее в реализации, но никакого повышения эффективности использования компьютера не дает. Вычисления в реальном времени являются тем исключением, при котором параллелизм, присущий модулярной арифметике, приобретает большое значение.) Теперь проанализируем фундаментальное положение, лежащее в основе модулярного представления чисел.
Теорема С (Китайская теорема об остатках). Пусть ты тю..., т„— положи- тельные целые попарно простые числа, т. е. (5) т, ать при1~Й. Пусть т = т~тз...т„н пусть также а, иы ию ..., и„— целые числа. Тогда существует ровно одно целое число и, удовлетворяющее условиям а<и<а+т и иьз и. (помодулют) при1<1<г. (6) Доказатпельство. Если и = с (по модулю т,) при 1 < 1 < г, то и — с кратно т, для всех з.
Тогда из условия (5) следует, что и — с кратно т = т,тз... т„. Значит. уравнение (6) имеет нс более одного решения. Для завершения доказательства необходимо показать, что существует по меньшей мере одно решение. Это можно сделать двумя простыми способами. Способ 1 (кНеконструктивное" доказательство). Так как и принимает т различных значений а < и < а + т, наборы из г чисел (и шобгпп.... ишоб т„) также должны принимать т различных значений (поскольку уравнение (6) имеет не более одного решения). Но имеется ровно тратт... т„возможных г-наборов (сы..., гг), таких, что 0 < о, < т, Поэтому каждый г-набор должен встречаться точно один раз и должно существовать такое значение и, для которого (и шос1ты ...,ишобт„) = (им...,и„). Способ 2 (" Конструктивное" доказательство).
Можно найти числа ЛХ при 1 < 1 < г, такие, что Мз = 1 (по модулю тз) и М1 мО (по модулю ть) для Й г-у. (7) Действительно, из (5) следует, что т и т/т взаимно просты, а потому согласно теореме Эйлера (упр. 1.2.4 — 28) можно взять М. = (т/тз)"1 (8) Теперь число (9) и = а+ ((и~ЛХ~ + игМз+ + и„̄— а) пюс1т) удовлетворяет всем условиям (6). ! Частный случай этой теоремы был сформулирован китайским математиком Сунь Пу, который предложил правило, названное "тай-йен" (" большое обобщение" ). Дата написания его работы точно не установлена; предположительно — между 280 и 473 г. н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
