также подчиняется логарифмическому закону в том смысле, что

В работе Р. Schatte, Afath. Nuchnchten 148 (1990), 137-144, доказано, что знаменатели в непрерывных разложениях дробей имеют логарифмические дробные части, если только частичные отношения имеют повторяющуюся форму с полиномиальной вариацией, как в упр. 4.5.3-16. Очень интересен вопрос, который до сих пор остается открытым: будет ли последовательность (2!, (2!)!, ((2!)!)!,...) иметь логарифмические дробные части; см. J. Н. Conway и М. J. Т. Guy, Еигеки 25 (1962), 18-19.

РАЗДЕЛ 4.3.1

2. Если г-м слагаемым является щ = (ицп-х).. .ициго)ь, то используем алгоритм А, в котором шаг А2 модифицирован следующим образом.

А2. [Сложить разряды.] Присвоить

Wj <- [uij Н-----f- Umj + к) mod* и •<- [{uij Н-----1- Umj + k)/b\.

(Максимальное значение fc равно m - 1, поэтому при m > b потребуется изменить шаг A3.) 3.

Время выполнения в предположении, что К = \MN, равно 5.5MN + 7N + 4 циклов.

4. Перед шагом А1 можно сделать следующее утверждение: "п > I и О < Ui,Vi < b при О < г < п". Перед шагом А2 справедливо утверждение "О < j < п; О < Ui,Vi < b при О < г < п; О < < ЬприО < г < j; О < fc < 1; [uj-i . ..uo)b+{vj-i . ..ио)ь = {kwj-i... wo)b\ Более точная форма последнего утверждения такова:

0<i<J 0<l<3 0<1<J

Перед шагом A3 справедливо утверждение "О < j < п; О < Ui,Vi < b при О < г < п; О < tf, < Ь при О < г < j; О < fc < 1 и (uj ... ио)ь + {uj .. .ио)ь = {kwj ... wo)b После шага A3 справедливо утверждение, что О < Wi < b при О < г < п; О < tfn < 1 и {un-i . ио)ь +

{v„-i . . . Vo)b = {Wn ..Wo)b.

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

5. Bl. Присвоить J <- n - 1, tfn <- 0.

B2. Присвоить t Uj + Vj, Wj t mod 6, i 4- j.

B3. Если t >b, присвоить i +- i + 1, t <- wt + I, wt t mod b и повторять этот шаг до тех пор, пока не будет выполнено неравенство t < 6.

В4. Уменьшить j на единицу и, если j > О, вернуться к шагу В2.

6. С1. Присвоить j -t- п - 1, i п, г <~ 0.

С2. Присвоить t Uj + Vj. Если t > b, присвоить Wi-i-r + lHWk-t-O при г > к > j; затем присвоить i +- j и г +- t mod 6. В противном случае, если t < Ь-1, присвоить Wii-rawkb - 1 при i > к > j. После этого присвоить i +- j и г <- t.

СЗ. Уменьшить j на единицу. Если j > О, вернуться к шагу С2, в противном случае присвоить Wi+-rHWkb-1 при г > > 0.

7. Если, к примеру, j = п - 3, то fc = О с вероятностью (Ь + 1)/2Ь; fc = 1 с вероятностью ((Ь - 1)/2Ь)(1 - 1/6), а это вероятность того, что произошел перенос"и предшествующий разряд не был равен 6-1; fc = 2 с вероятностью ((6 - 1)/26)(1/6)(1 - 1/6) и fc = 3 с вероятностью ((6- 1)/26)(1/Ь)(1/6)(1). При фиксированных fc можно просуммировать все вероятности по параметру j, который изменяется от п - 1 до 0; это даст среднее число случаев, когда перенос распространяется на fc разрядов:

6-1 /

Для проверки найдем среднее число переносов

..,l fc)(l-) + l).

-f2m. + ...+.m„=:i(n--(l-(i))).

что согласуется с формулой (6). 8.

