lekcii (Лекции), страница 2

Программная поддержка длинной арифметики имеется в языках Ру<Ьоп (встроенный тип или перегрузка операторов) и Заъа (библиотечные функции). Позднее мы приведем реализации длинной арифметики на Паскале и на Си, так необходимые на олимпиадах по программированию. Лекция 20 3.2.4 Тип вещественный Как известно из курса математического анализа [82, 93[, следующим за целыми числаъли уровнем числовой абстракции стали рациональные числа, позволившие выражать отношения и пропорции. Рациональное число можно представить (не единственным образом!) в вид<, отношения целого и натурального г = †, г Е Я, р Е,'Е, <? Е 1<1.

=р <? Рациональные числа используются для более точного измерения отрезков и промежутков времени. Но еще в Древней Греции последователи Пифагора обнаружили несоизмеримость диагонали квадрата и его стороны [81[ и длины окружности с ее диаметром, выражаемых иррациональными числами. Позже, в середине Х1Х века, было установлено, что множество вещественных чисел несчетно и всюду плотно. В частности, вся эта бесконечная и всюду плотная числовая ось с помощью процедуры диагопализации Кантора однозначно отображается в любой конечный отрезок этой же самой числовой оси.

Из эт<н о сл<щует, что простым ограничением диапазона вещественных чисел мы не загоним этот отрезок в прокрустово ложе м<ппинцого с н>ва ограниченной длины, как мы это успешно сделали для целого типа. Пеобходимо предпринять более кардинальные меры. Естественным ограничением для представления одного числа в однол< машинном слове является отсутствие бесконечных или конечных, но очень длинных чисел.

Это означает, что мы вынуждены будем опустить при ъ«ъп<инноъ< представлении не только все иррациональные числа, но и подавляющее болыпинство рациональных чисел, за исключением лишь конечного их числа (если, конечно, мы нс будем прибегать к такой экзотике., как систеълы счисления с иррациональными основаниямир?). Если г<о1>учить ~~~~~~ этого оставшш ося ~о~с~~~~~ ~~~~~~~~~ «н1ъедставите.~<ьс«ие» функции относительно всех невошедших в президиум соседних чисел в некоторой окрестности, то мы получим машинный суррогат великого и ужасного веи<ественного континуума в виде конечных рациональных приближений. Вместо обычных конкретно-числовых множеств мы получим интервальные, Складывая два таких числа.-интервала своеобразной интервальной арифметикой, мы получиъл интервал для суммы.

153 Для решения проблемы ъл цпинного представления вещественных чисел осталось только предложить кодировку этих конечных рациональных приближений кодовыми комбинациями машинного слова. Замечание. При использовании одного и гого же машинного слова для представления целых и вещественных чисел оказывается, что машинных вещественных чисел даже меньше, чем целых ввиду неоднозначности представления. Как же все-таки машинные вегцественныс числа смогут выполнять свои исторические предначертания в расширении диапазона и в удобстве представлении дробных чисел'? В 1937 году, еще до создания первых компьютеров немецкий инженер Конрад Цузе, основываясь на экспоненциальной форме записи числа, предложил полулогарифминеский формат представления вещественных чисел в ЭВ.'»1. Число — 1.23 в экспоненциальной форме может быть представлено как — 1.23 10о, или как — 0.123 101, или как — 12.3 10 '.

То есть число разлагается на произведение (неправильной) дроби (мантиссы) и экспоненциальной части (экспоненты), являющейся целой частью логарифма этого числа по основанию порядка. У дроби есть целая и дробная части,которые в данной системе счисления интерпретируются полиномиальным способом, причем для вычисления дрооной части используется полипом по отрицательным степеням. При этом основания системы счисления для дроби и для экспоненты, вообще говоря, могут быть разными. Цузе предложил число — 1.23 перевести в нормализованную форму — 0.123 10 и представить в ЭВМ тремя частями одного машинного слова. — 1 123 Тем самым мы НОлучили Весьма эконОмнОс предстаВление ВсщсстВснного числа, ОпустиВ ведущий О, дссятичну|о точку, СИМВОЛ порядка (Основание систсыы счисления для п1юдставления порядка) и связыванъщий элементы экспоненциальной записи знак умножения.

Кроме того, ранее было опущено также основание системы счисления для целой и дробной частей числа. Мы сразу же поместили знак числа в отдельное поле машинного слова. потому что при представлении отрицательных вещественных чисел в ЭВМ дополнительное кодирование не дает таких замечательных преимуществ как в случае целого типа. Вышеприведенные примеры записи числа — 1.23 показывают неоднозначность такого представления вещественных чисел в ЭВЛ!. Однако существует простой способ избавиться от этой неоднозначности: необходимо потребовать, чтобы дробь была правильной и старший разряд числа всегда был ненулевым, подкорректировав соответствующим образом порядок. Такое однозначное представление числа называется нормализованным.

Опустив то зкув записи числа мы предполагаем ее наличие перед первым (ненулевым!) разрядом записи числа. При делении числа — 1.23 на 10 с последующей нормализацией и подразумеваемая десятичная точка, и цифры 123 останутся на месте, т!тобы правильно представить нормализованное частное при неподвижной точке надо чтобы «поплыл» порядок. Поэтому полулогарифмическое представление назывется еще и представленим с плавааои1вй ппочкой (запятой).

Хотя этот устоявшийся тсрълип следует признать неудачным, т. к. на самом деле плавает нс точка, а порядок! 154 ПОСКО11ЬКу необходимо ггрЕ11етавдяГЬ НЕ только ОЧСНЬ бО.1ЬШИС: Чиода. гго И МВЛЫс. Около нуля. то порядки чисел могут быть и положительными, и отрицательн»гми, и возникает проблема представления знака порядка. Обычно она решается с помощью догголнительного кодирования; дополнительный код порядка называется характеристикой. В реальных КОМПЬЮТС;РВХ ДЛЯ ПРСгДСТВВЛЕНИЯ ВС.ЩССТВС.'ННЫХ сц1ССЛ ИСПОЛЬЗУЮТСЯ ДВОИ-1НЫЕ Ма1!1ИННЫСг слова,, и основанис; системы счисления для мантиссы подразумевается тоже двоичное.

Л вот для расширс'ния диапазона, представимых чисел основание порядка, (характеристики) иногда бывает шестнадцатиричным (1ВМ!360). Это., правда,, понижает точность представления, поскольку в сгдин и тот же диапазон при меныпем порядке попадет больше чисел. Итак, мы представили вещественные числа в ЭВМ конечными рациональными приближенияъси. За пределами нашего рассмотрения пока осталась точность этого приближения — ширина отрезка, представляемого данным числом. Наиболее простым решением было бы выбрать ширину этого отрезка Лх постоянной для всех чисел.

Однако Ьх = сопаг Чх бессмысленно с физической точки зрения, т. к. абсолютная погрешность г."гх измерения величины х должна быть обязательно соотнесена с ее значением. Из этого следует, что шиг.'гх рина отрезков должна подчиняться соотношению = совЫ, иными словами постоянной должна быть отгюсительная погрешность. Прибегая к дифференциальному исчислению сгх — = сопЫ, получим, что ширина отрс;зка меняется по экспоненциальному закону. Таким образом, для малых чисел ширина отрезка мала> а для больших -- пропорционально велика и на всем множестве машинных вещественных чисел обеспечивается одинаковая относительная погрешность представления. Теперь мы можем заняться формальным определением вещественного типа.

Множество изображений вещественного типа, . это множество слов конечной длины над алфавитом 1'0,1,2,3,4, 5,6, 7,.8,910 1+, —,, Е7, причем длина слова, изображающего вещественное число, в языке программирования пе фиксирована и определяется с помощью соответствующих базовых атрибутов, которые имеют определенное значение для каждой реализации. Функция интерпретации определяется следующим образом: ННВАЬ(эгаггач...а,.

а,,а, а...аа Е В2а,ггьгггл г ..а~.,) знак ггорлдка символ порядка деслааичггал точка знак числа с и г г Е сс гог=вг ~~г а, 10с г+ ~ а; 10с ' 10 '=о а=с-1 где ао, ад,...,. ас цифры, изображаницие целую часть вещественного числа; а1, ал 1,..., аг. — цифры, изображаннцие дробную часть вещественного числа. Рассмотренное выше изоб1га кение получило название иредставление. с плавающей тонкой.

Фактичс:ски это специальным образом нормализованное экспоненциальное представ- 155 ление числа. Ранее существовало также представление с фиксированной пи>иной, при которл>м Точка подразумевалась В фиксгй>ованном месте машинного с:лова. Поскольку "гочносль представления с фиксированное точкой также фиксирована, то оно может применяться только для ограниченного диапазона чисел, в котором фиксированное представление имеет одинаковую абсасиогпнрю (Ьх = сопвс) погрешность, Фиксированная арифметика использовалась на бортовых и других встроенных компьютерах, работавших в реальном масштабе Времени, а также используется в современных СУБД (наприклер, для представления денежных величин). В некоторых языках программирования, ориентированных на эти сферы, есть вещественный тип с фиксированной точкой.

Это не только Лс1а, и Яс1?., но и Вог1апс1 Пе1рЫ1'Вп>1с1ег (тип Спггепсу). Итак, вещественное число с плавающей точкой фактически изображается с помощью двух целых чисел р и т, каждое из которых содержит конечное (фиксирслванное для каждой реализации) число цифр, так что вещественное число Х = т, л. В", причем тдлгехр < р < тахеху;тгппгап1 < т < тахтап$; т, называется ллантиссой; р --- порядлсолл, а В, тлгсехр, тахехр, птллпапЯ, и гглахгпап4 являются констаптахли, характеризующими представление; число В называется основанием представления с плавающей точкой. Итак, ИНТВещ(т, р) = т л. В". Для любого числа Х можно найти столько различных пар (гп, р), сколько позволяет ширина мантиссы.