Вернуться в библиотеку

Источник: Наукові праці ДонНТУ Серія “Інформатика, кібернетика та обчислювальна техніка” випуск 14(188) 2011

Программная модель преобразователя вещественных чисел в постбинарные форматы

Кулибаба С.В, Иваница С.В.

serzh@mail.ua,  isv@cs.donntu.ru

Донецкий национальный технический университет

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

Введение

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

В свете вышеизложенного представляются актуальными задачи проектирования, разработки и реализации базовых математических алгоритмов нижнего уровня, например, элементарных арифметических функций для встраиваемой процессорной системы. На начальном этапе проектирования должна быть решена важнейшая задача, связанная с обеспечением корректности вычислений, т. е. получения результата с гарантированной точностью. Решение такой задачи можно разбить на два этапа: 1-й этап — модификация форматов представления вещественных чисел (корректность представления данных); 2-й этап — введение дополнительных методов контроля точности для стандартных вычислительных алгоритмов (коррекция вычислений).

В данной работе показана реализация 1-го этапа, в ходе которой предлагается уход от традиционного (бинарного) представления вещественных чисел в ЭВМ в сторону постбинарного. При таком представлении чисел с плавающей запятой предложен ряд модифицированных форматов [1, 2], способных представлять не только вещественные числа как таковые, а и их совокупности в виде обыкновенных дробей (пара чисел — числитель и знаменатель) и интервалов (пара чисел — границы интервала).

Для последующей проверки алгоритмов арифметических и логических операций над постбинарными числами возникла необходимость разработки программной модели соответствующих форматов. При этом аппарат ввода чисел должен быть настолько гибким, чтобы имелась возможность представления сколь угодно точного отображения множества всех действительных чисел, т. е. преобразование входное число х ® постбинарный формат (pbinary[x]) и pbinary[x] ® выходное число y должно быть максимально точным и стремиться к равенству х = y.

В результате поиска программных продуктов, работающих с числами произвольной длины, было выявлено следующее: все программные модели представления чисел двоичной системе счисления (в частности, вещественных чисел) имеют ограничения на количество знаков после запятой и невозможность представления входных чисел и результатов в экспоненциальном виде. На фоне остальных приложений существенно выделяется бесплатная программа IEEE754 v.1.0 [3], которая способна выполнять преобразования вещественных чисел в формат одинарной или двойной точности стандарта IEEE-754 в обоих направлениях. Программа отображает абсолютно точные значения десятичных или двоичных чисел, может представлять исходные числа и результаты преобразования в экспоненциальном виде и позволяет вводить исходное десятичное число до 1074 значащих цифр в простом или экспоненциальном виде. Данный программный продукт был выбран в качестве прототипа к построению представленной далее модели преобразования десятичного вещественного числа произвольной точности в постбинарные форматы различной точности.

Программная модель постбинарных форматов

В современных вычислительных устройствах для представления действительных (вещественных) чисел используются форматы, соответствующие стандарту IEEE754-2008, которые состоят из полей знака, порядка и мантиссы числа. Такая же структура сохранена и в постбинарных форматах, однако поле мантиссы претерпело модификацию, выделив незначительное количество разрядов на поле идентификатора [2].

Программная модель PBinary является преобразователем исходного десятичного числа в двоичное, «упакованное» в постбинарных форматах. PBinary реализован на языке Java и занимает около 300 КБ дискового пространства. Создание модели PBinary в виде Java-приложения было обосновано, во-первых, кроссплатформенностью, и, во-вторых, повышенным быстродействием выполнения элементарных математических операций. Интерфейс программы PBinary представлен на рис. 1.

В поле ввода данных формируется исходное десятичное число, которое может вводиться с клавиатуры или загружаться из текстового файла. Переключатели «число», «дробь» и «интервал» позволяют представлять входные данные в виде одного числа, числителя и знаменателя дроби или границ интервала. Флажок «тетракод» позволяет отображать значения полей форматов в тетракоде, где каждая пара двоичных бит представляет значение тетрита tÎ{0, 1, A, M} [4] следующим образом: 00 для «А», 01 для «0», 10 для «1» и 11 для «М». Цифровой счетчик показывает количество значащих цифр исходного числа (в простом или экспоненциальном виде) которое будет учитываться при дальнейшем преобразовании (по умолчанию — 1024 цифры). Кнопки «Старт» и «Сбросить в 0» позволяют начать преобразование или обнулить полученные ранее результаты. Результаты всех выполняемых моделью PBinary преобразований записываются в информационные поля группы вкладок «pbinary32–pbinary256».

Названия вкладок «pbinary32–pbinary256» повторяют названия соответствующих постбинарных форматов различной точности. Тело каждой вкладки содержит следующие информационные поля:

