Введение

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

На сегодняшний день в математике существует множество методов решения задач в различных областях человеческой деятельности. Но, в отличии от теоретических изысканий, непосредственное применение этих методов в реальности затруднительно, ибо на практике можно использовать только числа, имеющие конечное представление, т.е. представленные в виде конечной цепочки цифр, в то время, как большинство этих методов работают с произвольными вещественными числами. Естественно, подавляющее большинство вещественных чисел невозможно выразить конечным представлением (и это легко доказать, ибо для любого конечного представления мы будем иметь возможность представить всего N = a^z чисел, где a – основание с.с. представления, а z – число разрядов представления, а как известно, мощность множества вещественных чисел равна ∞ и естественно, что N < ∞). А т.к. данное ограничение касается как входных, так и выходных и промежуточных данных, то в области реальных вычислений встает задача как повышения точности расчетов, так и разработки устойчивых методов расчета (т.е. таких методов, в которых теоретически оценено или (что то же) контролируется влияние точности промежуточных вычислений на результат).

Задача выполнения вычислений с высокой точностью возникает в инженерных и научных расчетах в различных областях [1]: моделирование в физике, химии, астрономии и т.д. На практике наиболее часто возникающей проблемой является выбор между диапазоном представления величин и точностью вычислений (т.е. потерей точности и накоплением ошибок при выполнении вычислительных операций).

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

1. точечный или аппроксимационный подход – использовать вместо вещественных чисел их приближение рациональными, т.е. имеющими представление в виде конечной цепочки цифр. Общепринятым стандартом для представления чисел в формате с плавающей точкой и выполнения операций над ними является стандарт IEEE-754 [2];
2. интервальный подход – представление вещественных чисел в виде конечно-представимого множества чисел, содержащих в себе искомое число, в форме достоверного интервала–пары рациональных чисел [A, B] (достоверный в данном случае означает, что истинный абстрактный результат гарантированно находится в интервале, локализуемом указанными границами).

Актуальность темы

За последние два-три десятка лет в литературе неоднократно поднималась проблема достоверности компьютерных вычислений [3-6]. Несмотря на существование стандарта, есть исследования [7-9], которые показывают, что использование современных подходов к представлению в компьютере действительных чисел приводит к:

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

Для понимания серьезности этих проблем рассмотрим следующий пример – будем выполнять операцию сложения 0.3 и 0.2. Известно, что 0.3 + 0.2 = 0.5. Однако программа на рисунке 1 (анимация) ставит данный факт под сомнение. Код этой сомневающейся программы приведен на рисунке 2.

(Анимация [56 Кб] продолжительностью 8.56 сек с частотой 25 кадров в секунду имеет 214 кадров и повторяется 2 раза)

Особенно серьезными данные проблемы становятся тогда, когда вычисления – это составляющая процесса моделирования сложных, дорогостоящих и опасных объектов – энергетика, космос, технологические процессы и т.д. В этом случае недостоверность результата вычислений может приводить к аварийным ситуациям, техногенным катастрофам и т.п. Как упоминается в [10], «математическая модель будет адекватной и работоспособной лишь в том случае, если погрешности вычислений контролируются». Например, теоретически (A + B – 0.5) * 10¹⁰ = 0, а в нашем случае – 149.01161. Встает закономерный вопрос – а какая теперь разница между 0 и 149?

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

Цель и решаемые задачи

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

Соответствующими задачами в рамках достижения данной цели будут:

1. Анализ математической корректности существующих форматов работы с рациональными числами и форматов их представления (включая IEEE-754);
2. Разработка методов для повышения точности выполнения вычисляющих операций и соответствующих им структур данных;
3. Теоретическое и экспериментальное исследование разработанных методов и форматов;
4. Практическая реализация новых методов и форматов в виде исполнимой библиотеки.

Предполагаемая научная новизна

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

Планируемые практические результаты

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

Обзор исследований и разработок по теме

В области расчетов и работы с нецелыми числами сложилась странная ситуация – большинство разработчиков оборудования и ПО без особого сопротивления приняли стандарт IEEE-754 [2], вышедший еще в 1985 (последняя версия стандарта – от 2008 года), однако нигде в самом стандарте не приведено теоретико-математическое обоснование выбранных для представления рациональных чисел фундаментальных значений. Также имеется стандарт P754 [12], описывающий более корректную реализацию стандарта IEEE–754 в железе и ПО, однако и здесь мы видим отсутствие какого-либо теоретико-математического основания предложенных рациональных чисел. В области интервальных вычислений можно наблюдать большее количество исследований (оценивание по количеству публикаций на эту тему). Основополагающим документом данного направления стала написанная в 1966 году монография Р. Мура [4].

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

Также, из зарубежных публикаций можно отметить [1] и [6], а среди описаний программных реализаций по теме – [8] и [9]. На постсоветском пространстве можно выделить: по интервальным вычислениям – [7], а по точечным – критикующие их (в частности IEEE-754) статьи В.М. Юровицкого [13, 14].

В рамках ДонНТУ исследования как по данной теме в частности, так и в области теории рациональных чисел в общем не проводились.

