► 14. [М27] (А. Шёнхаге (А. Schonhage).) При большом п время, необходимое для выполнения преобразования п-разрядного целого числа рассмотренным в разделе методом преобразования целых чисел многократной точности, имеет порядок п. Покажите, что п-разрядное целое число можно перевести в двоичный формат за 0{M{n)logn) шагов, где М(п) - количество циклов, необходимых для выполнения операции умножения п-битовых чисел, которые удовлетворяют "условиям гладкости" М(2п) > 2М{п).

15. Можно ли существенным образом понизить верхнюю грань времени выполнения преобразования больших целых чисел, данную в упр. 14? (См. упр. 4.3.3-12.)

16. [41] Постройте быструю линейную итерационную конфигурацию для преобразования чисел из десятичной системы счисления в двоичную (см. раздел 4.3.3Е).

17. [М40] Разработайте "идеальные" подпрограммы, выполняющие преобразования чисел с плавающей точкой, которые переводили бы р-разрядные десятичные числа в Р-раз-рядные двоичные числа и наоборот, выдавая в обоих случаях правильный округленный результат в терминах раздела 4.2.2.

18. [НМЗ4] (Дэвид В. Матула (David W. Matula).) Пусть roundb(u,p) - функция 6, u и р, которые являются наилучшим приближением р-битового числа и с плавающей точкой, представленного в системе счисления по основанию b в смысле раздела 4.2.2. Предполагая, что logg b иррационально и что целаячасть принадлежит бесконечному интервалу, докажите, что

и = roundb (rounds (и, Р),р)

для всех р-битовых чисел и с плавающей точкой, представленных по основанию 6 тогда и только тогда, когда В~ > Ь. (Другими словами, "идеальное" входное преобразование произвольного числа и в представление по независимому основанию В и выполняемое после него "идеальное" выходное преобразование этого результата всегда снова даст число и тогда и только тогда, когда промежуточная точность Р будет достаточно большой, как определено вышеприведенной формулой.)

19. [MZ3] Предположим, что десятичное число и = {щ ... uiuo)io представлено как двоично-закодированное десятичное число U = (и? .. • И1Ио)1б. Найдите соответствующие константы Ci и маски тщ, такие, что операция U <- U - Ci{U Л тщ), повторенная для г = 1, 2,3, переводит число U в двоичное представление числа и, где "Л" означает извлечение (побитового AND).

4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ

При решении вычислительных задач зачастую важно знать, чем выражается результат: точным числом (например, 1/3) или числом с плавающей точкой (например, "0.333333574"). Если арифметические операции выполняются над дробями, а не над приближениями к ним, то при выполнении большинства вычислений совершенно не накапливаются ошибки округления. Это порождает чувство спокойной уверенности (которое часто отсутствует при вьшолнении операций над числами с плавающей точкой), что точность вычислений больше повышена быть не может.

4.5.1. Дроби

При вьшолнении арифметических операций над дробями числа могут быть представлены в виде пары целых чисел {и/и), где и и и взаимно просты и и > 0. Число нуль представляется как (0/1). В таком представлении {и/и) = {v/v) тогда и только тогда, когда и = v и и = v.

Перемножать дроби, конечно, просто. Чтобы найти {и/и) х {v/v) - {w/w), можно просто вычислить UV и uv. Два произведения uv и uv могут не быть взаимно простыми, но если обозначить d = gcd{uv,uv)*, то искомый результат будет равен w = uv/d, w = uv/d (см. упр. 2). В разделе 4.5.2 рассматривается эффективный алгоритм вычисления наибольшего общего делителя.