1. Значения полей числа. Данное поле содержит информацию о структуре формата (рис. 2), названия и значения его полей (используется 2 с/с и 16 с/с), принадлежности числа к стандартному множеству (± нормализованное, ± денормализованное, ± ¥, не число (NaN)) и выбранном способе округления (в меню «Опции») при формировании значений полей формата (к нулю (без округления), к ближайшему целому, к + ¥ и к – ¥). Данное поле отображает результат преобразования х ® pbinary[x].

Рисунок 1 — Интерфейс программы PBinary

2. Значения, полученные из pbinary? — точные значения в виде вещественного числа с фиксированной точкой, полученные в десятичном или двоичном виде при «распаковке» полей текущего формата pbinary. Полученное значение можно отобразить в простом (рис. 3, а) и экспоненциальном (рис. 3, б) виде. Стоит отметить, что такие точные вычисления микропроцессор производить не способен, поэтому PBinary не использует математические возможности микропроцессора, а имитирует математические расчеты выполняемые вручную. Данное поле отображает результат преобразования pbinary[x] ® y .

3. Погрешность. В этом поле вычисляется абсолютная погрешность представления исходного числа в постбинарном формате. Значение погрешности позволяет оценить точность представления исходного числа и выбрать оптимальную точность (от 32 до 256 двоичных разрядов) для его хранения. Данное поле показывает, насколько верно равенство х = y.

Рисунок 2 — Представление полей формата pbinary128

В поле статуса окна программы выводится информация о времени преобразования, которое определяет временной интервал с момента нажатия на кнопку «Старт» и до заполнения всех информационных полей. Следует отметить, что при проведении многочисленных экспериментов с различными входными числами (и с различным количеством значащих цифр в числе) в пределах показателя экспоненты –1000 ¸ 1000, время преобразования ни разу не превысило 15-секундный рубеж.

а) 

б) 

Рисунок 3 — Вывод точного значения числа в 10 с/с, полученного из формата pbinary128, в простом (а) и экспоненциальном (б) виде

Структура программной модели PBinary

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

1) исходное десятичное дробное число невозможно точно представить ни в одном из стандартных вещественных форматов, т. к. десятичная дробь х₁₀ записывается в виде строки цифр a_k (0 £ a_k £ 9) c количеством n разрядов целой части и m разрядов дробной части числа

.                                                     (1)

По умолчанию исходная десятичная дробь может быть представлена значением n + m = 1024, однако эту сумму можно увеличить до 10 000. Такие числа в регистрах современных микропроцессоров непредставимы.

2) при преобразовании десятичной дроби в двоичную возникает необходимость представления рационального числа х₁₀ в х₂ в виде линейной комбинации (в большинстве случаев бесконечной) степеней числа 2:

,                                                       (2)

где b_k и c_k — цифры целой части и дробной части (b_k, c_kÎ{0, 1}), n — число разрядов целой части. При больших значениях n (например, в формате pbinary256 длина мантиссы равно 219 разрядам) не представляется возможным загрузить такое число в регистры современного микропроцессора.

Для преодоления возникшей ситуации было принято решение хранить все числовые значения в строковых форматах и разработать собственные алгоритмы, имитирующие для преобразования 2«10 с/с сложение, вычитание, умножение и деление «в столбик» строковых чисел. При этом каждая двоичная и десятичная цифра, знаки «+», «–», «,» и «е» являются символами системы Юникод. Данный подход позволил представить числа в виде строк большой длины (до 4 ГБ (для платформы Java), где каждый символ строки равен двум байтам), т. е. фактически модель PBinary в состоянии учитывать до 2•10⁹ значащих цифр входного числа.

Все операции, происходящие после начала преобразования (нажатие кнопки «Старт») можно разбить на несколько этапов:

Этап 1. Инкапсуляция входных данных. Если входное строковое число представлено в нормализованном виде, то оно приводится к простому виду, состоящему из цифр, знакового символа («+» или «–») и разделителя «,». Символ знака определяет знаковый разряд форматов, а модуль числа разбивается на две части, представляющих строковый эквивалент целой и дробной части исходного числа.

Этап 2. Получение двоичного числа и заполнение полей постбинарных форматов («упаковка» числа). Функция преобразования 10®2 с/с реализует два алгоритма, которые выполняют преобразование целой и дробной части строкового числа. На этом этапе дробная часть двоичного числа может оказаться бесконечной, аналогичной (2). В этом случае вычисление происходит до количества двоичных разрядов, необходимых для корректного заполнения мантиссы старшего формата (в данном случае pbinary256). Если происходит преобразование исходного рационального числа, которое можно представить в виде  (где q и m — целые числа), то такое число обладает конечной записью в двоичной системе счисления:

