Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 80
Текст из файла (страница 80)
Если 1/Ь < ис < 1/6, то 0 < ис — в З с < 36 з, так что в етом случае относительная ошибка ограничена величиной 36 ~/ии < 36 г. Возьмем в качестве бз ббльшую из этих двух оценок, а именно — ЗЬ ~. В случае деления требуется более тщательный анализ программы 1), Величина, действительно вычисленная подпрограммой, будет равна а — б — Ье((а — б" ) (/) — б') -б"') -6„, где а = (и, + вц)/Ье, /) = ш/Ьс,„; неотрицательнме ошибки отбрасывания, равные (6,6', б",6'"), не превышают (Ь 'о, Ь ~,6 ~,6 е) соответственно; наконец, б (ошибка, возникающая при отбрасывании в процессе нормализации) неотрицательна и меньше либо Ь э, либо Ь е в зависимости от того, происходит ли сдвиг. Действительное значение частного есть а/(1 + Ьеб) = а — Ьеаб + Ь а)1~6"", где бье — неотрицательная ошибка, возникающая при отбрасывании бесконечного ряда в (2).
Здесь бзз < ез: Ь 'о, так как ряд знакопеременный. Следовательно, относительная ошябка равна абсолютному значению выражения (Ьеб' + Ьеб"4/а + Ьсб"'/а) — (б/а + Ьеб'б"/а + Ь~б~бел + 6 /а), умноженному на(1+Ьед). Положительные члены зтоговыраженияограниченывеличияойЬ э+Ь "+Ь э, а отрицательные ограничены (по модулю) величиной Ь е + Ь 'з + Ь а плюс вклад от фазы нормализации, велнчипа которого может достигать Ь г. Таким образом, яспо, что потенциально наибольшаи составляющая относительной ошибки возникает в процессе выполнения нормализации, и можно считать, что значение бз: (Ь + 2)6 а является надежной верхней границей для относительной ошибки. 8.
Сложение. Если е, < с + 1, то всв относительная ошибка возникает в процессе нормализации и она ограничена значением Ь '. Если е„> е»+2 и если знаки операндов совпадают, то, опять же, вся ошибка может быть отнесена на счет нормализации; если знаки противоположны, то ошибка, связанная со сдвигом разрядов из регистра, противоположна ошибке, возникающей после этого в ходе нормализации.
Обе составляющие ограничены значением Ь ~; следовательно, А = Ь г. (Это существенно лучше результата упр. 7,) Умножение. Анализ, аналогичный вмполнеиному в упр. 7, дает 6» = (Ь+ 2)Ь». РАЗДЕЛ 4.2.4 1. Так как переполнение дробной части может происходить зол»ко при операндах одного знака, искомая вероятность равна вероятности переполнения дробной части, деленной на вероятность совпадения знаков операндов, т. е.
7%/(э(91%)) = 15%. 3. 1ойш 2.4 — !обш 2,3 ж 1.84334%. 4. Страницы были бы потрепаны равномерно. б, Вероятность того, что 10/и < г, равна (г-1)/10+(г — 1)/100+ -. = (г-1)/9. Поэтому в рассматриваемом случае ведущие цифры распределены раеие»»ерно, например ведущая цифра 1 встречается с вероятностью -', б. Вероятность того, что имеется три нулевых ведущих бита, раина 1оК,»2 = », 1 вероятность того, что два ведущих бита нулевые, равна !оК, 4 — 1об,е 2 = 71 аналогично и для двух других случаев. "Среднее" число нулевых ведущих битов равно 11, так что "среднее" число "значащих битов" есть р+ -', Однако наихудший случай, р — 1 значащих битов, встречается с довольно высокой вероятностью.
На практике, как правило, опенки ошибок необходимо проводить на основе наихудшего случая, поскольку цепь вычислений настолько "прочна", насколько прочно слабейшее звено. Как следует из анющза ошибок в разделе 4.2.2, верхняя граница относительной ошибки округления равна 2' " для шестнадцатеричной сигтемы счисления. При работе в двоичной системе счисления можно получить р + 1 значащих битов во всех нормализованных числах с относительной ошибкой округления, ограниченной значением 2 ' " (см. упр. 4.2.1-3), Обширные вычислительные эксперименты подтверждают утверясдение, что вычисления в двоичном формате с плавающей точкой дают более точные результаты, чем аналогичные вычисления в шестнадцатеричном формате с плавающей точкой, даже когда точность представления двоичных чисел равна р бит, а не р + 1. Из табл.
1 и 2 видно, что шестнадцатеричная арифметика может быть сделана чуть более быстрой, так как для нее необходимо меныпе циклов цри масштабировании посредством сдвига вправо или нормализации посредством сдвига влево. Но этот фактор оказывается несущественным в сравнении с теми неоспоримыми преимуществами, которые имеет выбор Ь = 2 над другимя основаниями (см. также теорему 4.2.2С и упр.
4.2.2-13, 15, 21), в особенности„если принять во внимание, что моною достичь той же скорости вычислений в двоичном формате с плавающей точкой, что и в шестнадцатеричном, ценой очень незначительного повышения суммарной стоимости процессора. 7. Предположим, что 2 (»г(10 5») — г'(10» )) = 1ОК5»/!ОК10 и что (Р(10" » . 4») — Г(10" »)) = !оК 4»/!оК 10"; тогда 2 (Г(10»т ° 5») — Г(10» 4»)) = 1ОК»о 4$ для всех Ь. По данному малому положительному числу е выберем 6 > 0 так, чтобы Г(к) < е при О < з < 6, и выберем М > 0 так, чтобы г'(я) > 1 — е при я > М.
Можно взять Ь столь большим, что будут выполняться неравенства 10 " 5~ < е и 4" > М; следовательно, в связи с монотонностью функции К получаем ~ (Р(10~ .5*) — Р(10 .4 )) »» < ~ (Р(10 и 5ь) — Р(!Ощ 0.5~))+~ (Р(10ы ен 4 )-Р(10ь 4 )) »»до »»йе = Р(10 5 )+1 — Г(10 4 ) <2н 6. Если е > г, то Ре(10"е) равно 1 при малых и и равно О, если (1О"е) > (1О"г!'. Нанменыпее и, для которого так бывает, может быть произвольно большим, так что для !»е(е) нельзя дать никакой равномерной оценки, не зависящей от е, (Вообще говоря, в учебниках по анализу доказывается, что из такой равномерной оценки следовало бы, что предела»»ая функция 8о(е) непрерывна, а зто не так.) 9. Пусть дм йм ...
таковы, что Ре(н) = дз (~„) + дт (", ') + . для всех и. Тогда Р„,(п) = 1 ~9~(" ')+2 ~дз(",')+ длявсех»лип. 10. Если 1 < г < 10, производящая функция С(х) имеет простые полюсы в точках 1+ ш„, где ш„ж 2»пн/ 1и 10. Следовательно, -»„м ° 1 — х ш„(!и 10)(х - 1 — ш„) ьие где Е(х) есть аналитическая функция иа всей плоскости.
Таким образом, если д = агссап(2к/!п10), то 2 г -»» ы» см-!ой,ег-1 — — 7 Я~ ~+е,п 1п10 ~~ '»и (1+ш ) е!п(»нд + 2к !ой»') — чп(шд) () ) !ой ег 1+ гз + к(1 + 4кт/(!и !0)з) г (1+ 1бт~/(!и 10)~) 11. Если величина (!ойе У) шоб1 равномерно распределена в интервале (О ..
1), то так же распределена и величина (!о6„1/У) шоб 1 м (1 — 1ойь (/) шоб 1. 12. Нм ем Ь(х) = !/ /(х)»(хд(л/Ьх)/Ьх+ !/ /(х)»)хд(х/х)/х; .г~!ь з» следовательно, »<)-'») Г' „,»е»»е-юс~»)»»(ь»-с»» !(а) 3ц ь !(л/Ьх) /» !(х/х) 'Так как /(х) > О, )(Ь(х) — !(з))/!(л)) < /' /(к)»(хА(д) + ~'/(х)»!хА(д) для всех х А(Ь) < А(д). В силу симметрии А(Ь) < А(/). (Вей Яуасеш ТесЬ. у. 49 (1970), 1609-1625.) 13. Пусть Х = (!ой„У) шоб1 и У = (!обе 1') шов!, так что Х и )» независимо и равномерно распределены в интервале (О ..
1). Ни одного сдвига влево не потребуется тогда и только тогда, когда Х + У > 1, и зто происходит с вероятностью -'. (Аналогично результат выполнения деления по алгоритму 4.2.1М не нуждается в нормэлизующих сдвигах с вероятностью -,,', здесь достаточно более слабого предположения о совпадении распределений независимых операндов.) 14. Для удобства вычисления проводятся здесь для Ь = 10. Если й = О, то вероятность переноса равна ( //- — у 2 /,~з,У„ !п10/ /'<»«5'е т у »+«31« (рис. А-7).
Интеграл равен ~.~е,~ ~«е,~ ~«» .~а 01 10 1 О 1О Рис. А-7. (Последний интеграл, по существу, является "билогарифмическим".) Значит, вероятность переноса при Ь = О равна (1/)п10)з(яз/6 — 2~"„>,1/п«10") ш,27154, (Заме»опас, Если Ь = 2 и Ь = О, переполнение дробной части происходит есе«де, так что этот вывод подтверждает справедливость соотношения 2 >, 1/и«2" = кз/12 — ()и 2)~/2.) Если Й > О, вероятность равна Таким образом, если Ь = 10, переполнение дробной части должно возникать с вероятностью приблизительно .272ро+.017р~+.002рз+., Когда Ь = 2, соответствующие величины равны ре+ 655р~+ 288рт+.137р«+ 067р«+ 033р«+ 016ре+ 008рг+.004р«+.002рэ+.001рш+ Если теперь воспользоваться значениями вероятностей из табл.
1, разделив их на .91 для устранения нулевых операндов, н принять, что вероятности не зависят от знака операндов, можно при Ь = 10 предсказать значение вероятности около 14% против 15% из упр. 1. При Ь 2 мы предсказываем значение, приблизительно равное 48%, в то время как таблица даст 44%. Эти раскол<дания, конечно, лежат в допускаемых пределах, если учтена ошибка эксперимента. 16. Если Ь = О, то старшая цифра равна 1 тогда и только тогда, когда возникает перенос.
(Возможно, что при Ь > 4 в результате переполнения дробной части и последующего округления жилится ведущий разряд, равный 2, но в этом упражнении округление игнорируется,) Как показано в предыдущем упражнении, вероятность переполнения дробной части равна приблизительно .272, а,272 < )ой,е 2. Если !с > О, то ведущий разряд равен 1 с вероятностью (ь)'У" '/ "--. -") (+)'(/" '/ "-) =- 16. Для доказательства положения, сформулированного в указании !его авторство принадлежит Ландау ()апбап, Ргасе Масешасусэпо-Уму<зле 21 (1910), 103-113)), слачааа предположим, что !ппэпра„= Л > О.
Пусть е = Л/(Л+ 4М), н выберем Ж так, что )а~ + ° + а ! < 7«<Лп длв всех и > !»'. ПУсть и > /6/(! — <), и > 5/с бУдет таким, что а„> ~5Л. '1Ъгда по индукции а„«> а„- ЬМ/(и — сн) > -'Л для 0 < Ь < сп и Е»-,»<«6» а«> Р(сп — 1) > 1Л<п. По Е»-с»<«6» «! (.с.,!5«6» ° с 18«6»»» «! $ так как и — сп > А!. Аналогичное противоречие возникает н если Иш!п(о < О. Предполагая, что Р +|(«) -| Л при и | оо, положим а| = Рм(Ь) — Л.
Если пз > О, то а| удовлетворяют гипотезе, сформулированной в указании, поскольку 0 < Р„,(Ь) < 1 (см. 4,2.2-(15)); отсюда Р («) -| Л. 17. См. Х Ма|Ь. Яос. аврал 4 (1952), 313-322. (Тот факт, что гармоническая вероятность расп|ирнет понятие обычной вероятности, следует из теоремы Чезаре (Сеэ1ао, А|Н дейв Неа)е Асслдет!а де| Ъ|лсш, Непд(сопб (4) 4 (1888), 452-457).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
