w = и, \v\ < 5. Тогда и = и, v = О, и" = и, v" = 0. Если t; = i и допустимо более общее правило округления, можно было бы получить и = и ± 1, t;" = Случай (1, с): W = и - 1, V < -i, Cv = 0. Тогда и = и или и - 1, t; = -1, и" = и, v" = -1 или 0. Случай 2: и = Ь" . Случай (2, а): w = и + 1, > , е„ = О, как в (1, а). Случай (2, Ь): W = и, \v\ < 5, и > и, как в (1, Ь). Случай (2, с): w = и, \v\ < 5, и < и. Тогда и = и - j/b, где = j/b + ti и wi < для некоторого положительного целого j < jb; имеем t; = О, и" = и, v" = jjb. Случай (2, d): w < и. Тогда w = и - j/b, где = -j/b + vi и \vi\ < для некоторого положительного целого j < b; имеем {v,u") = {-j/b,и)

и {и,v") = {и,-j/b) или {и - 1/6,(1 - j)/b)\ последний вариант возможен, только если ti = \b~. В любом случае uQu = и -и , v Qv = v - v , uQu" = и - и", vQv" = v - v", round(w - u - v) = w - u - V.

13. Поскольку round(a;) = 0 тогда и только тогда, когда а; = О, нужно найти множество пар целых чисел (m,n), обладающих таким свойством: результат m 0 п есть целое число тогда и только тогда, когда целым числом является т/п. Предположим,-что т, \п\ < Ь. Если т/п есть целое, то m 0 п = т/п - также целое. И наоборот, если т/п не есть целое, а m0n - целое, имеем 1/п < т 0 п - т/п\ < \т/п\Ь~. Следовательно, \т\ > 26". Значит, ответ таков: нужно потребовать, чтобы выполнялись условия \т\ < 26" и О < п < Ь. (Возможно и чуть менее жесткое ограничение.)

14. \{u(8)v)(8)w-uvw\ < \{u(Biv)w-{uv)w\ + \w\\uv-uv\ < <J(m8„)i8„+b°""""<Ju(gj« < (1 + b)<J(u(gj.;)(8u>- Теперь \e(ui8v)i8ui - sisivisui)] < 2; таким образом, в качестве искомого результата можно взять б = j(l + 6)6".

15. Из и < следует, что (и е и) 0 2 < (и е w) 0 2 < (w е w) 0 2. Таким образом, сформулированное в задаче условие остается справедливым для любых и и w тогда и только тогда, когда оно справедливо для любых и = v. Для основания 6 = 2 исходное условие справедливо всегда (за исключение случая, когда возникает переполнение); но при 6 > 2 существуют числа v ф w, такие, что w ф w = w ф w. Значит, сформулированное в задаче условие не выполняется. [С другой стороны, формула и Ф ((w 0 и) 0 2) действительно дает среднюю точку, лежащую внутри интервала. Доказательство. Достаточно показать, что и + (w в и) 0 2 < W, т. е. (t; 0 и) 0 2 < W - и; легко проверить, что round(5round(a;)) < х для любых X > 0.]

16. (а) Изменение порядка появится в суммах Ею - И-ШШ, Egi - 101.11111, Едо\ - 1001.1102, Е9001 = 10001.020, Еэоооэ = 100000.91, Едоо&ю = ЮООООО.О; таким образом, Eioooooo = 1109099.1.

(b) После определения суммы X]it=i 1-2345679 = 1224782.1 вычисления в соответствии с (14) приведут к попытке определить квадратный корень из -.0053187053. Но в этом случае вычисления в соответствии с (15) и (16) будут точными. [Если а;* = 1 + [(Л - 1)/2J10~, то вычисления в соответствии с (15) и (16) дадут ошибку порядка п. Более детальный анализ точности вычисления стандартного отклонения приведен в работе Chan and Lewis, CACJW 22 (1979), 526-531.]

(c) Нужно показать, что и ф ((w 0 и) 0 к) находится между и и w; см. упр. 15.

17. FCMP STJ 9F Подпрограмма для сравнения чисел в формате

с плавающей точкой. J0V OFLO Убедиться, что индикатор переполнения выключен.

STA TEMP

LDAN TEMP Vi--V.

(Сюда скопируйте строки 07-20 из программы 4.2.1А.)

LDX FV(0:0) Присвоить гХ значение "нуль" со знаком, совпадающим

со знаком /„.

19. Пусть 7ц, = (5ц, = Tjfr = <тц: = О при к > п. Достаточно найти коэффициент при х\, поскольку коэффициент при Xk будет точно таким же, если все индексы увеличить на /с - 1. Пусть {fk,gk) означают соответственно коэффициенты при xi в (sk - Ск,Ск)- Тогда /i = (1 + ?7i)(l - 7i - 7i<Ji - 7i<Ti - Siffi - 7i<Ji<Ti), gi - {1 + Si){l + ?7i)(7i + <ti + 7KT1) и

/*: = (1 - fkffk - Skffk - ikSk(Tk)fk-\ + (7*: -??*:+ Ik&k + 1кГ]к + -ук&кЩ + -укЩОк + 5кГ]к<Гк +

ykSkVkcrk)gk-i, gk = <Tk(l +7fc)(l +h)fk-\ - (1 +к)Ы +-укЩ +Щ<Гк + fkVkcrk)gk-u где 1 < к <n. Тогда /п = 1 + ??i - 7i + (4n членов второго порядка) + (члены более высоких порядков) = 1 + - 71 + О(пе) будет достаточно мало. [Формула суммирования Кахана впервые была опубликована в САСМ 8 (1965), 40; см. также Ргос. JFJP Congress (1971), 2, 1232, а продолжение - в работе К. Ozawa, J. Information Ргос. 6 (1983), 226-230. Другой подход к организации точного суммирования описан в работе R. J. Hanson, САСМ 18 (1975), 57-58. Когда одни Хк отрицательны, а другие положительны, можно с пользой для дела скомбинировать их, как рекомендуется в работе Т. О. Espelid, SIAM Review 37 (1995), 603-607. См. также работу G. Bohlender, IEEE Trans. С-26 (1977), 621-632, где

приводятся алгоритмы, которые вычисляют round(xi ------- Хп) и round(xi... Хп) точно,

по заданным {xi,... ,Хп}.]

20. Как следует из доказательства теоремы С, соотношение (47) не выполняется при Си, =р, только если \v\ + ~ > \w - и\ > Ь"" + Ь~, поэтому \fu\ > \fv\ > 1 - (5b- 1)6". Теперь приходим к выводу, что необходимое и достаточное условие "невыполнения" (47) есть округление \fw\, по сути, почти до 2 в процессе нормализации (фактически до 2/Ь после масштабирования посредством сдвига вправо для получения переполнения дробной части). Случай, конечно же, чрезвычайно редкий!

21. (Решение Г. В. Вельткампа (G. W. Уеккатр).) Пусть с = 2 + 1; можно предположить, что р > 2, так что с репрезентативно. Сначала вычислим и = и ® с, «1 = (и е и) фи, U2 =uQui; аналогично w = w ® с, m = (w е v) ф w, V2 =vQvi. Затем присвоим w <- u (8 w, w <- (((«1 <Svi Qw)® {ui ® W2)) Ф («2 ® Vl)) ф («2 ® V2).

Достаточно доказать это для случая, когда и, w > О и Сц = Сц = р, так что и я v есть целые € [2"" . .2"). Тогда и = wi -- U2, где 2"- < wi < 2", щ mod2P/1 = О и и2 < 2ГР/21-1. аналогично v = vi + V2. Операции, выполняемые при вычислении w, являются

точными, поскольку UI - UlVl кратно 2 , причем ш -WlWll < \ui - Uv\ + \u2Vl+UlV2+U2V2\ <

+ 2Р+р/21 аналогично \w - uivi - uiV2\ < \w-uv\ + \u2v\ < 2"- зр/И-р

где w - uiV\ - u\V2 кратно 2.

22. Можно предположить, что b~ < u,v < b. Если uv < b~, то x\ = uv - r, где \r\ < \b~. Значит, X2 = round(w - r/w) = xo (since \rlv\ < b~lb~ < 5 и при равенстве следует v = b~, откуда г = 0). Если uv > b~, то xi = uv - г, где r < ib. Поэтому xi/w = и - r/v < b"" + ~b и X2 < b Если X2 = b, TO Xi = Xl (поскольку из условия (b - )w < Xl следует, что xi кратно b и имеем xi < b{v+\)). Если хг < Ь и xi > Ь", то пусть Х2 = xi/v + д, где д < j; получим хз = round(xi + qv) = xi. Окончательно, если Х2 < Ь, XI = Ьр" и Хз < Ь*"", то Х4 = Х2 как следствие первого из рассмотренных выше случаев. Такая ситуация может возникнуть, например, когда Ь = 10, р = 2, и = 19, 1» = 55, XI = 1000, Х2 = 18, Хз = 990.

23. Если и > О или и < -1, имеем и (mod) 1 = и mod 1, так что равенство справедливо. Если -1 < и < О, то и (mod) 1 = иф1=и + 1+г, где г < jb"*"; равенство справедливо тогда и только тогда, когда round(l + г) = 1, так что оно будет иметь место всегда, когда выполняется округление до четного. Если использовать правило округления, приведенное в тексте раздела, то равенство не будет выполняться тогда и только тогда, когда b кратно 4, -К и < О и мmod25" = §5" (например, р = 3, 5 = 8, и = -(.0124)8).

24. Пусть и= [щ .. Ur], V = [vi.. Vr]. Когда и ® v = [ui vi.. Ur А Vr], где х Ay = у А х, X А +0 = X для всех х, х А -О = х для всех х ф +0, х А +оо = +оо для всех х ф -оо, а X А -00 не нуждается в определении; х у = -((-х) А (-у)). Если х ®у приведет к переполнению при выполнении операции согласно обычным алгоритмам работы в формате с плавающей точкой, поскольку х+у слишком велико, то х Ау есть +оо и х у является наибольшим по величине представимым числом.

Для вычитания положим и 0 w = и ф {-v), где -v = [-Vr .. -vi].

С умножением дела обстоят сложнее. Правильный результат даст такая процедура:

пусть и ® W= [min(wi Vl,Ul Vr,Ur Vl,Ur Vr) . . Шах(и( &.Vl,Ul &\Vr,Ur &\Vl,Ur A Wr)],

где X A г/ = у A X, x A (-y) = -(x y) = (-x) Ay; x A +0 = (+0 при x > 0, -0 при X < 0); X A-0 = -(xA+0); x A+oo = (+oo при x > +0, -oo при x < -0). (Можно определить минимум и максимум, просто просмотрев знаки и/, Ur, vi и Wr и вычислив таким образом только два из восьми произведений, кроме ситуации, когда < О < Иг и Vl < о < Wr; в последнем случае нужно вычислить четыре произведения и результатом будет [min(w( Vr,Ur vi) .. шах(и( Avi,Ur А Wr)].)

Окончательно получаем: и 0 w неопределенно, если vi < О < Vr; иначе - будем использовать формулы для умножения, заменив vi и Vr соответственно значениями w и vr\ где X А у" = X А у, X V 2/" = 2 V У, (±0)" = ±оо, (±оо)" = ±0.

[См. Е. R. Hansen, Math. Сотр. 22 (1968), 374-384. Альтернативная схема, в которой деление на О не приводит к сообщению об ошибке и интервалы могут быть окрестностями 00, предложена У. М. Каханом (W. М. Kahan). По схеме Кахана, например, обращение [-1..+1] дает результат [+1..-1], а попытка умножения интервала, включающего О, на интервал, включающий оо, дает результат [-оо..+оо], т. е. множество всех чисел. См. JVumericaJ Anedysis, Univ. Michigan Engineering Summer Conf. Notes No. 6818 (1968).]

25. Это явление связано с ошибками в предшествующих операциях вычисления и я v. Например, если е мало, /(х + е) Q /(х) часто вычисляется с низкой точностью, поскольку округление при вычислении /(х + е) приводит к утрате информации об е. Рекомендуется переписать эту формулу в виде е 0 у(х,е), где у(х,е) = (/(х + е) - f{x))/e определяется сначала в символьном виде. Таким образом, если /(х) = х, то д{х,е) = 2х + б; если fix) = s/x, то у(х, е) = 1/(ч/х + б + ).