Время выполнения программы зависит от L - числа позиций, в которых Uj + Vj > 6, и от К - общего числа переносов. Нетрудно заметить, что К - это та же самая величина, которая появляется в программе А. Анализ в тексте раздела показывает, что среднее значение L равно Л((6 - 1)/26), а среднее значение К равно (Л - 6~ - 6" - ... - 6""). Таким образом, если пренебречь членами порядка 1/Ь, время выполнения программы будет равно 9N + L + 7K + 3ai 13N + 3 циклам.

9. На шаге А2 везде заменить "6" на "bj".

10. Если поменять местами строки 06 и 07, то почти всегда можно получить переполнение. При этом регистр А в ходе выполнения команды в строке 08 может иметь отрицательное значение, так что программа работать не будет. Если поменять местами строки 05 и 06, то последовательность переполнений, происходящих в ходе работы программы, будет в некоторых случаях иной, но программа даст правильный результат.

11. Эта задача равносильна задаче лексикографического сравнения цепочек: (i) присвоить j <- тг -1; (ii) если щ < Vj, закончить с результатом [и < v]; если Uj = vj и j = О, закончить

с результатом [и = г;]; если щ = vj и j > О, присвоить j j - 1 и повторить (ii); если Uj > Vj, то закончить [и > и]. Этот алгоритм оказывается довольно быстрым, так как обычно очень мала вероятность того, что j станет очень большим раньше, чем возникнет случай, когда щ ф vj.

12. Используем алгоритм В при Uj = О и vj = Wj. В конце этого алгоритма появится другое "заимствование", но на этот раз им можно пренебречь.

13. ENN1 N 1 MUL V STA W+N,l N JOV OFLO 1 SLC 5 N INCl 1 N ENTX 0 1 ADD CARRY N JIN 2B N

2H STX CARRY N JNOV *+2 STX W+N 1

LDA U+N.l N INCX 1 К

Время выполнения программы равно 23Л + АГ + 5 циклам, а грубая оценка К есть N,

14. Ключевым является индуктивное утверждение, которое должно быть справедливым в начале шага М4. Все остальные утверждения легко выводятся из этого утверждения, которое выглядит так; О < г < т; О < j < п; О < и; < 6 при 0</<т;0<г;;<Ь при О < Z < п; О < и;; < 6 при 0<Z<j + m;0<fc<b;HB обозначениях, введенных в ответе к упр. 4,

{Wj+m-l .Wo)b + kb" = U X [Vj-l . ..Vo)b + (ui-l . ..Uo)b X Vjb .

15. Ошибка неотрицательна и меньше (n - 2)6-"". (Аналогично, если проигнорировать произведения при i+j > п+3, ошибка будет ограничена величиной (71-3)6-""", и т. д. Но, вообще говоря, для получения правильно округленного результата необходимо вычислять все произведения.) Дальнейший анализ показывает, что корректно округленный результат перемножения дробных частей чисел в формате с плавающей точкой почти всегда может быть получен при вычислительных затратах, почти вдвое меньших, чем при вычислении полного произведения с удвоенной точностью. Более того, выполнив проверку, можно убедиться, что случаи, в которых необходима полная точность, крайне редки. [См. W. Krandick, J. R. Jolinson, Ргос. IEEE Symp. Computer Arithmetic 11 (1993), 228-233.]

16. SI. Присвоить r <- Q, j <- n - I.

52. Присвоить Wj <- [{rb + Uj)/v\, r -t- (rb + Uj) mod v.

53. Уменьшить j на 1 и, если j > О, вернуться к шагу S2.

17. u/v > Unb/{vn-i + 1)6"- = 6(1 - \/{vn-i + 1)) > 6(1 - 1/(6/2)) =6-2.

18. {unb + Un-i)/{vn-i + 1) < u/{vn-i + 1)6"- < u/v.

19. и - qv < и - gt)„-i6"- - gt;„ 26"- = «„-26"" + • • + «о + г6"- - gt;„ 26"- < 6""(un 2 + 1 + г6 - qVn-i) < 0. Поскольку и - qv < 0, то q < q.

20. Если q < q-2, TO и < {q- l)v < g(ii„-i6"- + {vn-2 + 1)6"-) - v < qvn-ib" + дг;„ 2б-+6"--г; <gt;„ i6"-4(6r + M„-2)6"-+6"--t; = M„6" + M„ i6"-i+M„ 26"- + 6"~ - t; < u„6" + Un-i6"- + Un 26"~ < u. Другими словами, выходит, что u < u, а это невозможно.

21. (Получено Г. К. Гоялом (G. К. Goyal).) Из неравенства qvn-2 < bf + Un-2 следует q < (u„6 + u„ i6 + u„ 2)/(t;„ i6 + Vn-2) < u/{{vn-\b + d„-2)6"-). Отсюда u mod v = u - gt; = i;(l - q), где 0 < a = 1 + g - u/v < q - u/v < u(l/((t;„ i6 + «„-2)6"-) - 1/v) = и(г;„ зЬ"-Ч--)/(К-1б+г)„-2)6"-г;) < u/iv-ibv) < q/iv-ib) < (6-1)/(г;„ 16), которое ограничено величиной 2/6, так как Vn-i > j(6 - 1).

22. Пусть и = 4100, v = 588. Возьмем сначала q = [yJ = 8. Однако видим, что 8 • 8 > 10(41 - 40) + 0. Тогда полагаем g = 7 и получаем 7 • 8 < 10(41 - 35) + 0. Но число 588, умноженное на 7, равно 4116, так что правильное частное будет q = 6. (Между прочим,