тогда в соответствии с равенством 10 = 1 + 2lnlO+ (l/2!)(2ln 10) Н----приходим

к заключению, что

jCm+l

Ст+1 - YQCm+1 + YQCm+l

4(c„.i + c„lnl0 + ...+ i,c.(lnl0r)+(l+... + i,(lny есть коэффициент при z" в разложении функции

Это условие выполняется для всех значений тп, так что значение выражения (24) должно равняться C{z). Получаем в явном виде формулу

Чтобы завершить анализ, необходимо проанализировать асимптотические свойства коэффициентов C{z). Множитель в скобках в выражении (25) при 2 -> 1 стремится к 1п(10/г)/ In 10 = 1 - logio i откуда следует, что

С(2) + = Riz) (26)

есть аналитическая функция комплексной переменной z в круговой области

27гг

2 <

+1п10

В частности, разложение функции R{z) сходится при, z = 1, так что ее коэффициенты стремятся к нулю. Это доказьгеает, что коэффициенты функции C{z) ведут себя, как коэффициенты функции (logio г ~ !)/(! ~ так что

lim Cm - logio г - 1-

m-+oo

Наконец, сопоставляя этот результат с выражением (22), получаем, что на отрезке 1 < S < 10 функция Qmis) равномерно стремится к

l + l2Il0iL:ii(l + ln5+A(lns)2 + ...) = logior. I

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

Приведенные выше доказательства леммы Q и теоремы F - это несколько упрощенные и усиленные методы, описанные в работе Б. Дж. Флехингер (В. J. Flehinger, АММ 73 (1966), 1056-1061). Многие авторы исследовали распределение значений в ведущих разрядах, показав, что логарифмический закон является хорошим приближением к таким функциям распределения. Более полный обзор имеющейся по этому вопросу литературы читатель найдет в работах Ральфа А. Рэйми (Ralph А. Raimi,

АММ 83 (1976), 521-538) и Петера Шатта (Peter Schatte, J. Information Processing and Cybernetics 24 (1988), 443-455).

В упр. 17 рассматривается подход к определению распределения вероятностей, при котором для целых чисел логарифмический закон выдерживается точно. Далее в упр. 18 демонстрируется, что любое разумное определение распределения вероятностей на целых числах должно приводить к логарифмическому закону, если оно (определение) применимо к вероятности появления значения ведущего разряда.

Конечно, при работе в формате с плавающей точкой используются, в основном, нецелые числа, а мы анализировали целые числа, в первую очередь, потому, что этот предмет более знаком и анализ выполняется существенно проще. Если рассматривать произвольные действительные числа, то теоретические результаты получить сложнее. Однако постепенно накапливаются доказательства, что имеет место та же статистика в том смысле, что повторяющиеся вычисления с действительными числами будут почти всегда иметь тенденцию ко все большему приближению к логарифмическому закону по отношению к дробным частям. Например, Петер Шатт показал (Peter Schatte, Zeitschrift fur angewandte Math, und Mechanik 53 (1973), 553-565), что при весьма слабом ограничении функция распределения произведения независимых случайных действительных переменных, имеющих один закон распределения, стремится к логарифмическому закону. Сумма таких переменных ведет себя так же, но только для повторяющегося усреднения. Аналогичные результаты были получены в работе J. L. Barlow, Е. Н. Bareiss, Computing 34 (1985), 325-347.

УПРАЖНЕНИЯ

1. [13] Если и и V - десятичные числа в формате с плавающей точкой, имеющие один и тот же знак, то каково согласно табл. 1 и 2 приближенное значение вероятности того, что при вычислении значения и ® и произойдет переполнение дробной части?

2. [42] Проведите дальнейщие эксперименты со слокением и вычитанием чисел в формате с плавающей точкой для подтверждения и уточнения данных, приведенных в табл. 1 и 2.

3. [15] Найдите, исходя из логарифмического закона, вероятность того, что две начальные цифры десятичного числа в формате с плавающей точкой будут "23".

4. В тексте раздела отмечено, что начальные страницы интенсивно используемых таблиц логарифмов потрепаны в большей степени, нежели последние. Какие страницы были бы самыми потрепанными, если бы мы работали с таблицей антилогарифмов, т. е. с таблицей, которая для данного значения log[o х указывает значение х?

► 5. [М20] Предположим, что вещественное число U равномерно распределено в интервале О < и < 1. Каково распределение значений наиболее значимого разряда V

6. [23] Если бы одно двоичное слово содержало п+1 бит, то можно было бы использовать р бит для представления дробной части двоичных чисел с плавающей точкой, один бит - для знака и п - р бит - для порядка. Это означает, что интервал изменения представимых значений, т. е. отношение наибольшего положительного нормализованного значения к наименьшему, равен, по существу, 2 . То же машинное слово можно было бы использовать и для представления шестнадцатеричных чисел в формате с плавающей точкой, выделив р -f- 2 бит для дробной части ((р -f- 2)/4 шестнадцатеричных цифр) и п - р - 2 бит для порядка. Тогда интервал изменения значений был бы 16 = 2 , т. е. тем же, что и раньше, причем с большим числом битов в дробной части. Может сложиться впечатление, что получено нечто из ничего, однако условие нормализации в случае основания 16 слабее

в том смысле, что дробная часть может содержать нули в трех старших значимых битах. Таким образом, не все р + 2 бит "значащие".

Исходя из логарифмического закона, выясните, какова вероятность того, что дробная часть положительного нормализованного шестнадцатеричного числа в формате с плавающей точкой имеет в точности О, 1, 2 и 3 нулевых наиболее значимых битов? Основываясь на материале, изложенном в этом разделе, рассмотрите вопрос о достоинствах шестнадца-теричной системы в сравнении с двоичной.

7. [НМ28] Докажите, что не существует функции распределения F(u), удовлетворяющей соотношению (5) для каждого целого числа 6 > 2 и для всех вещественных значений г из интервала 1 < г < Ь.

8. [НМ23] Выполняется ли соотношение (10) при m = О для соответствующим образом выбранного Ло(е)?

9. [НМ25] (П. Дьяконис (Р. Diaconis).) Пусть Pi(n), Р2{п), ...-некоторая последовательность функций, определенных повторяющимся усреднением функции Ро(п) в соответствии с формулой (9). Докажите, что Ишт-юо Рт{п) = Ро(1) для всех фиксированных п.

► 10. [НМ28] В тексте раздела показано, что Ст = logm г - 1 -Н «т, где «т стремится к нулю при m -> оо. Найдите следующий член в асимптотическом разложении для Ст-

11. [Ml 5] Докажите, что если U - случайная величина, распределенная по логарифмическому закону, то этим же свойством будет обладать и величина 1/С/.

12. [НМ25] (Р. У. Хэмминг (R. W. Hamming).) Цель этого упражнения - показать, что результат умножения в формате с плавающей точкой соответствует логарифмическому закону лучше, чем сомножители. Пусть U и V - случайные нормализованные положительные числа в формате с плавающей точкой, имеющие независимое распределение с функциями плотности вероятности f{x) и д{х) соответственно. Тогда /и < г и /„ < в с вероятностью Si/bS/b f9{y)dyd> где 1/Ь < г,в < 1. Пусть h{x)-функция плотности вероятности дробной части и xV (неокругленной). Определим меру отклонения A{f) функции плотности вероятности / как максимальную относительную ошибку

fix)-Их)

A(f) = max

1/Ь<1<1

1{х)

где 1{х) = 1/(а;1пЬ) есть плотность логарифмической функции распределения.

Докажите, что A{h) < mm(A{f), А{д)). (В частности, если некоторый множитель имеет логарифмическое распределение, то и произведение будет иметь такое распределение.)

► 13. [М20] В алгоритме умножения чисел с плавающей точкой (алгоритм 4.2.1М) число сдвигов влево, требуемых при нормализации, равно нулю или единице в зависимости от того, будет ли /„/„ > 1/Ь. " Предполагая, что операнды распределены независимо по логарифмическому закону, найдите вероятность того, что для нормализации результата не потребуется ни одного сдвига влево.

► 14. [НМЗО] Пусть и иУ - случайные нормализованные положительные числа в формате с плавающей точкой, имеющие дробные части с независимым распределением по логарифмическому закону, и пусть pk-вероятность того, что разность их порядков равна к. Предполагая, что распределение порядков не зависит от распределения дробных частей, выведите формулу, которая через основание Ь и величины ро, Рь Рг, .. выражает вероятность того, что при выполнении сложения (78К происходит "переполнение дробной части". Сравните результат с результатом упр. 1 (округление игнорировать).

15. [НМ28] Пусть [/, V, ро, Pi, . те же, что и в упр. 14, и пусть используется арифметика по основанию 10. Покажите, что независимо от значенийpo,pi,p2, • • • сумма (78К не будет