Дроби можно перемножить и другим способом, который состоит в том, что находятся значения di = gcd(u,u) и = gcd{u,v); тогда результатом будет W = {u/di){v/d2), ю = {u/d2){v/dl) (см. упр. 3). При перемножении дробей этим методом необходимо вычислить два наибольших общих делителя, но в действительности вычисления по такому методу выполняются не дольше, чем по первому. В процессе нахождения наибольшего общего делителя осуществляется ряд итераций, количество которых фактически пропорционально логарифму входных чисел, так что количество итераций, необходимых для получения чисел di и 2, по существу, равно количеству итераций, необходимых для вычисления одного числа d. Более того, каждая итерация при определении di и d2, видимо, выполняется быстрее, так как рассматриваются сравнительно малые числа. Если и, и, v и v -.величины с однократной точностью, то этот метод имеет преимущество по сравнению с первым, поскольку, если только допускается представление чисел w и w с однократной точностью, в вычислениях совсем не участвуют числа с удвоенной точностью.

Деление может быть выполнено аналогично (см. упр. 4).

Операции сложения и вычитания дробей немного сложнее. Обычная процедура заключается в том, что принимается {и/и) ± {v/v) = {{uv ± uv)/uv), а затем данная дробь приводится к несократимому виду. При этом используется, как и в первом методе, наибольший общий делитель d = gcd{uv ± uv, uv). Но, опять же, можно избежать действий со столь большими числами, если начать с вычисления dl = gcd(u, v). При dl = 1 искомыми делимым и делителем будут w = uv ± uv и w = uv. (Этот случай следует выделить особо, поскольку согласно теореме 4.5.2D, если знаменатели и и v распределены случайно, то di равно 1 примерно в 61 случае

* Здесь и далее gcd{) означает наибольший общий делитель (greatest common devisor). - Прим. перев.

из 100. Если di > 1, то положим t = u{v/di) ± v{u/di) и вычислим 2 = gcd(<,di); окончательный результат равен w = t/d2, w = {u/di){v/d2)- (В упр. 6 доказывается, что эти значения w и ги взаимно просты.) Операции над числами, представленными с однократной точностью, выполняются также с однократной точностью, но t может быть числом с двойной точностью или чуть больше (см. упр. 7); учитывая, что gcd{t,di) = gcd(tmoddi, di), вычиачение числа 2 не требует двойной точности.

Например, чтобы вычислить (7/66) + (17/12), находим di = gcd(66,12) = 6; тогда < = 7 • 2 -Ь 17 • И = 201, а 2 = gcd(201,6) = 3, так что в результате получим

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

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

Методы, рассматриваемые в этом разделе, распространяются также на другие числовые поля, в частности можно было бы выполнять арифметические действия над величинами вида {и + ил/5)/и", где и, и, и" - целые числа, gcd(u, и, и") = 1 и и" > О, или над величинами вида {и + и\/2 + и"\/4)/и" и т. д.

Интересно рассмотреть также (если не упорствовать в применении точных методов) числа в формате с фиксированной дробной чертой, и в формате с плавающей дробной чертой, которые являются аналогами чисел с плавающей точкой, но в их основе лежат рациональные дроби, а не дроби, ориентированные на представление Б системах счисления с каким-либо основанием Ь*.

При представлении дроби в двоичном формате с фиксированной дробной чертой числитель и знаменатель дроби содержат не более р бит, где р - заданное целое число. В случае представления дроби в формате с плавающей дробной чертой сумма битов для числителя и знаменателя не превышает некоторого данного q; при этом для определения размера числителя как составной части цепочки из q бит используется другое поле представления. Бесконечность может быть представлена как (1/0). Чтобы выполнять арифметические действия над такими числами, введем определение х (В у = round(a; + у), х Q у = round(a; - у) и т. д., где round(a;) = х, если X представимо. В противном случае в качестве х выбирается одно из предста-вимых чисел в окрестности числа х. На первый взгляд может показаться, что для определения round(a;) лучше всего выбрать представимое число, ближайшее к х, по аналогии с выбором округления в арифметике с плавающей точкой. Но практика

* В оригинале используются термины "fixed slash", "floating slash" и "slash-arithmetic", которые в связи с отсутствием в русскоязычной литературе соответствующих устоявшихся терминов мы будем переводить как "формат с фиксированной дробной чертой", "формат с плаваюшей дробной чертой", "арифметика в формате с дробной чертой" и "числа в формате с дробной чертой".- Прим. перев.