8. [Л/Й5] Оцените (в смысле упр. 7) точность усовершенствованных подпрограмм вычислений с удвоенной точностью из упр. 4 и 5.

9. [М42] В работе Т. J. Dekker, Numer. Math. 18 (1971), 224-242, предлагается альтернативный подход к вычислениям с удвоенной точностью, полностью базирующийся на методах вычислений с однократной точностью. Например, теорема 4.2.2С утверждает, что U + V = w + r, где W = u®v и г = {uQw)®v, если и > а основание системы счисления равно 2. Здесь г < \w\/2, так что пару (w,r) можно рассматривать в качестве версии U + V с удвоенной точностью. Для сложения двух таких пар (и, u)®{v, v), где < и/2 и v < w/2, u > Деккер предложил точно вычислить сначала u + v - w + r, затем - приближенное значение остатка в = (гфг;)фии наконец вернуть в вызывающую программу в качестве результата значение (w ®s, {wQ{w ® s)) Ф s).

Проанализируйте точность и эффективность такого подхода в случае, когда он используется рекурсивно для вычислений с учетверенной точностью.

4.2.4. Распределение чисел в формате с плавающей точкой

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

А. Программы сложения и вычитания. Время выполнения операций сложения и вычитания чисел с плавающей точкой в значительной мере зависит от исходной разности порядков, а также от числа необходимых шагов нормализации (влево или вправо). До сих пор неизвестна хорошая теоретическая модель, которая предсказывала бы ожидаемые характеристики, но мы располагаем результатами обширных эмпирических исследований, проведенных Д. У. Суини [D. W. Sweeney, IBM Systems J. 4 (1965), 31-42].

При помощи специальной программы трассировки Суини проследил выполнение шести "типовых" программ вычислений большой сложности, отобранных в различных вычислительных лабораториях, и тщательно исследовал каждую операцию сложения и вычитания чисел с плавающей точкой. В процесс сбора этих данных было вовлечено более 250 ООО таких операций. Примерно одной из каждых десяти команд, выполненных тестируемыми программами, была либо FADD, либо FSUB.

Поскольку вычитание есть не что иное, как сложение, в котором второй операнд взят с противоположным знаком, все такого рода статистические данные можно рассматривать как относящиеся только к сложению. Результаты, полученные Суини, можно подытожить следующим образом.

Одно из двух слагаемых равнялось нулю примерно в 9% всех случаев, и обычно это был аккумулятор (АСС). Остальные 91% случаев распределились примерно поровну между одинаковыми и противоположными знаками операндов, а также примерно поровну между случаями, когда и < и когда < Вычисленный результат равнялся нулю примерно в 1.4% случаев.

Поведение разности между порядками приблизительно описывалось распределениями вероятностей, приведенными в табл. 1, для разных значений основания Ь.

Таблица 1

ЭМПИРИЧЕСКИЕ ДАННЫЕ О СООТНОШЕНИЯХ МЕЖДУ ОПЕРАНДАМИ ПЕРЕД ВЫПОЛНЕНИЕМ СЛОЖЕНИЯ

Таблица 2

ЭМПИРИЧЕСКИЕ ДАННЫЕ О НОРМАЛИЗАЦИИ ПОСЛЕ ВЫПОЛНЕНИЯ СЛОЖЕНИЯ

(Строка "Свыше 5" в таблице содержит, по сути, все случаи, когда один операнд был равен нулю, но в строку "В среднем" они не включены.)

Когда U и и имеют одинаковые знаки и нормализованы, при вычислении суммы и + V либо требуется осуществить сдвиг на один разряд вправо (в связи с переполнением дробной части), либо вообще не требуется выполнять сдвиги в процессе нормализации. Когда и и v имеют противоположные знаки, при нормализации происходит сдвиг влево на нуль или более разрядов. В табл. 2 представлены данные наблюдений за распределением количества сдвигов. В последнюю строку вошли все случаи, когда результат был равен нулю. Среднее число сдвигов влево в процессе нормализации равнялось примерно 0.9 для 6 = 2, около 0.2 - для 6 = 10 или 16 и около 0.1 - для 6 = 64.

