Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 1) (1119452), страница 81
Текст из файла (страница 81)
Естественно принять !!ш„+ Р1(п) в качестве искомой "вероятности" р(т). Именно так и было сделано в определении 3.3А. Но в данном случае этот предел не существует, Рассмотрим, например, подпоследовательность Рз(з), Рз(10з), Рз(100з), ..., Рз(10"з), где з — некоторое вещественное число, 1 < з < 10. Если з < т, то имеем Р(10"з) = — (! ! -1+ ! Ют1 -1О+" + ! 10"-' ) -10"-'+ (Ю"з)+1-1О") 10~э 1 = — (т(1+ Ю+" +Ю"-')+О(п)+ (Ю"з) -1-Ю-" -1О") 10" з — (ф(10"т-10"+з) + 110"з) + 0(п)) .
(8) 10" з При и -э оо функция Р1(10"з) стремится, следовательно, к предельному значению 1+ (т -"10)79з. Те же вычисления справедливы и для з > т, если заменить !10" з) + 1 на (10"т). Тогда получим предельное значение 10(т — 1) ~йз при з > т. (См. Л. Ггапе), Жазшзогзс)юла Севе))зевай, Иегсе((апгззсЬг!71 62 (Ыг!сЬ, 1917), 286-29$.) Другими словами, последовательность (Р1(п)) содержит подпогледовательиости (Рз(10"з)), предел которых возрастает от (т — 1)/9 до 10(т — 1)/9т, а затем убывает до (т — 1)/9 по мере того, как з возрастает от 1 до т, а затем от т до 10. Отсюда видно, что последовательность Р1(п) не имеет предела при и -+ оо и что значения Рз(п) при больших п нельзя считать слишком хорошим приближением к пределу !ойзе т, на котоРый мы Рассчитывали! Тах как Р~(п) не стремится к некоторому пределу, можно попытаться еще раз использовать ту же идею, что и в (7), для "усреднения" этого аномального поведения нашей последовательности.
Вообще, положим (9) Интересно доказать это предположение, вычислив в явном виде ь/,в(в) н В (в) дзя всех т, что н делается в доказательстве следующей теоремы. Теорема Г. Пусть 3 (в) — предел, определенный в (16). Для всякого «> 0 найдется такое чнсло Х(«), что ф„,(з) — 1ойщг! <«для1< в<10, (17) Где т ) Х(«). Доказательство. На основании леммы (3 этот результат может быть доказан, если показать, что существует такое число ЛХ, зависящее от «, что для всех 1 < з < 10 н всех т > М справедливы неравенства !Ц (в) — 1ойщг( <«н !В„,(з)! < «. (19) Нетрудно найти решение рекуррентного уравнения (11) для В . В самом деле, имеем Ве(в) = -1, Вв(в) = -1+г/з, Вт(з) = -1+(г/з)(1+!п(з/г)) н в общем случае г/ 1 в 1 г вх В (в) =-1+- ~1+-!и-+".+ — ~!п-~ (19) И ° "' ( -1)!~ .) Для значений з нз указанного иитервала эта функция равномерно сходится к -1+ (г/в) ехр(!п(з/г)) = О.
Для Ц рекуррентная формула (11) принимает вид д () =-~с„+1+у 1;)„,(Г)(1, где гво с = — Ц д (1)а+)! В 61)41 — 1. 1 э (21) Решение рекуррентного уравнения (20) также можно найти без труда; необходимо выписать выражения для нескольких первых членов, сообразить, какова общая формула, и доказать ее по индукции. Получим, что 1/ 1 1 9 (в) =1+- ~с + — с ~!пв+" + — св(!пз) ~~. (22) з ~ 1! (т — 1)! Остается только вычислить коэффициенты с, которые в соответствии с формулами (19), (21) н (22) удовлетворяют соотношениям св = (г — 10)/9; 1/ 1 1 ем+~ = — !1«~1п10+ — с„, в(1п10)з+ ° + — св(1п10)ы 91 2! т! (23) 1 10 1 Г 101м1 + г 1+ — 1п — + " + — ~!п — ) /! — 10 .
1! г т(~ г) ) Эта последовательность кажется очень сложной, однако в действительности ее можно легко исследовать прн помощи производящих функций, Положим С(з) = с«в+ свз~+сзз~+ "", (26) !пп с = !ойш г — 1. ФП-ФОО Наконец, сопоставляя этот результат с выражением (22), получаем, что на отрезке 1 < э < 10 функция Я (э) равномерно стремится к 1ойюг — 1 г 1 1+ й~е ~1+!пэ+ — (!пэ)з+ ° ° ) = 1ойюг.
3 2! Итак, посредством прямого вычиспения доказан логарифмический закон для целых чисел, причем одновременно обнаружено, что, хотя этот закон и служит очень хорошим приближением для описания усредненного поведения, он никогда ие выполняется в точности. Приведенные выше доказательства леммы Я и теоремы à — это несколько упрощенные и усиленные методы, описанные в работе Б.Дж. Флехингер (В.3. Г!еЫпяег, АМАХ ТЗ (1966), 1056-1061). Многие авторы исследовали распределение значений в ведущих разрядах, показав, что логарифмический заков является хорошим приближением к таким функциям распределения. Более полный обзор имеющейся по этому вопросу литературы читатель найдет в работах Ральфа А.
Рэйми (Ва!рЬ А. Вапш, тогда в соответствии с равенством 10" = 1+ с!п10+ (1/2!)(г)п10)т+ приходим к заключению, что 1 9 с .~д = — с„+~+ — с .~~ 10 10 1 г 1 = — ~с,„+~+ем 1п10+ "+ — с~(!и 1О)"') + — ~1+ ° + — ~!и — ) ! -1 10~ + т! ) 10~, "' т)~ т1 / есть коэффициент при г ~~ в разложении функции — С(х)10 + — ( — ) ( — )— (24) Это условие выполняется лля всех зиачений т, так что значение выражения (24) должно равняться С(г). Получаем в явиом виде формулу С(г) =— —. /(10~с)'-' — й (25) 1 — с~ 10' г — 1 Чтобы завершить анализ, необходимо проанализировать асимптотические свойства коэффициентов С(г).
Множитель в скобках в выражении (25) при с -+ 1 стремится к !п(10~с)~ !и 10 = 1 — !ойю г, откуда следует„что С(.)+' "" "=и(.) есть аналитическая фупкция комплексной переменной с в круговой области 2т ~ )г! < ~1+ — . ! 10~ В частности, рвзложеиие функции Я(г) сходится при, х = 1, так что ее коэффициенты стремятся к нулю. Это доказывает, что козффициеитгя функции С(г) ведут себя, как коэффициенты функции (1ойю г — 1)/(1 — г), так что АММ 83 (1976), 521-538) и Петера Шатта (Ре1ег БсЬасте, Х ХпуоггпаНоп Ргосетпя апд Субегпеисв 24 (1988), 443-455).
В упр. 17 рассматривается подход к определению распределения вероятностей, при котором для целых чисел логарифмический закон выдерживается точно. Далее в упр. 18 демонстрируется, что любое разумное определение распределения вероятностей на целых числах должно приводить к логарифмическому закону, если оно (определение) применимо к вероятности появления значения ведущего разряда. Конечно, при работе в формате с плавающей точкой используются, в основном. нецелые числа, а мы анализировали целые числа, в первую очередь, потому, что этот предмет более знаком и анализ выполняется существенно проще.
Если рассматривать произвольные действительные числа, то теоретические результаты получить сложнее. Однако постепенно накапливаются доказательства, что имеет место та же статистика в том смысле, что повторяющиеся вычисления с действительными числами будут почти всегда иметь тенденцию ко все большему приближению к логарифмическому закону по отношению к дробным частим. Например, Петер Шатт показал (Ресег БсЬа11е, Хе/ГзсЬпЯ Гцг ап8енвлг]се МасЬ. шЫ Мес]ммн)г 53 (1973), 553 — 565), что при весьма слабом ограничении функция распределения произведения независимых случайных действитедьных переменных, имеюп1их один закон распределения, стремится к логарифмическолгу закону.
Сумма таких переменных ведет себя так же, но только для повторяющегося усреднения. Аналогичные результаты были получены в работе Л. 1. Ваг1ож, Е. Н. Ваге]вв, Сотриипб 34 (1985), 325-347. УПРАЖНЕНИЯ 1, [1у) Если в и а — десятичные числа в формате с плавающей точкой, амеющис аА» и гнетя ясе знак, то каково согласно табл. 1 и 2 приближенное значение вероятности того, чта при вычислении значения в й а произойдет переполнение дробной части? 2. [40] Проведите дальнейшие эксперименты со сложением и вычитанием чисел в формате с плавающей точкой для подтверждения н уточнения данных, приведенных в табл. 1 и 2.
3. [15] Найдите, исходя из логарифмического закона, вероятность того, что две начальные цифры десятичного числа в формате с плавающей точкой будут "23". 4, [М18] В тексте раздела отмечено, что начальные страницы интенсивно используемых таблиц логарифмов потрепаны в большей степени, нежели последние. Какие страницы были бы самымн потрепанными, если бы мы работвлн с таблицей анягилагарвфмое, т.
е. с таблицей, которая для двннога значения 1ойщ х указывает значение ху б. [М20) Предположим, что вещественное числа П равномерно распределено в интервале 0 < 17 < 1, Каково распределение значений наиболее значимого разряда 1гэ 6. [28) Если бы адно двоичное слово содержала и+1 бит, то можно было бы использовать р бит для представления дробкой части двоичных чисел с плавающей точкой, один бит— для знака н и — р бит — для порядка. Зта означает, что интервал изменения представимых значений, т. е.
отношение наибольшего положительного нормализованного значения к наименьшему, равен, по существу, 2~ . То же машинное слово можно было бы использовать и для представления щес~внодкавгервчнмх чисел в формате с плавающей точкой, выделив р + 2 бит для дробной части ((р + 2)/4 щестнадпатеричных цифр) и и — р — 2 бит для 2 г 2 порядка. 2бгда интервал изменения значений был бы 16 = 2~, т. е.
тем же, что и раньше, причем с большим числам битов в дробной части, Может сложиться впечатление, что получена нечто нз ничего, однако условие нормализации в случае основания 16 слабее в том смысле, что дробная часть может содержать нули в трех старших значпмых битах. Таким образом, не все р+ 2 бнт»значащие". Исходя нз логарифмического закона, выясните, какова вероятность того, что дробная часть положительного нормализованного шестнадцатеричного числа в формате с плавающей точкой имеет в точности О, 1, 2 и 3 нулевых наиболее значимых битовУ Осковываясь на материале, изложенном в этом разделе, рассмотрите вопрос о достоннствах шестнадцатеричной системы в сравнении с двоичной.
У. [1»М88] Докажите, что ие существует функции распределения Р(и), удовлетворяющей соотношению (Б) для каждого целого числа Ь > 2 и для всех вещественных значений г из интервала 1 < г < Ь. 8. [ДМ88] Выполняется лн соотношение (10) при ш ж 0 для соответствующим образом выбранного №(е)1 9, [НМ88] (П. Дьяконис (Р. )ушсоп(з),) Пусть Р~(и), Рг(и), ... — некоторая последовательность функций, определенных повторяющимся усреднением функции Ро(п) в соответствии с формулой (9). Докажите, что йш Р (и) = РЬ(1) для всех фиксированных и. ь 10 [1»М88] В тексте 1заздела показано, что см м 1ойш г — 1+ ем, где г»» стремится к нулю при пг -+ оо.
Найдите следующий член в асимптотическом разложении для с 11. [М)8] Докажите, что если П вЂ” случайная величина, распределенная по логарифмическому закшгу, то этим же свойством будет облапать и величина 1/П. 12. [НМ88] (Р. Ъ'. Хэммннг (В. ЪЧ. Напппйгй).) Цель этого упражнения — показать, что результат умножения в формате с плавающей точкой соответствует логарифмическому закону лучше, чем сомножители. Пусть (/ и У вЂ” случайные нормализованные положителькые числа в формате с плавающей точкой, имеющие независимое распределение с функциями плотности вероятности /(я) н 8(я) соответственно.
Тогда / < г н /„< з с вероятностью /ць Я~з /(я)8(8)888я, тле 1/Ь < г,е < 1. Пусть Л(я) — функция плотности вероятности дробной чести (/ х У (неокруглшшой). Определим меру егвялоиенвл А(/) функции плотности вероятности / как максямальную относительную сяпибку А(/) = шах где Дя) = 1/(х 1п Ь) есть плотность логарифмической функции распределения. Доказгите, гго .4(Л) < ш(п(А(/), А(8)). (В частности, если некоторый множитель име. ет логарифмическое распределение, то и произведение будет иметь такое распределение.) ° 13. [М80] В алгоритме умножения чисел с плавающей точкой (алгоритм 4.2.188) число сдвигов влево, требуемых прн нормалнзапии, равно нулю или единице в завнспмостн от того, будет лн /„/„> 1/Ь, Предполагая, что операнды распределены независимо по логарифмическому закону, найдите вероятность того, что для нормализации результата не потребуется ни одного сдвига влево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
