AOP_Tom2 (1021737), страница 79
Текст из файла (страница 79)
[М80] Оцените точность вычислений в подпрограммах этого раздела, работающих с форматом удвоенной точности, подыскав подходящие постоянные бм бз и бз, которые могут служить верхними границами для относительных ошибок [((ибЪи) — (и+с))/(и+с)[, [((иЗс) — (и х с))/(и х о)[, [[(и З о) — (и/о)) /(и/е)] . Однократная точность 45.5п 49.5п 46и 52и Удвоенная точность 64п 68и 109и 126.5п 8. [Мйй) Оцените (в смысле упр. 7) точность усовершенствованных подпрограмм вычислений с удвоенной точностью из упр.
4 и 5. 8. [М42) В работе Т. Я. Реккег, Хитег. Ма15. 18 (1971), 224-242, предлагмтся альтернативный подход к вычислениям с удвоенной точностью, полностью базирующийся на методах вычиглений с однократной точностью. Например, теорема 4.2.2С утверждает, что и+ е = ю+ г, где ю = и 9 е н г = (и 9 ю) 9 е, если [и[ ) [е[, а основание системы счисления равно 2. Здесь [г[ < [ю[/2", так что пару (ю,г) можно рассматривать в качестве версии и+ е с удвоенной точностью.
Для сложения двух таких пар (и, и') 9 (е, е'), где [е'[ < [и[/2г и [е'[ < [еД2г, [и[ > [е[, Деккер предложил точно вычислить сначала и + е = ю + г, затем — приближенное значение остатка е = (г 9 е') 9 и' н наконец вернуть в вызывающую программу в качестве результата значение (ю 9 з, (ю 9 (ю 9 в)) 9 е).
Проанализируйте точность и эффективность такого подхода в глучм, когда он используется рекурснвно для вычислений с учетверенной точностью. 4.2.4. Распределение чисел в формате с плавающей точкой Чтобы дать усредненную картину поведения алгоритмов, использующих арифл~етические операции с числами в формате с плавающей точкой (и, в частности, чтобы определить среднее время выполнения таких алгоритмов), потребуется некоторая статистическая информация, позволяющая подсчитать частоту появления различных случаев.
В этом разделе будут проанализированы эмпирические и теоретические свойства распределения чисел в формате с плавающей точкой. А. Программы сложения и вычитания. Время выполнении операций сложения н вычитания чисел с плавающей точкой в значительной мере зависит от исходной разности порядков, а также от числа необходимых шагов нормализации (влево или вправо).
До сих пор неизвестна хорошая теоретическая модель, которая предсказывала бы ожидаемые характеристики, но мы располагаем результатами обширных эмпирических исследований, проведенных Д. У. Суини [Р. Ж. Бюеепеу, 1ВМ Вуэ1ешэ Х 4 (1965), 31-42).
При помощи специальной программы трассировки Суини проследил выполнение шести "типовых" программ вычислений большой сложности, отобранных в различных вычисяительных лабораториях, и тщательно исследовал каждую операцию сложения н вычитания чисел с плавающей точкой. В процесс сбора этих данных было вовлечено более 250 000 таких операций. Примерно одной нз каждых десяти команд, выполненных тестируемыми программами, была либо гАРР, либо г90В. Поскольку вычитание есть не что иное, как сложение, в котором второй операнд взят с противоположным знаком, все такого рода статистические данные можно рассматривать как относящиеся только к сложению.
Результаты, полученные Суини, можно подытожить следующим образом. Одно из двух слагаемых равнялось нулю примерно в 9% всех случаев, и обычно это был аккумулятор (АСС). Остальные 91% случаев распределились примерно поровну между одинаковыми н противоположными знаками операндов, а также примерно поровну между случаями, когда [и[ < [е[ н когда [е[ < [и[, Вычисленный результат равнялся нулю примерно в 1.4% случаев. Поведение разности между порядками приблизительно описывалось распределениями вероятностей, приведенными в табл. 1, для разных значений основания 5. Таблица 1 ЭМПИРИЧЕСКИЕ ДАННЫЕ О СООТНОШЕНИЯХ МЕЖДУ ОПЕРАНДАМИ ПЕРЕД ВЫПОЛНЕНИЕМ СЛОЖЕНИЯ Таблица 2 ЭМПИРИЧЕСКИЕ ДАННЫЕ О НОРМАЛИЗАЦИИ ПОСЛЕ ВЫПОЛНЕНИЯ СЛОЖЕНИЯ 1Строка "Свыше бе в таблице содержит, по сути, все случаи, когда один операнд был равен нулю, но в строку "В среднем" онн не включены.) Когда и н и имеют одинаковые знаки и нормализованы, прн вычислении суммы и + о либо требуется осуществить сдвиг на один разряд вправо (в связи с переполнением дробной части), либо вообще не требуется выполнять сдвиги в процессе нормализации.
Когда и н о имеют противоположные знаки, при нормализации происходит сдвиг влево на нуль нли более разрядов. В табл. 2 представлены данные наблюдений за распределением количества сдвигов. В последнюю строку вошли все случаи, когда результат был равен нулю. Среднее число сдвигов влево в процессе нормализации равнялось примерно 0.9 для 6 = 2, около 0.2 — -для Ь = 10 или 16 и около 0.1 — для 6 = б4. В. Дробные части. Дальнейший анализ программ, работаншгнх с числами в формате с плавающей точкой, можно проводить на основе статистического распределения дробных частей случайно выбранных нормализованных чисел. Здесь обнаруживаются весьма удивительные факты н имеется интересная теория, объясняющая зтн феномены.
Для удобства временно предположим, что мы имеем дело с числами в десятичной системе счисления; последующие рассуждения легко распространяются на любое другое положительное основание Ь. Предположим, что дано "случайное" положительное нормализованное число (е, у) = 10' 1. Поскольку У нормализовано, его ведущий (наиболее значимый) разряд равен 1, 2, 3, 4, 5, 6, 7, 8 илн 9, и, казалось бы, естественно предположитгч что каждая из этих цифр встречается в качестве ведущей приблизительно в 1/9 всех случаев. Однако на практике картина оказалась совершенно иной. Например, ведущий разряд равен 1 более чем в 30% случаев! Один из способов проверить это утверждение состоит в том, чтобы обратиться к таблице физических постоянных (наподобие скорости света, гравитационной постоянной и т. п.) из какого-либо справочника.
Заглянув, например, в НапдЬоок оГЛ1агИ- ешабса) Гппсг1опэ (Б. 8. Перс оГ Сопппегсе, 1964), можно обнаружить, что у 8 из 28 различных физических постоянных, приведенных в табл, 2.3, а это примерно 29% случаев, ведущий разряд равен 1. Значения и! в десятичной системе при 1 < и < 100 включают ровно 30 элементов. начинающихся с 1: то же самое относится к десятичным значениям 2" и Г„при 1 < и < 100.
Можно было бы заглянуть также в отчеты о переписи населения или в "Календарь фермера" (но не в телефонный справочник). В те не такие уж далекие времена, когда не было карманных калькуляторов, в таблицах логарифмов, которые часто использовались, как правило, первые страницы были довольно грязными, потрепанными, а последние оставались сравнительно чистыми и, на первый взгляд, нетронутыми.
По-видимому, впервые это явление было отмечено в печати американским астрономом Саймоном Ньюкомбом [Яшоп ХеъсошЬ, Ашег. Х Маг1ь 4 (1881), 39 — 40], который привел разумные доводы в пользу того, что цифра д встречается в качестве ведущей с вероятностью (ойш(1+1/6). Тот же закон распределения много лет спустя был эмпирически открыт Ф. Бенфордом (Г. Венного, Ргос, Ашег. РЛйоэор1нса1 5ос. 78 (1938), 551-572), который сообщил о результатах 20 229 наблюдений, взятых из других источников. Для того чтобы "прочувствовать" этот закон ведущего разряда, давайте внимательно посмотрим, как записываются числа в формате с плавающей точкой.
Если взять произвольное положительное число и, то его дробная часть будет определиться по формуле 107"„= 10~ма э "1 'в ' Следовательно, ведущий разряд в ней будет меньше, чем Ы, тогда и только тогда, когда (1ойще и) шоб 1 < 1ой,р Ы. Далее, если имеется какое-либо "случайное" положительное число У, выбранное из совокупности, которая существует в природе, то можно ожидать, что числа (1обш У) шоб 1 будут равномерно распределены между нулем и единицей или по крайней мере их распределение будет достаточно близко к равномерному. (Аналогично мы ожидаем, что так же равномерно распределены величины У шо61, Уз спой1, ~(У+яшо61 и т. д. Мы уверены, что колесо рулетки беспристрастно, в основном, по этой же причине,) Значит, из неравенства (1) следует, что единица будет ведущей цифрой с вероятностью 1ойш 2 ю 30.103%, двойка — с вероятностью 1ойю 3 — !ой,е 2 а 17.609%, и вообще, если г — пРоизвольное вещественное число, заключенное между 1 и 10, приблизительно в 1ойю г всех случаев должно выполняться неравенство 10Хи < г.
Поскольку ведущие цифры, в основном, небольшие, наиболее распространенная методика оценки "средней ошибки" при вычислениях в формате с плавающей точкой становится неверной. Относительная ошибка вследствие округления обычно оказывается несколько болыней, чем ожидается. р(г) = Рг((1ойгаП) шоб1 < !обшг). Согласно сделанному ранее предположению имеем также р(г) = Рг((!ой,е (/+!ок, с) шод 1 < 1ок, г) Рг((!ой,э П шоб 1) < 1ойш г — 1ойщ с или (1окге П шоб1) > 1 — 1ойгес), Рг((1ояш (/ пкк! 1) < 1ойш г + 1 — !окш с и (!ок, е Г шоб 1) > ! — !ок э с ), если с < г; если с > г; р(г/с) + 1 — р(10/с), если с < г; р(10г/с) — р(10/с), если с > г. (2) Продолжим теперь функцию р(г) вне интервала 1 < т < 10, положив р(10"г) = р(г) + и.
Тогда, заменив 10/с на Ы, можно записать последнее соотношение в (2) в виде р(г 1) = р(г) + рИ) (3) Если верно предположение об инвариантности распределения относительно умножения на произвольный постоянный множитель, то соотношение (3) должно выполняться для всех г > 0 и 1 < Ы < 10. Из того факта, что р(1) = 0 и р(10) = 1, теперь следует: 1= р(10) = р((АО)") = р(ъ710)+р((ЯО)" ') =" = пр(ЯО) отсюда приходим к заключению, что для всех положительных целых пт и и справедливо равенство р(10™~") = т/и. Если дополнительно потребовать, чтобы распределение р было непрерывным, то можно прийти к заключению, что р(г) = (ок,ег, а это и есть искомый закон.
Хотя данный аргумент, возможно, и убедительнее предыдущих, он тоже в действительности не выдерживает придирчивой проверки, если строго придерживаться Разумеется, можно справедливо утверждать, что приведенные выше эвристические доводы не доказывают сформулированного закона. Они только указывают правдоподобные причины того, что поведение ведущих цифр именно таково, каково оно есть на самом деле. Интересный подход к анализу значений ведущих разрядов был предложен Р. Хэммингом (К. Напнп!пк). Пусть р(г) — вероятность того, что 10/и < г, где 1 < г < 10 и /и — нормализованная дробная часть случайным образом выбранного нормализованного числа К Если говорить о случайных величинах в реальном мире, то можно заметить, что они измеряются в произвольных единицах, и если изменить, скажем, определение метра или грамма, то многие из фундаментальных физических постоянных будут иметь другое значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
