AOP_Tom2 (1021737), страница 81
Текст из файла (страница 81)
Интересно доказать это предположение, вычислив в явном виде 1з (з) и г1 (з) для всех пц что и делается в доказательстве следующей теоремы. Теорема Р. Пусть 5 (з) — предел, определенный в (16). Для всякого е > 0 найдется такое чягло Х(е), что фе,(з) ох10 г~ е для < 3 < Ы, где п1 ) Ф(с). Доказатлсльсшво.
На основании леммы () этот результат может быть доказан, если показать, что существует такое число М, зависящее от е, что для всех 1 < з < 10 и всех т ) М справедливы неравенства ф,,(з) — 1ой~ег) < е н (В„~(з)! < с. Нетрудно найти решение рекуррентного уравнения (11) для В . В самом деле, имеем Вс(з) = — 1, Л1(з) = — 1+г/з, Йэ(з) = — 1+(г/з)(1+1п(з/г)) и в общем случае г ~ 1 з 1 Н (з) = — 1+ — ~1+ —,1п — + +,(1п-) ~. (19) Для значений з из указанного интервала эта функция равномерно сходится к -1+ (г/з) ехр(1п(з/г)) = О. Для ц рекуррентная формула (11) принимает вид 1г Г~ 1~~(~) = - ~с + 1+ / Я ~(1) йс (20) где (21) с = (г — 10)/9; 1/ 1 1 с .~~ — — — ~с 1п10+ —,с 1(1п10)т+ + —,с1(1п10) (гз) 10 1 г 101 + г 1+ — 1п — + + — ~1п — /' — 10 1! г ш! г / Эта последовательность кажется очень сложной, однако в действительности ее мо- жно легко исследовать при помощи производящих функций.
Положим С(з) = сгз+сэз +сзз + Решение рекуррентного уравнения (20) также можно найти без труда; необходимо выписать выражения для нескольких первых членов, сообразить, какова общая формула, и доказать ее по индукции. Получим, что 1/ 1 1 Ят(з) 1 + ~сь + се~ — 1 1и з+ ' ' " + с1(1пз)~ / . (22) 1) ™- (ш — 1)! Остается только вычислить коэффициенты с„„которые в соответствии с формулами (19), (21) и (22) удовлетворяют соотношениям тогда в соответствии с равенством 10= = 1+ з 1п 10+ (1/2!)(з1п10)з + приходим к заключению, чта 1 9 Сап+! — 1 !Сп1+1+ 10еплт! 1 1 = — (с +!+с !п10+ + — С1(1П10) ) + — ~1+.. + — (!п — ) ) — 1 10л + т! ) 10~ пл!~ г) / есть коэффициент при г +' в разложении функции — С(з)10 + — ( — ) ( — ) —— (24) Это условие выполняется для всех значений т, так что значение выражения (24) должно равняться С(з).
Получаем в явном виде формулу — з (10/г)' ' — 1 (25) Чтобы завершить анализ, необходимо проанализировать асимптотические свойства коэффициентов С(з). Множитель в скобках в выражении (25) ири з — л 1 стремится к !п(10/г)/!п10 = 1 — 1ойшг„откуда следует, что 1 — !ойш г (26) есть аналитическая функция комплексной переменной з в круговой области (г! < 1+— В частности, разложение функции Я(з) сходится прк с = 1, так что ее коэффици- енты стремятся к нулю. Это доказывает, что коэффициенты функции С(с) ведут себя, как коэффициенты функции (!ох!ос — 1)/(1 — с), так что 1ип с„, = 1айшг — 1. п1-и пп Наконец, сопоставляя этот результат с выражением (22), получаем, что на отрезке 1 < а < 10 функция Я (з) равномерно стремится к !ов10г 1 ~ 1 1+ 'о (1+!па+ — (!пэ)з+ .
) = !оп!ос. 1 э 21 Итак, посредствам прямого вычисления доказан логарифмический закон для целых чисел, причем одновременно обнаружено, чта, хотя этот закон и служит очень хорошим приближением для описания усредненного поведения, он никогда не выполняется в точности. Приведенные выше доказательства леммы Я и теоремы Р— это несколько упрощенные и усиленные методы, описанные в работе Б. Дж.
Флехингер (В. 3. Р1еЬ!пкег, АММ ТЗ (1966), 1056 — 1061). Многие авторы исследовали распределение значений в ведущих разрядах, показав, что логарифмический закон является хорошим приближением к таким функциям распределения. Более полный обзор имеющейся по этому вопросу литературы читатель найдет в работах Ральфа А. Рзйми (Ка!рЬ А. Капп!, АММ 83 (197б), 521-538) и Петера Шатта (Регег БсЬагге, Х 1пгогта6оп Ргосезз ля апс~ СуЬегпе11сз 24 (1988), 443 — 455).
В упр. 17 рассматривается подход к определению распределения вероятностей, при котором для целых чисел логарифмический закон выдерживается точно. Далее в упр. 18 демонстрируется, что любое разумное определение распределения вероятнастей иа целых числах должна приводить к логарифмическому закону, если оно (определение) применимо к вероятности появления значения ведущего разряда. Конечно, при работе в формате с плавающей точкой используются, в основном.
нецелые числа, а мы анализировали целые числа, в первую очередь, потому, что этот предмет более знаком и анализ выполняется существенно проще. Если рассматривать произвольные действительные числа, то теоретические результаты получить сложнее. Однако постепенно накапливаются доказательства, что имеет место та же статистика в том смысле, что повторяющиеся вычисления с действительными числами будут почти всегда иметь тенденцию ко все большему приближению к логарифмическому закону по отношению к дробным частям. Например, Петер Шатт показал (Резег Бсйа11е, Хеугзсбг1Е~ гпг апяешапг(ге Маг)ь ппг( Месйап11г 53 (1973), 553 — 5б5), что при весьма слабом ограничении функция распределения произведения независимых случайных действительных переменных, имеющих адин закон распределения, стремится к логарифмическому закону.
Сумма таких переменных ведет себя так же, но только для повторяющегося усреднения. Аналогичные результаты были получены в работе 1. Ь. Ваг!оъ, Е. Н. Вате]зз, Сошрп11пя 34 (1985), 325-347. УПРАЖНЕНИЯ 1. [1В] Если и и в — десятичные числа в формате с плавающей точкой, имеющие один и шот оюг знак, та какова согласно табл. 1 и 2 приближенное значение вероятности того. чта при вы лясленни значения ай в произойдет переполнение дробной части? 2. [42) Проведите дальнейшие эксперименты са сложением и вычитанием чисел в формате с плавающей точкой лля подтверждения и уточнения данных, приведенных в табл.
1 н 2. 3. [15] Найдите, исходя нз логарифмического закона, вероятность того, чта две начальные цифры десятичного числа э формате с плавающей точкой будут "23". 4. [М1В) В тексте раздела отмечено, чта начэльные страницы интенсивна используемых таблиц логарифмов потрепаны в большей степени, нежели последние. Какие страницы были бы самыми потрепанными, если бы мы работали с таблицей аншилогари1бмов, т. е. с таблицей, которая для даннага значения!абш х указывает значение х? б. [МВО] Предположим, чта вещественное число 11 равномерна распределено в интервале 0 с 11 < 1.
Каково распределение значений наиболее значимого разряда 11о б. [ВВ) Если бы адно двоичное г шва содержала и+1 бнц то можно было бы использовать р бнт для представления дробной части двоичных чисел с плавающей тачкой, адин бит— для знака н а — р бит — -для порядка. Эта означает, чта интервал изменения представимых значений, т.
е. отношение наибольшего полажнтельнага нормализованного значения к наиг меньшему, равен, аа сушеству, 2 . Та же машинное глава можно была бы использовать я для представления шгсгниодцощеричиих чисел в формате с плаваюягей тачкой, выделив р + 2 бит для дробной части ((р + 2)/4 шестнадцатеричных цифр) и и — р — 2 бит для — г — г г -г порядка. Тогда интервал изменения значений был бы 1б = 2, т. е. тем же, что и раньше, причем с ббльшнм чистом битов в дробной части. Может сложиться впечатление, что получено нечто из ничего, однако условие нормализации в случае основания 1б слабее в том смысле, что дробная часть может содержать нули в трех старших значимых битах.
Таким образом, не все р+ 2 бит "значащие". Всходя из логарифмического закона, выясните, какова вероятность гаго, что дробная часть положительного нормализованного шестнадцатеричного числа в формате с плавающей точкой имеет в точности О, 1, 2 и 3 нулевых наиболее значимых битов? Основываясь на материале, изложенном в этом разделе, рассмотрите вопрос о достоинствах шестнадцатеричной системы в сравнении с двоичной. Т. [НМ88[ Докажите, что не существует функциираспределения Е(к), удовлетворяющей соотношению (5) для каждого целого числа Ь > 2 и для всех вещественных значений г из интервала 1 < г < Ь.
й. [НМ83] Выполняется ли соотношение (10) при ш = 0 лля соответствующим образом выбранного Не(е)2 9. [НМ85] (П. Дьяконис (Р. 01асоп!э).) Пусть Р,(п), Рз(п), ... — некоторая последовательность функций, определенных повторяющимся усреднением функции Ра(п) в соответствии с формулой (9), Докажите, что 1нп, Р (и) = Рэ(1) для всех фиксированных и. ь 10. [НМ88] В тексте раздела показано, что с = 1обю г — 1+», где е стремится к нулю при ш ~ оо. Найдите следующий член в всимптотическом разложении для с 11.
[МИ] Докажите, что если Н вЂ” случайная величина, распределенная по логарифмиЧЕСкОму ЗаКОну, то ЭтИм же Свойстапм будет обладать и величина 1/сГ. 12. [НЮ8] (Р. У. Хэлгминг (Я. Ч~. Напишпй).) Цель этого упражнения — показать, что результат умножения в формате с плавающей точкой соответствует логарифмическому закону лучше, чем сомножители. Пусть 11 и У вЂ” случайные нормализованные положительные числа в формате с плавающей точкой, имеющие независимое распределение с функциями плотности вероятности /(я) и д(з) соответственно. Тогда /„ < г и /„ < в с вероятностью Д,э Л„ /(з)д(д) 808х, где 1/Ь < г,э < 1. Пусть Л(з) †функц плотности вероятности дробной части (/ х 1~ (неокругленной). Определим меру ошклоненил А(/) функции плот ности вероятности / как максимальную относительную ошибку А(/) = щах где 1(х) = 1/(з 1и Ь) есть платность логарифмической функции распределения. Докюките, что А(Л) < пъ!п(А(/), А(д)).
(В частности, если некоторый множитель имеет логарифмическое распределение, то и произведение будет иметь такое распределение,) ь 13. [МЯО] В алгоритме умножения чисел с плавающей точкой (влгоритм 4.2.1М) число сдвигов влево, требуемых при нормализации, равно нулю или единице в зависимости от того, будет ли /„/ > 1/Ь. Предполагая, что операнды распределены независимо по логарифмическому закону, найдите вероятность того, что для нормализации результата не потребуется ни одного сдвига влево. ° 14. [Над] Пусть ЬГ и У вЂ” случайные нормализованные положительные чнгла в формате с плавающей точкой, имеющие дробные части с независимым распределением по логарифмическому закону, и пусть рь — вероятность того, что разность их порядков равна Л.
Предполагая, что распределение порядков не зависит от распределения дробных частей, выведите формулу, которая через основание Ь и величины рэ, рп рз, ... выражает вероятность тога, что при выполнении сложения 1Г0~ ~' происходит "переполнение дробной части". Сравните результат с результатом упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
