34. [40] Разработайте набор машинных подпрограмм для выполнения четырех арифметических операций над произвольными целыми числами без ограничений их величины, но с учетом ограничения общего объема оперативной памяти компьютера. (Используйте связное распределение памяти так, чтобы время на поиск места для хранения результата совсем не тратилось.)

35. [40] Разработайте набор подпрограмм для "плавающей арифметики десятикратной точности", используя девятиразрядное представление чисел с плавающей точкой по основанию b с избытком О, где 6 равно длине машинного слова, и выделяя для порядка полное слово. Таким образом, каждое число в формате с плавающей точкой записывается в 10 словах памяти и общее масштабирование выполняется посредством сдвигов машинных слов целиком вместо сдвигов внутри слов.)

36. [М25] Поясните, как с высокой точностью вычислить In ф по заданному с соответствующей точностью приближению числа ф, используя только операции сложения и вычитания многократной точности и деления на короткие числа.

► 37. [20] (Ю. Саламин (Е. Salamin).) Объясните, как в алгоритме D при его реализации на двоичном компьютере запретить нормализацию и денормализацию, не изменяя порядка попыток вычисления разрядов частного, если число d представлено по степеням 2. (Как можно на шаге D3 вычислить q, если на шаге D1 не была выполнена нормализация?)

38. [Л/55] Предположим, что и иь - целые числа в интервале О < u,v < 2". Предложите способ вычисления среднего геометрического [\/uv+\ при помощи 0{п) операций сложения, вычитания и сравнения (тг + 2)-битовых чисел. [Указание. Объедините классические методы умножения и извлечения корней, используя "конвейер".]

39. [25] (Д. Бейли (D. Bailey), П. Борвейн (Р. Borwein) и С. Плуфф (S. PlouflFe), 1996.) Поясните, как вычислить тг-й бит двоичного представления числа тг, не зная предыдущих тг - 1 бит, используя тождество

W 4 2 1 IN

16*\8А; + 1 8А; + 4 8А; + 5 8А; + б/

и выполняя 0(тгIogтг) арифметических операций над 0(Iog тг)-битовыми целыми числами. (Полагаем, что двоичные разряды числа тг не содержат слишком длинных строк из нулей или единиц.)

40. [М24] Иногда возникает необходимость в делении числа и на число v, когда заранее известно, что деление выполнится без остатка. Покажите, что если и есть 2тг-разрядное число и V является тг-разрядным числом, таким, что и mod v = О, то можно сэкономить около 75% объема вычислений в алгоритме D, вычислив сначала половину частного, начиная слева направо, а затем другую половину - справа налево.

► 41. [М26] Во многих приложениях арифметики с высокой точностью требуются повторные вычисления основания тг-разрядного числа w, которое изначально было представлено по основанию Ь. Эти вычисления могут быть ускорены при помощи приема, предложенного Петером Л. Монтгомери (Peter L. Montgomery) [Math. Сотр. 44 (1985), 519-521]. Он выполнял вычисление остатка справа налево вместо общепринятого направления вычислений слева направо.

a) Для заданных чисел и = ±{um+n-i uiUo)b, и> = (Wn-i wiWo)b и числа w, такого, что wow mod6 = 1, покажите, как вычислить v - ±{vn~i ViVo)b, чтобы выполнялось соотношение b"v mod w = и mod w.

b) Для задгшных тг-разрядных целых чисел со знаком и, v ию с \и\, \v\ < w и заданного w, как в алгоритме (а), покажите, как вычислить тг-разрядное целое число t, такое, что t < w и b"t - uv (по модулю w).

с) Как алгоритмы (а) и (Ь) упрощают выполнение арифметических операций по модулю ги?

