АДАПТИВНЕ КОНТРОЛЬНЕ ТЕСТУВАННЯ ЧИСЛОВОЇ АРИФМЕТИКИ: МЕТОД І ФОРМАЛІЗАЦІЯ - Scientific conference
Main page
UA PL EN

Congratulation from Internet Conference!

Hello

Рік заснування видання - 2011

АДАПТИВНЕ КОНТРОЛЬНЕ ТЕСТУВАННЯ ЧИСЛОВОЇ АРИФМЕТИКИ: МЕТОД І ФОРМАЛІЗАЦІЯ

12.06.2025 18:07

[1. Information systems and technologies]

Author: Дейнеко Денис Павлович, аспірант кафедри програмного забезпечення компʼютерних систем, Чернівецький національний університет, м. Чернівці, Україна


У цій роботі пропонується новий підхід до оцінки точності числових обчислень, який поєднує в собі ідеї з галузей чисельної оптимізації, тестування алгоритмів та адаптивного інтегрування. Запропонований алгоритм отримав назву Adaptive Benchmark Testing (ABT). Його мета — ідентифікація критичних ділянок числової області, де стандартна арифметика демонструє найбільші відхилення, і наступна концентрація тестування саме в цих зонах.

Методика роботи алгоритму включає кілька послідовних етапів. Спочатку генерується базовий тестовий набір значень, який рівномірно покриває заданий числовий інтервал [1]. Для кожного значення обчислюються результати двома арифметичними системами — альтернативною арифметикою та стандартною реалізацією CPython. Далі визначається абсолютна і відносна похибка кожного результату:

AbsError(x)=|f1 (x)-f2 (x)|,

RelError(x)=|f1 (x)-f2 (x)|/|f2 (x)| 

де f1 (x) — результат альтернативної арифметики, f2 (x) — результат CPython.

На основі цих похибок формується функція точності E(x), яка є максимумом між абсолютною та відносною похибками. Потім виконується статистичний аналіз: обчислюється середнє значення похибки та її стандартне відхилення. Порогове значення τ, що визначає критичні області, встановлюється за формулою:

τ=μ+λσ,

де μ — середнє значення похибки, σ — її стандартне відхилення, λ — параметр чутливості, що регулює ступінь деталізації виявлення проблемних точок.

Наступні ітерації алгоритму спрямовані на збагачення тестового набору саме в тих піддіапазонах, де похибка перевищує поріг. Таким чином, замість сліпого тестування випадкових значень, ABT динамічно фокусується на тих зонах, які вимагають детальнішої перевірки [2]. Ітерації повторюються доти, доки зміна середньої похибки між ітераціями не стане меншою за ε.

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

Оцінка складності алгоритму показує, що кожна ітерація має лінійну складність O(n), де n — кількість тестових точок. У випадках, коли приріст точності зменшується, число ітерацій автоматично обмежується, що робить підхід обчислювально ефективним [4].

ABT має потенціал для широкого застосування в системах, де критично важлива арифметична точність: компілятори, інтерпретатори мов програмування, числові бібліотеки, а також системи комп'ютерної алгебри. Його також можна адаптувати для тестування стабільності числових алгоритмів або для верифікації точності розв’язання диференціальних рівнянь.

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

Література:

1. Metropolis N., Ulam S. The Monte Carlo Method. Journal of the American Statistical Association. 1949. Vol. 44, no. 247. P. 335–341. URL: https://doi.org/10.1080/01621459.1949.10483310 (date of access: 08.06.2025).

2. Numerical methods for least squares problems. Choice Reviews Online. 1996. Vol. 34, no. 03. P. 34–1602–34–1602. URL: https://doi.org/10.5860/choice.34-1602 (date of access: 08.06.2025).

3. Higham N. J. Accuracy and stability of numerical algorithms. 2nd ed. Philadelphia, PA : Society for Industrial & Applied Math, 2003. 680 p.

4.Time bounds for selection / M. Blum et al. Journal of Computer and System Sciences. 1973. Vol. 7, no. 4. P. 448–461. URL: https://doi.org/10.1016/s0022-0000(73)80033-9 (date of access: 08.06.2025).

________________________________________________________

Науковий керівник: Воробець Георгій Іванович, кандидат фізико-математичних наук, доцент, Чернівецький національний університет, м. Чернівці, Україна

Creative Commons Attribution Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License
допомога Знайшли помилку? Виділіть помилковий текст мишкою і натисніть Ctrl + Enter

Another articles in this section

Сonferences

Conference 2025

Conference 2024

Conference 2023

Conference 2022

Conference 2021



Міжнародна інтернет-конференція з економіки, інформаційних систем і технологій, психології та педагогіки

Наукова спільнота - інтернет конференції

:: LEX-LINE :: Юридична лінія

Інформаційне суспільство: технологічні, економічні та технічні аспекти становлення