5 Додавання великої множини чисел

Складання великої множини чисел, що істотно відрізняються за величиною

2 Тривіальний метод підсумовування

3 Упорядковане підсумовування

4 Попарне підсумовування

5 Метод підсумовування Кохена

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

Складання – це, напевно, перша операція, яку ви навчилися виконувати щодо математики, але це, можливо, одна з останніх операцій, яку ви навчитеся надійно виконувати на компьютере.

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

Нижче припускатимемо, що числа, суму яких потрібно знайти, записані в масиві flt_arr. Довжина масиву ARR_SIZE досить велика кількість.

Тривіальний метод підсумовування

Спочатку розглянемо найпростіший спосіб обчислення суми чисел з плаваючою точкою.

float f_add(float * flt_arr)

for (i = 0; i Числа в комп'ютері надаються приблизно, що зумовлено кінцівкою розрядної сітки (див.Міжнародний стандарт подання чисел з плаваючою точкою в ЕОМ). Припустимо, що порядок мантиси не дозволяє розрізнити цифри порядку в 10 більйонів Ми хочемо скласти числа:

1.0 + 1.0e10 + −1.0e10

Виконуючи підсумовування чисел у різному порядку, ми отримуємо різний результат:

(1.0 + 1.0e10) + −1.0e10

1.0 + (1.0e10 + −1.0e10)

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

Можна порадити, складати числа з більшою точністю. Якщо, наприклад, потрібно скласти числа типу float, то результат краще представляти як типу double, аналогічно для початкового double — краще використовувати long double.

/* Extended Precision method */

float fx_add(float * flt_arr)

Ця функція досягає повної передбачуваності проходження елементів.

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

float fp_add(float * flt_arr)

float sum [ARR_SIZE / 2 + 1];

return flt_arr[0] + flt_arr[1];

else if (ARR_SIZE == 1)

for (i = j = 0; i 2)

Калькулятор

Сервіс безкоштовної оцінки вартості роботи

1. Заповніть заявку. Фахівці розрахують вартість вашої роботи
2. Розрахунок вартості прийде на пошту та по СМС

Номер вашої заявки

Зараз на пошту прийде автоматичний лист-підтвердження з інформацією про заявку.

---