Skip to main content.

Вступ

Число. Найбільш важливий абстрактний об'єкт, вигаданий людством за всю історію його існування, тому що воно є базовим елементарним об'єктом математики, а вона, надаючи методи практичного рішення сучасних прикладних задач, є, таким чином, царицею наук технологічної цивілізації.

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

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

Отже, підсумовуючи вищеозначене, можна казати про існування на сьогоднішній день проблеми співвіднесення обчисленого наближеного результату із дійсним абстрактним рішенням поставленої задачі. Існує два основних підходи до рішення даної проблеми:

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

Актуальність теми

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

Для розуміння серйозності цих проблем розглянемо наступний приклад - будемо виконувати операцію додавання 0.2 до 0.3. Відомо, що 0.3 + 0.2 = 0.5. Однак програма на малюнку 1 (анімація) ставить даний факт під сумнів. Код цієї програми наведений на малюнку 2.

Демонстрація актуальності

Малюнок 1 – Демонстрація актуальності теми даної роботи

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

Код демонстраційної програми

Малюнок 2 – Код демонстраційної програми

Особливо серйозними дані проблеми стають тоді, коли обчислення – це складова процесу моделювання складних, дорогих і небезпечних об'єктів – енергетика, космос, технологічні процеси та ін. У цьому випадку невірогідність результату обчислень може привести до аварійних ситуацій, техногенних катастроф і т.ін. Як говориться в [10], «математична модель буде адекватною та працездатною лише в тому випадку, якщо похибка обчислень контролюється». Наприклад, теоретично (A + B – 0.5) * 1010 = 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].

У рамках ДонНТУ дослідження як з даної теми зокрема, так і в області теорії раціональних чисел взагалі не проводилися.

Висновок

На сучасний момент обґрунтована актуальність теми, поставлена мета та сформульовані задачі, а також практично закінчений аналіз обраної предметної області. Також був початий деякий теоретичний аналіз предметної області (зокрема, коректності формату 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