содержатся весьма полезная теоретическая часть и демонстрация ее приложения на практике.

Введенные в этом разделе отношения -<, ~, >-, « имеют аналогию с идеями, сфор.мулированным в работе А. Van Wijngaarden, BIT 6 (1966), 66-81. Приведенные выше теоремы А и В навеяны некоторыми работами в этой области Оле Меллера (01е МоИег), BIT 5 (1965), 37-50, 251-255. Теорема С взята из работы Т. J. Dekker, Sumer. Math. 18 (1971), 224-242. Расширение и уточнение всех трех теорем опубликовано в работе S. Linnainmaa, BIT 14 (1974), 167-202. У. М. Кахан (W. М. Kahan) сформулировал теорему D в неопубликованных заметках; полное ее доказательство и комментарии приведены в работе J. F. Reiser, D. Е. Knuth, Inf. Ргос. Letters 3 (1975), 84-87, 164.

Использовать арифметику ненормализованных чисел с плавающей точкой рекомендовали Ф. Л. Бауэр и К. Замельзон в упомянутой выше статье; независимо ее использовал Дж. В. Карр (J. W. Carr Ш) из Мичиганского университета (1953 г.). Несколькими годами позже был спроектирован компьютер MANIAC III с аппаратной реализацией арифметики обоих типов (см. R. L. Ashenhurst и N. Metropolis, JACM 6 (1959), 415-428, IEEE Trans. EC-12 (1963), 896-901; R. L. Ashenhurst, Proc. Spring Joint Computer Conf 21 (1962), 195-202). Среди других других ранних работ, касающихся ненормализованной арифметики, нужно также упомянуть статьи И. L. Gray, С. Harrison, Jr., Ргос. Eastern Joint Computer Conf 16 (1959), 244-248, и W. G. Wadey, JACM 7 (1960), 129-139.

О ранних исследованиях в области арифметики интервалов речь идет в работах А. Gibb, САСМ 4 (1961), 319-320; В. А. Chartres, JACM 13 (1966), 386-403, и книге Interval Analysis by Ramon E. Moore (Prentice-Hall, 1966). Последующий "расцвет" в этой области приводится в более поздней книге Мура (Moore) Methods and Applications of Interval Analysis (SIAM, 1979).

Расширение языка Pascal, допускающее использование переменных наподобие "interval", разработано в Университете Карлсруэ в начале 80-х годов.

Описание этого языка, который включает и множество других функций, ориентированных на научные расчеты, приведено в работе Pascal-SC (Academic Press, 1987); авторы - Бохлендер (Bohlender), Ульрих (Ullrich), Вольф фон Гуден-берг (Wolff vOn Gudenberg) и Ролл (Rail).

Книга Ulrich Kulisch, Grundlagen des numerischen Rechnens: Mathematische Be-griindung der Rechnerarithmetik (Mannheim: Bibl. Inst., 1976) полностью посвящена исследованию систем арифметики в формате с плавающей точкой. (См. также статью Кулиша (Kulisch) в журнале IEEE Trans. С-26 (1977), 610-621, и его более позднюю работу в соавторстве с У. Л. Миранкером (W. L. Miranker), озаглавленную Computer Arithmetic in Theory и Practice (New York: Academic Press, 1981).)

Прекрасный обзор наиболее свежих работ, касающихся анализа точности выполнения расчетов в формате с плавающей точкой, появился в книге N. J. Higham, Accuracy и Stability of Numerical Algorithms (Philadelphia: SIAM, 1996).

УПРАЖНЕНИЯ

Замечание. Если не оговорено противное, предполагаются действия над нормализованными числами в формате с плавающей точкой.

1. [М18] Докажите, что тождество (7) следует из соотнощений (2)-(6).

2. [М20] Используя тождества (2)-(8), докажите, что (и ® х) ® (v @ у) > u®v, каковы бы ни были X > О и у > 0.

3. [Л/20] Найдите восьмиразрядные десятичные числа с плавающей точкой и, v и w, для которых

