данный пример показывает, что для 6 = 10 теорема В при данных предположениях не может быть улучшена.)

23. Очевидно, что vYb/{v + 1)J < (w + 1)[Ь/(г; + 1)J < b, поэтому при v > 6/2 выполняется левая часть неравенства. В противном случае v\b/{v + 1)J > v{b - v)l{v + 1) > (6- l)/2 > [6/2J - 1.

24. Приближенная вероятность равна всего лишь logj, 2, а не . (Например, если 6 = 2, вероятность того, что Vn~\ > 2, приблизительно равна jj. Тем не менее этого еще достаточно много для того, чтобы оправдать выполнение специальной проверки условия rf = 1 на шагах D1 и D8 алгоритма D.)

26. (См. алгоритм в упр. 16.)

Ha этом программа деления упражнении, гАХ = 0.

завершается, причем, как будет показано в следующем

27. Это число равно du mod dv = d{u mod v).

28. Предположим (для удобства), что v имеет десятичную точку слева, т. е. что v = {vn.Vn-iVn~2 •••)(> После завершения шага N1 получим j < и < 1 + 1/6. Тогда

Vn-l + 1 6+1

г;(6+1) t;(l + l/6) 1

-г;„ 1 + 1 (1/6)(г;„ 1+1) "6

Vn-l + 1

V{b+1- Vn-l) 1 Vn-l{b+l - Vn-l) - Vn-l +1 - 6 Vn-l + 1

Величина в последнем соотношении принимает наименьшее значение при Vn-i = 1, так как это выпуклая функция и другое ее экстремальное значение больше.

АТО 6(6+1)

Формулу на шаге N2 можно переписать в виде v -----

находим, что v никогда не будет > 1 + 1/6.

.Vn-l + 1.

-, поэтому, как и выше, 6

После одной итерации шага N2 минимальное значение v не меньше, чем

/6(6+l)-t;„-i\ г; /6(6 + l)-j\ /6(6 +1) + 1 - t \/< - 1 \ V г;„ 1+1 )Ь-\ г;„ 1 + 1 ) 6 V < ДбУ

662 бН < У

при i = t;„ i + 1. Минимум этой величины достигается при t - bjl + 1, нижняя граница равна 1 - 3/26. Следовательно, после одной итерации шага N2 имеем Vn-i > 6 - 2. В итоге получаем (1-3/26)(1 + 1/6) > 1, где 6 > 5, так что потребуется еще не более двух итераций. В случае, когда 6 < 5, утверждение легко проверяется непосредственно.

29. Это утверждение верно, так как (uj+n .. .Uj)b < v.

30. При выполнении алгоритмов А и S такое перекрытие возможно, если алгоритмы слегка видоизменить. К примеру, в алгоритме А можно так переписать шаг А2: "Присвоить t<-Uj+Vj+k,Wj <r-tmodb, к •«- [t/b\".

При выполнении алгоритма М значение Vj может храниться в том же месте, что и Wj+n- При реализации алгоритма D удобнее всего (как в программе D в упр. 26) принять, что значения r„ i ... го хранятся там же, где и Un-i ...щ. Можно также считать qm .до такими же, как и Um+n - Un, при условии, что на шаге D6 значения переменных Uj+n не изменились. (Строка 098 программы D может быть без вреда заменена на "J1N2B", так как величина щ+п в вычислениях, выполняемых на этом шаге, не используется.)

31. Рассмотрите ситуацию, приведенную на рис. 6, положив и = (uj+n ... м>+1М>)з, как в алгоритме D. Если ведущие ненулевые разряды чисел и и v имеют один знак, то присваиваем г и - v, q -t- 1; в противном случае присваиваем г <- и + и, g <- -1. Если теперь г > \и\ или г = и и знак первого ненулевого разряда чисел Uj-i .. .ио совпадает с первым ненулевым разрядом числа г, то присваиваем 5 <- 0; в противном случае присваиваем uj+n .. .Uj значения разрядов числа г.

32. См. М. Nadler, САСМ 4 (1961), 192-193; Z. Pawlak and А. Wakulicz, Bull, de iAcad. Poionaise des Sciences, Classe III, 5 (1957), 233-236 (см. также с. 803-804), и упр. 4.1-15.

34. См., например, R. Е. Maeder, The Mathematica Journal 6, 2 (Spring, 1996), 32-40; 6,3 (Summer, 1996), 37-43.

36. Имея число ф, заданное с точностью ±2"", ф~, ф~, значение 1пф можно вычислить, выполняя вычитания до тех пор, пока ф~ < 2~". Накапливаемая при этом ошибка не превысит 2""". Затем можно использовать ряд \пф = 1п({1 + ф~)/{1 -ф~)) = 2{ф~ + ф~ + 1ф~ Н----). [См. статью William Schooling, Napier Tercentenary Memorial,

edited by С. G. Knott (London: Longmans, 1915), 337-344.] Ho еще лучше (предложено в 1965 году Дж. У. Ренчем (мл.) (J. W. Wrench, Jr.)) вычислить

1пф=11п((1 + 5-1/)/(1 - 5-1/)) = {2ф - 1)(5-1 + 5- + i5- + ••)•

37. Пусть d = 2, так что b > dvn-i > 5/2. Вместо нормализации и и и на шаге D1 определяем два ведущих разряда vv" числа 2(D„ iD„-.2Wn-3)i> посредством его сдвига влево на е бит. На шаге D3 вместо {vn-\-,Vn-2) используем (и, и"), а вместо (tij+n, Uj+n-ii j+n-2) используем {и ,и" ,и"). Значения разрядов ии"и" вычисляются путем сдвига влево на е бит числа {щ+п Uj+n-3)b- Деление на d на шаге D8 опускаем. (В сущности, числа и и v сдвигаются "виртуально". Такой метод снижает объем вычислений, если тп малб по сравнению с п.)