В. Дробные части. Дальнейший анализ программ, работающих с числами в формате с плавающей точкой, можно проводить на основе статистического распределения дробных частей случайно выбранных нормализованных чисел. Здесь обнаруживаются весьма удивительные факты и имеется интересная теория, объясняющая эти феномены.

Для удобства временно предположим, что мы имеем дело с числами в десятичной системе счисления; последующие рассуждения легко распространяются на любое другое положительное основание 6. Предположим, что дано "случайное" положительное нормализованное число (е, /) = 10 • /. Поскольку / нормализовано,

его ведущий (наиболее значимый) разряд равен 1, 2, 3, 4, 5, б, 7, 8 или 9, и, казалось бы, естественно предположить, что каждая из этих цифр встречается в качестве ведущей приблизительно в 1/9 всех случаев. Однако на практике картина оказалась совершенно иной. Например, ведущий разряд равен 1 более чем в 30% случаев!

Один из способов проверить это утверждение состоит в том, чтобы обратиться к таблице физических постоянных (наподобие скорости света, гравитационной постоянной и т. п.) из какого-либо справочника. Заглянув, например, в Handbook of Mathematical Functions (и. S. Dept of Commerce, 1964), можно обнаружить, что у 8 из 28 различных физических постоянных, приведенных в табл. 2.3, а это примерно 29% случаев, ведущий разряд равен 1. Значения п! в десятичной системе при 1 < п < 100 включают ровно 30 элементов, начинающихся с 1; то же самое относится к десятичным значениям 2" и F„ при 1 < п < 100. Можно было бы заглянуть также в отчеты о переписи населения или в "Календарь фермера" (но не в телефонный справочник).

В те не такие уж далекие времена, когда не было карманных калькуляторов, в таблицах логарифмов, которые часто использовались, как правило, первые страницы были довольно грязными, потрепанными, а последние оставались сравнительно чистыми и, на первый взгляд, нетронутыми. По-видимому, впервые это явление было отмечено в печати американским астрономом Саймоном Ньюкомбом [Simon Newcomb, Amer. J. Math. 4 (1881), 39-40], который привел разумные доводы в пользу того, что цифра d встречсьется в качестве ведущей с вероятностью logio(l -f 1/d). Тот же закон распределения много лет спустя был эмпирически открыт Ф. Бенфордом [F. Benford, Ргос. Amer. Philosophical Soc. 78 (1938), 551-572], который сообщил о результатах 20 229 наблюдений, взятых из других источников.

Для того чтобы "прочувствовать" этот закон ведущего разряда, давайте внимательно посмотрим, как записываются числа в формате с плавающей точкой. Если взять произвольное положительное число и, то его дробная часть будет определяться по формуле 10/и = l0<°8io") mod 1 Следовательно, ведущий разряд в ней будет меньше, чем d, тогда и только тогда, когда

(logiou) modi < logiod. (1)

Далее, если имеется какое-либо "случайное" положительное число U, выбранное из совокупности, которая существует в природе, то можно ожидать, что числа (logio U) mod 1 будут равномерно распределены между нулем и единицей или по крайней мере их распределение будет достаточно близко к равномерному. (Аналогично мы ожидаем, что так же равномерно распределены величины U mod 1, mod 1, у/и + 7г mod 1 и т. д. Мы уверены, что колесо рулетки беспристрастно, в основном, по этой же причине.) Значит, из неравенства (1) следует, что единица будет ведущей цифрой с вероятностью logio2 « 30.103%, двойка - с вероятностью logio 3 - logjo 2 « 17.609%, и вообще, если г - произвольное вещественное число, заключенное между 1 и 10, приблизительно в logo г всех случаев должно выполняться неравенство lOfu < г.

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