•U (8 (v® w) (и (8 (8 W,

причем ни при одном из этих вычислений не происходит ни переполнения, ни исчезновения порядка.

4. [10] Можно ли найти числа с плавающей точкой и, v и w, для которых при вычислении •U (8 (8 w) происходило бы исчезновение порядка, а при вычислении (и (8 7) (8 w не происходило?

5. [М20] Выполняется ли для всех чисел с плавающей точкой uuv ф О равенство u<dv - •U (8 (1 0 таким образом, что не возникает ни переполнения, ни исчезновения порядка?

6. [М22] Для каждого из следующих двух соотношений выясните, выполняется ли оно тождественно для всех чисел и в формате с плавающей точкой: (а) О в (О в и) = и; (Ь) I0(l0u) = и.

7. [М21] Пусть и© означает и (8 и. Найдите такие бинарные числа с плавающей точкой и HV, для которых [и ф v)® > 2{и® + v®).

* 8. [20] Пусть б = 0.0001; какое из соотношений

и-< V (б), u~v (б), u>-v (б), и я: V (б)

выполняется для следующих пар восьмиразрядных десятичных чисел с плавающей точкой с избытком О?

a) u = (1, +.31415927), v = (1, +.31416000);

b) и = (О, +.99997000), v = (1, +.10000039);

c) и = (24, +.60221400), v = (27, +.00060221);

d) и = (24, +.60221400), v = (31, +.00000006);

e) u = (24, +.60221400), v = (28, +.00000000).

9. [М22] Докажите утверждение (33) и объясните, почему его нельзя усилить до и й W (ei +62).

► 10. [М25] (У. М. Кахан (W. М. Kahan).) На некотором компьютере неправильно выполняется округление при арифметических операциях над числами в формате с плавающей точкой, и фактически программа умножения принимает во внимание только первые р значащих разрядов 2р-разрядного произведения ffv (Таким образом, если /„/„ < 1/Ь, из-за последующей нормализации наименее значимый разряд в и (8 и всегда оказывается равным нулю.) Покажите, что это приводит к утрате монотонности умножения, т. е. что существуют такие положительные нормализованные числа с плавающей точкой и, v и w, что на этом компьютере и < но и (8 w > v 0 ш.

11. [М20] Докажите лемму Т.

12. [М24] Докажите теорему В и (46), если [е - е„ > р.

► 13. [М25] Некоторые языки программирова1Шя (и даже некоторые компьютеры) оперируют только числами в формате с плавающей точкой, не выделяя в отдельную группу точные операции над целыми числами. Если желательны и операции над целыми числами, можно, естественно, представить их в формате с плавающей точкой. Тогда, если операции арифметики с плавающей точкой удовлетворяют базовым соотношениям (9), можно считать, что все операции выполняются точно в том смысле, что, если операнды представлены р значащими разрядами, точными будут р значащих разрядов. Далее, до тех пор, пока

можно быть уверенным, что числа не слишком велики, можно складывать, вычитать и умножать целые числа и считать при этом, что округление не сказывается на точности.

Но предположим, что программисту необходимо определить, является ли m точно кратным п, когда т и п ф О оба целые. Далее предположим, что в нашем распоряжении имеется подпрограмма для вычисления величины round(u mod 1) = и (mod) 1 для любого заданного числа и в формате с плавающей точкой, как в упр. 4.2.1-15. В качестве подходящего способа определения, является ли m кратным п, можно было бы проверить выполнение соотношения (т 0 п) (mod) 1 = 0, подразумевая наличие указанной выше подпрограммы. Но, возможно, в некоторых случаях эта проверка не даст адекватного результата из-за ошибок округления при выполнении вычислений в формате с плавающей точкой.

Отыщите подходящие условия, которые нужно наложить на диапазон значений целых чисел п 7 О и т, такие, что m является кратным п тогда и только тогда, когда (т 0 п) (mod) 1 = 0. Другими словами, покажите, что, если m и п не слишком велики, эта проверка дает верный результат.

14. [М27] Найдите подходящее значение е, такое, что (и ® и) ® го и и ® (и ® го) (е), если выполняется ненормализованное умножение. (Этим обобщается соотношение (39), поскольку ненормализованное умножение нормализованных операндов и, v nw в точности повторяет результат нормализованного умножения.)

► 15. [М24] (Г. Бьёрк (Н. Bjork).) Действительно ли вычисленная средняя точка интервала всегда находится между крайними точками? (Другими словами, действительно ли из и < и следует, что и < (и® v) 02 < v?)

16. [М28] (а) Чему равно (• • • ((ц Ф хг) Ф хз) Ф Ф х„) при использовании восьмиразрядного представления в формате с плавающей точкой, если п = 10* и х* = 1.1111111 для любых к? (Ь) Что произойдет, если использовать выражение (14) для вычисления стандартного отклонения на множестве этих конкретных чисел х*? Что произойдет, если вместо этого выражения использовать формулы (15) и (16)? (с) Докажите, что 5* > О в

(16) при любых XI, . . . , Xk-

17. [28] Разработайте подпрограмму FCMP для MIX, сравнивающую число в формате с плавающей точкой и, которое находится по адресу АСС, с числом в формате с плавающей точкой V, которое находится в регистре А и устанавливает в индикаторе сравнения значение LESS, EQUAL или GREATER соответственно результату и -< v, и v или и У v (е). Здесь 6 хранится по адресу EPSILON в виде неотрицательного значения с разделяющей точкой, фиксированной слева от старшего разряда слова. Предполагается, что входные значения нормализованы.

18. [М40] Существует ли в арифметике ненормализованных чисел подходящее значение б, такое, чО и ® (и ф го) « (и ® i;) ф (и ® го) (е) ?

► 19. [МЗО] (У. М. Кахан.) Проанализируйте следующие процедуры суммирования XI,..., Хп в формате с плавающей точкой:

So = Со = 0;

У* =а;*, ес* 1, Sk=Sk-ieyk, Ск = (sk в Sk-i) Q Ук, где 1 < к < п. Будем считать, что относительная ошибка в этих операциях определяется по формулам

Ук = (Хк - Ск-1){1 + Пк), Sk = (Sk-l +Ук){1+0Гк),

Ск = {(sk - Sk-i)(l + jk) - У*)(1 + Sk),

где тг*,к*,7*Ы<5* < е. Докажите, что s„ = ELi(l + *)*- где \вк\ < 2е + 0(пе)-[Теорема С утверждает, что, если 6 = 2 и \sk-i\ > \ук\, имеем точное равенство Sk-i +Ук = Sk-Ck- Но в данном упражнении желательно получить оценку, которая справедлива даже