42. [НМ35] Обозначим через Рпк вероятность того, что для заданных т и b выполняется [{щ Н-----(- Um)/b"\ = к, где т, ..., Um -случайные тг-разрядные целые числа, представленные в системе счисления по основанию Ь. (Это распределение события Wn в алгоритме сложения в столбик из упр. 2.) Покажите, что Р„к = + 0{b~"), где (J) есть число

Эйлера (см. раздел 5.1.3).

► 43. [22] Оттенки серого цвета или компоненты цветовой гаммы в цифровом виде обычно представляются 8-битовыми числами и в интервале [О .. 255], выраженными дробью и/255. По двум таким дробям и/255 и v/255 часто используемые алгоритмы графики приближенно вычисляют w/255, как ближайшее целое к uv/255. Докажите, что w может быть вычислено по формуле

t = uv + 128, W = L(U/256J + t)/256j.

"4.3.2. Модулярная арифметика

Еще один интересный метод выполнения арифметических действий над большими целыми числами основан на простых положениях теории чисел. Идея этого метода состоит в том, чтобы оперировать не непосредственно числом и, а его "остатками" и mod mi, и mod тг, ..., и mod гПг, где mi, тг, гпг - "модули", не содержащие общих делителей (т. е. они взаимно просты). Примем для удобства везде в этом разделе следующие обозначения:

«1= и mod mi, И2 = иnlodmг, Ur = и mod гПг. (!)

Числа (ui,U2,... ,Ur) можно легко вычислить путем деления числа и на простые целые числа Vk. Важно отметить, что при этом нет никакой потери информации (при условии, что и не очень велико), так как всегда, зная («1, «г, • •, «г), можно восстановить и. Например, если О < и < v < 1000, нельзя получить (и mod 7, и mod И, и mod 13), которое равнялось бы (v mod 7, v mod И, v mod 13). Это следствие китайской теоремы об остатках, рассматриваемой ниже. Поэтому (ииг, • • •, «г) можно рассматривать как новый тип представления в компьютере - "модулярное представление" целого числа и*.

Преимущество модулярного представления заключается в том, что операции сложения, вычитания и умножения выполняются очень просто:

{ui,...,Ur) + {vi,...,Vr)-= {{ui +vi) mod mi, ..., (ur + Vr) modm), (2) (ui,...,Ur) - {vi,...,Vr) = ((ui -ui)modmi, {ur - Vr) mod Шг), (3) (ux,... ,Ur) У- (vi,... ,Vr) ((ui X Vl) mod mi, ..., («г x Vr) mod тпг). (4)

Для доказательства, к примеру, (4) достаточно показать, что для каждого модуля rrij выполняется равенство

UV mod mj = (и mod m.j){v mod mj) mod mj.

* В литературе на русском языке используется аналогичный по смыслу термин "представление в остаточных классах". Далее в переводе будет использована терминология оригинала. - Прим. перев.

Это равенство следует из основного положения элементарной теории чисел: х mod rUj = у mod rtij тогда и только тогда, когда х = у (по модулю rrij). Далее, если х = х и у = у, то ху = ху (по модулю nij); отсюда следует (wmodmj)(t; modmj) = uv (по модулю rUj).

Основной недостаток модулярного представления состоит в том, что не так просто проверить, является ли («1,..., Ur) большим, чем {vi,...,Vr). Трудно также проверить, возникло ли переполнение в результате выполнения операций сложения, вычитания или умножения, но еще сложнее выполнять операцию деления. При выполнении такого рода операций в сочетании с операциями сложения, вычитания и умножения применение модулярной арифметики оправдано лишь в том случае, если имеются средства быстрого перехода к модулярному представлению и обратно. По этой причине переход от модулярного представления к позиционным системам счисления и наоборот является одной из основных тем данного раздела.

Операции сложения, вычитания и умножения, основанные на формулах (2)-(4), называются арифметикой остатков или модулярной арифметикой. Область чисел, над которыми можно выполнять операции модулярной арифметики, - это т = mim.2 .. .Шг (произведение модулей). Если каждое из m,j близко к размеру машинного слова, можно оперировать п-разрядными числами, когда г » п. Отсюда следует, что при использовании модулярной арифметики общее время, затрачиваемое на выполнение операций сложения, вычитания и умножения с п-разрядными числами, по существу, пропорционально п (не учитывая время, затрачиваемое на переход к модулярному представлению и обратно). При выполнении операций сложения и вычитания применение модулярной арифметики не дает никаких преимуществ, однако при умножении может быть получена значительная выгода, поскольку время выполнения операции умножения традиционным методом, описанным в разделе 4.3.1, пропорционально п.

Кроме того, на компьютере, в котором предусмотрена возможность параллельного выполнения операций, применение модулярной арифметики дает значительное преимущество даже для сложения и вычитания. Операции, связанные с разными модулями, могут выполняться одновременно, так что получается реальное повышение скорости их выполнения. Поскольку для традиционного метода, описанного в предыдущем разделе, требуется выполнение переноса разрядов, традиционный метод не позволяет достичь подобного сокращения времени реализации арифметических операций. Возможно, когда-нибудь компьютеры с высокой степенью параллелизма позволят сделать одновременное выполнение операций обычным делом, и тогда модулярная арифметика приобретет важное значение для вычислений в реальном времени, т. е. в условиях, когда для конкретной задачи требуется дать быстрый ответ с высокой точностью. (При работе на компьютерах с высокой степенью параллелизма часто предпочтительнее одновременно выполнять к отдельных программ вместо того, чтобы выполнять одну программу в к раз быстрее, поскольку последний подход сложнее в реализации, но никакого повышения эффективности использования компьютера не дает. Вычисления в реальном времени являются тем исключением, при котором параллелизм, присущий модулярной арифметике, приобретает большое значение.)

Теперь проанализируем фундаментальное положение, лежащее в основе модулярного представления чисел.