26. Пусть е = тгх{еи,еи), е = тах(е„,е„/), е" = mBx.(eu®v,eu®v), и предположим, что 9 = 0. Тогда {ифу)-{и ev) <u + v+ b"" - и - v + Ь"-р < eb" + eb + b"" и e" > max(e, e). Следовательно, и ф w ~ и Ф w (2б + b~).

Если 6 = 2, эта оценка может быть уточнена до 1.5е + Ь~. При условии, что е + Ь~ есть верхняя граница, если и - и и v - v, получим противоположные знаки, а в другом случае не может оказаться е = е = е".

27. Сформулированное тождество есть следствие того, что 1 0 (1 0 м) = и при 6" < fu < Ь~*. Если последнее ложно, значит, могут существовать целые числа х и у, такие, что

< а; < Ь""/, и либо у - < Ьр-/х < b/ix - ) < у, либо у < ЬЦх + i) < bf~lx < у + J. Но последнее явно невозможно, если только не выполняется соотнощение х{х + j) > Ьр-, а это последнее условие влечет за собой у = [b-J = х.

28. См. Math. Сотр. 32 (1978), 227-232.

29. Когда 6 = 2, р=1иа;>0, имеем round(a;) = 2", где е{х) = [lga;J. Пусть }{х) = х" -и пусть t{n) = [[an + lg fj/a + lg J. Тогда Л(2) = 2\ Когда а = .99, получим Л(2=) = 2-1 для 41< е < 58.

31. Как следует из теории, которая будет изложена в разделе 4.5.3, "сходимость" бесконечной дроби л/З = И- 1,2,1, 2,... есть рп/яп - An+i(l,l,2,l,2,... )/Кп{1,2,1,2,...). Это прекрасная аппроксимация для \/3, поскольку 3ql ss р, а фактически 3ql - Рп = 2 - 3(п mod 2). Заданный в условии пример таков:

2pii + (3qli -pii)(3gi +pIi) = 2р1 - (pli - l+pli) = 1.

Вычитание в формате с плавающей точкой pli из Здз1 дает нуль, если только нельзя представить Здз1 почти точно. Вычитание pli из 9дз1 дает в общем случае ощибку округления, значительно ббльщую, чем 2рз1. Аналогичный пример можно сформулировать, основываясь на аппроксимации бесконечной дробью любого алгебраического числа.

РАЗДЕЛ 4.2.3

1. {wm,wi) = (.573, .248); тогда WmVi/vm = 290. Таким образом, результат равен (.572, .958). Он верен с точностью до щести десятичных знаков.

2. Это не окажет никакого воздействия на результат, поскольку подпрограмма нормализации обрезает до восьми разрядов и никогда не принимает в расчет байт в этой позиции. (Сдвиг влево происходит в ходе нормализации не более одного раза, так как предполагается, что входные данные уже нормализованы.)

3. При выполнении команды в строке 9 переполнение, очевидно, произойти не может, поскольку складываются двухбайтовые величины. Не может оно произойти и при выполнении команды в строке 22, так как складываются четырехбайтовые величины. Команда в строке 30 вычисляет сумму трех четырехбайтовых величин, что не может привести к переполнению. Наконец, при выполнении команды в строке 32 переполнение невозможно, так как произведение fu fv должно быть меньще единицы.

4. Вставьте команду "JOV OFLO; ENT1 О" между строками 03 и 04. Замените строки 21-22 на "ADD TEMP(ABS); JNOV .+2; INCl 1", a строки 28-31 на "SLAX 5; ADD TEMP; JNOV *+2; INCl 1; ENTX 0,1; SRC 5". Таким образом, ко времени выполнения будет добавлено пять строк кода и только 1, 2 или 3 мащинных цикла.

5. Вставьте "JOV OFLO" после строки 06. Замените строки 22, 31, 39 на "SRAX 0,1", "SLAX 5", "ADD АСС" соответственно. Между строка.ми 40 и 41 вставьте команды "DEC2 1; JNOV DNQRM; INC2 1; INCX 1; SRC 1". (Так и подмывает удалить "DEC2 1" и заменить ее командой "STZ EXPO", но тогда команда "INC2 1" может вызвать переполнение регистра г12!)

Таким образом, программа увеличится на шесть строк; время выполнения уменьшится на Зи, если только не возникнет переполнения при работе с дробной частью. В этом последнем случае время выполнения увеличится на 7и.

6. DOUBLE STJ EXITDF Преобразование в формат с удвоенной точностью.

ENTX О Очистка гХ. STA TEMP

LD2 TEMP (ЕХР) rI2<-e.

INC2 QQ-Q Поправка на разность избытков.

STZ EXPO EXPO <- 0.

SLAX 1 Удалить порядок.

JMP DNORM Нормализовать и выйти из подпрограммы.

SINGLE STJ EXITF Преобразование в формат с однократной точностью.

JOV OFLO Убедиться, что индикатор переполнения выключен. STA TEMP

LD2 TEMP(EXPD) rI2 4-е.

DEC2 QQ-Q Поправка на разность избытков.

SLAX 2 Удалить порядок.

JMP NORM Нормализовать, округлить и выйти из подпрограммы.

7. Все три программы дают нуль в качестве результата тогда и только тогда, когда точный результат должен равняться нулю, так что не стоит беспокоиться о нулевых знаменателях в выражениях для относительной ошибки. Наихудший случай для программы сложения действительно плох. Перейдем для наглядности к десятичным обозначениям. Если входные значения слагаемых -1.0000000 и .99999999, то ответ будет равен вместо Ь~. Таким образом, максимальная относительная ошибка <Ji равна Ь - 1, где b - размер байта.

Что касается умножения и деления, то можно предполагать, что оба операнда положительны и порядки обоих операндов равны QQ. Максимальную ошибку умножения легко можно найти, проанализировав рис. 2. Если uv > 1/Ь, то О < uv - и Si v < ЗЬ" + {b - 1)Ь~, так что относительная ошибка ограничена значением (Ь -- 2)6""*. Если 1/Ь < UV < 1/Ь, то О < UV - и <g) V < ЗЬ~, так что в этом случае относительная ошибка ограничена величиной 3b~/uv < 3b~. Возьмем в качестве <$2 ббльшую из этих двух оценок, а именно -36".

В случае деления требуется более тщательный анализ программы D. Величина, действительно вычисленная подпрограммой, будет равна Q-6-be{{a-S"){l3-S)-S")-5n, где а = (um + eui)/bvm, /3 = vi/bvm] неотрицательные ошибки отбрасывания, равные {5, 5, 5", 5"), не превышают (Ь~°, Ь~, Ь~, Ь~) соответственно; наконец, <J„ (ошибка, возникающая при отбрасывании в процессе нормализации) неотрицательна и меньше либо Ь~, либо в зависимости от того, происходит ли сдвиг. Действительное значение частного есть а/{1 + Ье/3) = а - Ьеа/З -I- baS"", где 6""-неотрицательная ошибка, возникающая при отбрасывании бесконечного ряда в (2). Здесь S"" < = так как ряд знакопеременный. Следовательно, относительная ошибка равна абсолютному значению выражения (beS + beS"P/a + beS"/a) - (S/a + beSS"/a + bS"" + <S„/a), умноженному на {l+bej3). Положительные члены этого выражения ограничены величиной b~+b~-hb~, а отрицательные ограничены (по модулю) величиной Ь~ + + плюс вклад от фазы нормализации, величина которого может достигать Ь~. Таким образом, ясно, что потенциально наибольшая составляющая относительной ошибки возникает в процессе выполнения нормализации, и можно считать, что значение <$з = (Ь + 2)6""* является надежной верхней границей для относительной ошибки.

8. Сложение. Если Сц < е„ + 1, то вся относительная ошибка возникает в процессе нормализации и она ограничена значением . Если ви >е1.+2и если знаки операндов совпадают, то, опять же, вся ошибка может быть отнесена на счет нормализации; если знаки противоположны, то ошибка, связанная со сдвигом разрядов из регистра, противоположна ошибке, возникающей после этого в ходе нормализации. Обе составляющие ограничены значением Ь"; следовательно, 6i = b~. (Это существенно лучше результата упр. 7.) Умножение. Анализ, аналогичный выполненному в упр. 7, дает §2 = {b + 2)b~.

РАЗДЕЛ 4.2.4

1. Так как переполнение дробной части может происходить только при операндах одного знака, искомая вероятность равна вероятности переполнения дробной части, деленной на вероятность совпадения знаков операндов, т. е. 7%/(5(91%)) « 15%.

3. logio 2-4 - logjo 2.3 а 1.84834%.

4. Страницы были бы потрепаны равномерно.

5. Вероятность того, что Ю/и < г, равна (г-1)/10--(г-1)/100-----= (г -1)/9. Поэтому

в рассматриваемом случае ведущие цифры распределены равномерно, например ведущая цифра 1 встречается с вероятностью 5.

6. Вероятность того, что имеется три нулевых ведущих бита, равна logjg 2 = j; вероятность того, что два ведущих бита нулевые, равна logjg 4 - logi6 2 = 5; аналогично и для двух других случаев. "Среднее" число нулевых ведущих битов равно Ij, так что "среднее" число "значащих битов" есть р + . Однако наихудший случай, р - 1 значащих битов, встречается с довольно высокой вероятностью. На практике, как правило, оценки ошибок необходимо проводить на основе наихудшего случая, поскольку цепь вычислений настолько "прочна", насколько прочно слабейшее звено. Как следует из анализа ошибок в разделе 4.2.2, верхняя граница относительной ошибки округления равна 2-" для шестнадцатеричной системы счисления. При работе в двоичной системе счисления можно получить р -- 1 значащих битов во всех нормализованных числах с относительной ошибкой округления, ограниченной значением г""" (см. упр. 4.2.1-3). Обширные вычислительные эксперименты подтверждают утверждение, что вычисления в двоичном формате с плавающей точкой дают более точные результаты, чем аналогичные вычисления в шестнадцатеричном формате с плавающей точкой, даже когда точность представления двоичных чисел равна р бит, а не р -- 1.

Из табл. 1 и 2 видно, что шестнадцатеричная арифметика может быть сделана чуть более быстрой, так как для нее необходимо меньше циклов при масштабировании посредством сдвига вправо или нормализации посредством сдвига влево. Но этот фактор оказывается несущественным в сравнении с теми неоспоримыми преимуществами, которые имеет выбор 6 = 2 над другими основаниями (см. также теорему 4.2.2С и упр. 4.2.2-13, 15, 21), в особенности, если принять во внимание, что можно достичь той же скорости вычислений в двоичном формате с плавающей точкой, что и в шестнадцатеричном, ценой очень незначительного повышения суммарной стоимости процессора.

7. Предположим, что

ЕтИЮ*" •5*)--(10*")) =log5VloglO*

и что

Em((10*" • 4*) - Р(10*")) = log4Vlog 10

тогда

Em (P(10«="-5)-P(10«="-4«=)) = logiof

для всех к. По данному малому положительному числу е выберем <J > О так, чтобы F{x) < е при О < X < S, и выберем М > О так, чтобы F{x) > 1 - е при х > М. Можно взять к