,                                                     (3)

где  и  представляют двоичные записи соответственно частного и остатка от деления q на 2^m. Если значение n + m окажется меньше разрядности мантиссы большего постбинарного формата (в данном случае pbinary256), недостающие разряды заполняются незначащими нулями.

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

Этап 3. «Распаковка» числа из форматов для получения точного значения.  Из значений полей каждого постбинарного формата формируется точное двоичное число в нормальном виде. Для этого к значению мантиссы со знаком добавляется старшая «1» (если число принадлежит к области нормализованных чисел), вычисляется значение экспоненты без смещения, определяя тем самым положение запятой, делящей поле мантиссы на целую и дробную части. Далее полученное в нормальном виде двоичное число преобразовывается в точное десятичное. Оба этих числа можно отобразить в соответствующем информационном поле (рис. 3) в нормальном и экспоненциальном виде.

Этап 4. Вычисление погрешности представления. Абсолютная погрешность представления чисел D представляет собой разность между исходным десятичным числом x и полученным точным десятичным числом y из полей форматов после преобразования: D = x – y. Значение D выводится отдельно для каждого формата и позволяет судить об эффективности использования постбинарных форматов различной точности для заданного числа.

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

Исследование временных характеристик

Для исследования временных характеристик преобразователя, выбран ряд чисел, которые подавались на вход программы. Принцип проверки времени выполнения программы был основан на замере системного времени в момент нажатия кнопки «старт», до окончания всех преобразований. Результаты исследования представлены на рис. 4, где по оси ординат указано время выполнения программы в миллисекундах, а по оси абсцисс — значение экспоненты для каждого числа. Тестирование проводилось на компьютере со следующими параметрами: CPU: Celeron M 1.6 GHz, RAM: 1024 MB, HDD: SATA 80026 MB.

Рисунок 4 – Временная диаграмма преобразователя

По результатам исследования выявлено, что при небольших значениях экспоненты, время работы зависит от количества значащих цифр самого числа, а при больших значениях экспоненты разница между исходными числами не существенна. Анализируя полученные результаты можно предположить, что при отрицательных значениях экспоненты, зависимость времени от ее величины линейная, а при положительных значениях — экспоненциальная. Это явление можно объяснить следующим: при отрицательных значениях экспоненты происходит множественное выполнение операции умножения (фактически, многократное сложение), а при положительных значениях экспоненты — множественные операции деления (фактически, многократное вычитание).

Выводы

Таким образом, модель PBinary позволяет:

– вводить исходное десятичное число в пределах 1 ¸ 10 000 (по умолчанию 1024) значащих цифр в простом или экспоненциальном виде;

– преобразовывать исходное число в посбинарные форматы pbinary 32-, 64-, 128- и 256-разрядной точности;

– вычислять разницу между исходным числом и этим же числом представленном в постбинарном формате;

– вычислять точное значение десятичного числа для чисел представленных в постбинарном формате;

– вычислять точное значение двоичного числа для чисел представленных в постбинарном формате.

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

В дальнейшем планируется усовершенствование модели по следующим направлениям:

– разработка функций ввода и преобразования дробных и интервальных чисел в соответствующие постбинарные форматы, а также их представление в тетракодах;

– увеличение быстродействия за счет использования технологий многопоточности и параллелизма;

– реализация арифметических операций над числами, заданными в постбинарных обычных, дробных и интервальных форматах с отработкой механизмов гибкой разрядности и отложенного деления [2].

Литература

[1]         Аноприенко А.Я., Гранковский В.А., Иваница С.В. Пример Румпа в контексте традиционных, интервальных и постбинарных вычислений // Научные труды Донецкого национального технического университета. Серия «Проблемы моделирования и автоматизации проектирования динамических систем» (МАП-2011). Выпуск 9 (179): Донецк: ДонНТУ, 2011. С. 324-343.

[2]         Аноприенко А.Я., Иваница С.В., Кулибаба С.В. Особенности представления постбинарных вещественных чисел в контексте интервальных вычислений и развития аппаратного обеспечения средств компьютерного моделирования // Моделирование и компьютерная графика / Материалы IV международной научно-технической конференции – 5-8 октября 2011 г. Донецк, ДонНТУ. – 2011. С. 13-19.

[3]         Бесплатные программы SoftElectro. Программа IEEE754 — конвертор чисел формата IEEE754 c абсолютной точностью представления результата. Электронный ресурс. Страница доступа: http://www.softelectro.ru/program.html.

[4]         Аноприенко А.Я. Тетралогика и тетракоды. / В кн. «Сборник трудов факультета вычислительной техники и информатики». Вып. 1. Донецк, ДонГТУ, 1996.