Общее введение в теорию рациональных чисел

Итак, как было сказано ранее, рациональное число есть действительное число в виде конечной цепочки цифр. В системе счисления с основанием a такое число A в самом общем виде можно представить, как

где z_i ∈ [0; a-1] – значение i разряда (цифра) числа A в с.с. с основанием a,
N = n+m+1 – количество разрядов, отведенное под рациональное число A в с.с. a.

Форма записи (1), в которой основание с.с. a опускается, значения разрядов z_i записываются справа налево, а позиция десятичной точки запоминается (сама точка может ставиться или не ставиться), называется представлением числа A в формате с фиксированной точкой:

В данном случае позиция десятичной точки – между m и m-1 разрядом справа (отсчет с 0) либо между n и n+1 разрядом слева (отсчет также с 0).

Однако, формат фиксированной точки неудобен для представления чисел различного порядка, однако с примерно одинаковым количеством разрядов или, другими словами, его основной недостаток – малый диапазон представляемых чисел для заданного N [15]. Для улучшения ситуации вводится коэффициент масштаба, на которое умножается число, чтобы получить его истинное значение. В этом случае степень при этом коэффициенте укажет, на сколько разрядов необходимо сдвинуть точку в фиксированном представлении числа для получения его реального значения (направление сдвига имеет общематематическую зависимость от знака порядка, см. ниже, начальная позиция точки определяется конкретным форматом числа). Числа такого вида (базовое представление числа в форме с фиксированной точкой и коэффициентом масштаба) называются числами с плавающей точкой и представляются в с.с. a в виде

где M – мантисса, запись значения числа в форме с фиксированной точкой,
a^p – коэффициент масштаба,
p – порядок числа.

Стоит также отметить, что в данной форме записи знак числа выделен отдельно, поэтому мантисса представляется беззнаковым числом с фиксированной точкой, порядок же может иметь знак. Конкретная форма записи мантиссы (в основном начальное положение точки) и порядка (кодирование знака) определяется конкретным форматом представления чисел с плавающей точкой.

Заключение

На текущий момент обоснована актуальность темы, поставлена цель и сформулированы задачи, а также практически закончен анализ выбранной предметной области. Также был начат некий теоретический анализ предметной области (в частности, корректности формата IEEE-754), и на основании этого анализа была написана статья по теме теории рациональних чисел, подготовленная к публикации в сборник научных трудов ДонНТУ–2010.

Список литературы

1. У. Кулиш, Д. Рац, Р. Хаммер, М. Хокс. Достоверные вычисления. Базовые численные методы. Изд-во: «Регулярная и хаотическая динамика», - 1995. – 496 с.
2. IEEE Standard for Floating-Point Arithmetic (Revision of IEEE Std 754-1985) // IEEE Computer Society. – 2008. – 70 p.
3. Wilkinson J. H. Modern error analysis // SIAM Rev. — 1971. — Vol. 13, № 4. — P. 548–568.
4. Moore R. E. Interval analysis. — Englewood Cliffs; Prentice Hall, 1966. — 145 p.
5. Moore R. E. Methods and applications of interval analysis. — Philadelphia; SIAM, 1979. — xi, 190 p.
6. Alefeld G., Herzberger J. Introduction to interval computations. — New York etc.; Academic Press, 1983. — XVIII, 333 p.; Рус. перев.; Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления: Пер. с англ. — М.: Мир, 1987. — 356 с.
7. Добронец Б. С., Шайдуров В. В. Двусторонние численные методы. — Новосибирск; Наука, 1990. — 208 с.
8. Yohe J. M. Portable software for interval arithmetic // Fundamentals of numerical computation (computer-oriented numerical analysis) / Ed.: G. Alefeld, R. D. Grigorieff. — Wien etc.: Springer-Verlag, 1980. — (Computing; Suppl. 2). — P. 211–229.
9. Klatte R., Kulisch U., Wiethoff A., Lawo C., Rauch M. C-XSC. A C++ class library for extended scientific computing. — Berlin etc.: Springer Verlag, 1993. — 270 p.
10. Nickel K. Can we trust the results of our computing? // Mathematics for Computer Science; Proc. Symposium held in Paris, March 16–18, 1982. — S. l.; Association francaise pour la cybernetique et technique (AFCET), 1982. — P. 167–175
11. Верещагин Н.К., Шень А. Математическая логика и теория алгоритмов: Часть 1. Начала теории множеств. – М.: Изд-во МЦНМО, - 2008. – 128 с.
12. DRAFT Standard for Floating-Point Arithmetic P754 // IEEE Computer Society. – 2006. – 64 p.
13. Юровицкий В.М. IEEE754-тика угрожает человечеству [электронный ресурс]: http://www.yur.ru/science/computer/IEEE754.htm
14. Юровицкий В.М. Компьютерные числа − угроза человечеству // Млечный Путь. Сверхновый литературный журнал [электронный ресурс]: http://milkywaycenter.com
15. Edmond / HI-TECH. FPU посвящается (часть 1) [электронный ресурс]: wasm.ru/print.php?article=edfpu01