38. Присвоим к +- п, г +- О, S +- 1, t +- О, W i- и. Тогда сохраняется инвариантное отношение uv = 2"= (г + s - s) + 2"-"< + 2*-"Dtti при О < t, w < 2" и при О < г < 2s. Если условие (г, s) = (0,1) больше не выполняется, то до тех пор, пока к >-0, положить Aw = 2"-w + w" и 4t + wv = 2"t + <", где О < w",t" < 2" и О < t < 6. Затем присвоить t <- <", w <- w", s +- 2s, г <- Аг + t - s, к i- к - 1. Если г < О, присвоить s <- s - 1 и г <- г + 2s, в противном случае, если г > 2s, присвоить г<- г - 2shS<- s + 1 (эта поправка может понадобиться дважды). Повторять до тех пор, пока не получим к = 0. Тогда ud = г + s - s, так как w всегда умножается на 2"-*. Соответственно, г = О тогда и только тогда, когда ми = 0. В противном случае результат будет равен s, так как uv - S < < uv + S.

39. Положим 5j = Zfc>o 16"*/(8fc+j). Необходимо выяснить, выполняется ли неравенство 2""7г mod 1 < J. Так как тг = 45i - 254 - Ss - Se, этого достаточно для наличия хороших оценок 2"~5, modi. Теперь 2"~Sj конгруэнтно (по модулю 1)

Е anjk/i8k+j)+ Е r--/iSk+j),

0<fc<T»/4 к>п/4

где Unjk - 2"~~* mod(8A; + j). Каждый член в первой сумме может быть аппроксимирован посредством вычисления ajk при помощи C>(logn) операций (раздел 4.6.3) в пределах 2~". После этого получится промасштабированное частное [2anjk/{8k -I-j)J. Вторая сумма может быть аппроксимирована в пределах 2~" в результате вычисления 2"* раз ее первых т/4 членов. Если m а 21g тг, интервал неопределенности будет равен и 1/п, что почти всегда обеспечивает достаточную точность. [iVfath. Сотр. 66 (1997), 903-913.]

Примечание. Пусть = е* = (1 + г)/\/2 равно корню степени 8 из единицы. Рассмотрим значения Zj = ln(l-C/v2 ). Тогда /о = 1п(1 -1/\/2 ), Zi = I7 = 5 In -г arctan 1, /2 = 7б = 5 In 1 - i arctan(l/v/2 ), /3 = ?5 = 5 In - i arctan(l/3), h = ln(l + l/\/2 ). Кроме того, -Sj/2 = (Zo + C"-*! + • • • + Ch) при 1 < J < 8 вследствие 1.2.9-(13). Отсюда 45i - 254 - 55 - Se = 2lo - (2 - 2t)2Zi + 2/4 + (2 + 2г)/7 = п. Другие интересные тождества приведены ниже:

1п2 = 52 + 54 + 5б + 58; 1пЗ = 252 + jSe; 1п5 = 252 + 2s4 -I- ISe; \/2 1п(л/2 + 1) = Si + 5з + iSs + ISt; л/2 arctan(l/v) = Si - 5з + \Sb - ISt; arctan(l/3) = Si - 52 - 5s4 - Ss;

0 = 8S1 - 8S2 - 4S3 - 854 - 2S5 - 25б + St.