5.1. Арифметика наближених обчислень
5.3. Програмування числових типів даних
5.5. Програмування символьного типу
5.7. Програмування типів, що визначаються
5. ПРОСТІ ТИПИ ДАНИХ
При вивченні
арифметичного виконавця ми зіткнулися
з необхідністю розрізняти множини
допустимих значень числових змінних, зокрема, цілих і дійсних. Відмінність
множин допустимих значень природно спричиняє
відмінність операцій і функцій на них, що призвело
до появи поняття типу даних.
Типи
даних в інформатиці діляться на прості і складені типи.
У цій частині курсу вивчимо прості типи даних, які
можна поділити на дві групи:
стандартні, вбудовані у виконавець, і ті, що програмно визначаються. До
стандартних звичайно відносять натуральний, цілий, дійсний, бульовий і символьний (літерний) типи.
Прості
типи, що програмно визначаються, будуються
за допомогою деяких фіксованих механізмів: переліку
елементів множини значень та виділення підмножини - діапазону - шляхом вказання
його максимального і мінімального елементів.
Бульовий тип
даних ми розглянули раніше у другій частині
курсу. Тепер розглянемо інші прості
типи даних.
Надалі розглянемо методи визначення складених типів
даних, а також методи визначення нових
функцій на множинах значень як стандартних, так і типів, що визначаються
програмно - простих або складених.
5.1. Арифметика наближених обчислень
Вивчаючи
арифметичний виконавець, ми досі не вникали в деталі, пов'язані з
представленням чисел. Неявно малося на увазі, що мова йде про множину всіх
чисел - натуральних, цілих, дійсних. Однак це не так. У інформатиці звичайно
використовуються обмежені, а точніше, скінченні числові множини. Так,
наприклад, замість множини дійсних
чисел вивчається лише деяка її підмножина - так звана множина наближень. Звичайно множина
наближень скінченна, тому навіть раціональні числа представлені в ньому наближено з деякою вибраною точністю.
Аргументом практичного характеру на
користь наближених обчислень є зниження трудомісткості арифметичних
операцій над раціональними числами - зрозуміло, що виконати множення семизначних наближень простіше, ніж,
скажемо, множення стозначних чисел.
Правда, перехід до наближень спотворює результат, що отримується: виникає так звана похибка обчислень. Іншим аргументом на користь наближених обчислень є
ірраціональність, для роботи з якою у нас фактично немає інших засобів.
Займемося
вивченням арифметики наближених обчислень.
Основне питання полягає у вивченні способів округлення, аналізі похибок округлення
і наближених арифметичних операцій.
Арифметика
наближених обчислень, що розглядається нами, залежить від основи b
системи числення, що використовується для запису чисел, точність представлення
яких вимірюється числом b-ічних значущих цифр. Наприклад, наближене
представлення числа p з точністю до 8 десяткових
цифр p10 = 3.141592710, а з точністю до
8 вісімкових цифр - p8 = 3.11037558.
Зауваження
5.1. Записуючи числа в десятковій системі числення, індекс 10, що вказує на основу системи числення, ми будемо
звичайно опускати (наприклад, 63.48 замість 63.4810 ). Дробову частину від цілої ми відділяємо
точкою, яка називається позиційною, замість прийнятої у нас коми. Це - данина традиції англомовних країн, звідки прийшли поширені мови програмування.¦
Позиційний
запис числа в будь-якій системі числення можна представити в розгорнутому вигляді,
наприклад, розглянуте вище наближення числа p за основою 10 як
0 -1
-2 -3 -4
-5 -6 -7
3.141592710=
3*10 +1*10 +4*10 +1*10
+5*10 +9*10 +2*10
+7*10
або за основою
8 як
0 -1
-2 -3 -4
-5 -6 -7
3.11037558 = 3*8 +1*8
+1*8 +0*8 +3*8
+7*8 +5*8 +5*8.
Визначимо
поняття позиційного запису числа в системі числення за довільною натуральною
основою b>1.
Позиційним
записом числа а за основою b назвемо
запис наступного вигляду
(... a а а а .a а
а ...) =
3 2 1 0 -1 -2 -3
b
3 2 -1 -2
-3
=...+а *b + а *b + а *b + а + а
*b + а *b +
а *b
+...,
3
2 1 0
-1 -2 -3
де коефіцієнти
аk можуть приймати
одне з
b значень 0,1,..., b-1.¦
Ось приклад позиційного запису за основою 8
(462.7)8 = 4*64 + 6*8 + 2 +
7*(1/8) = (306.875)10.
Для
переведення чисел з однієї позиційної системи числення до іншої
дуже зручними є функції div і mod, що вже застосовувалися нами раніше при обчисленні
суми цифр натурального числа, відповідно, частки і залишку від ділення натуральних чисел.
Визначимо через Trans(a, b1, b2) - функцію, що переводить число а з
позиційної системи числення за основою b1 в систему за основою b2.
Перейдемо
тепер до вивчення методів округлення дійсних чисел.
Функцією
округлення числа х до р (р
> 1) b-ічних значущих цифр назвемо
функцію round(х, р, b), задану співвідношеннями
round(0, р, b) = 0;
r-p p-r
round(х,
р, b) = sign(х)*b *[b *¦х¦
+ 1/2],
r-1
r
де b <=¦х¦<
b. Тут під записом 1/2
мається на увазі вираз Trans(0.5,10,
b).¦
Наприклад, нехай х=(11.011) = (3.375), b=2
і р=3. Із рівності
2 10
1 2
(2 ) = (10)
і (2 ) = (100), слідує, що r=2. Тоді отримаємо
10
2 10 2
2-3 3-2
round(х,3,2)
= sign(х)*2 *[2
*¦11.011¦+ 1/2] =
-1 -1
= 2 *[2*11.011+0.1] = 2 *[110.11+0.1] =
-1 -1
= 2 *[111.01] = 2
*(111) = (11.1) = (3.5).
2 2 10
Якщо
ж округлити число (3.375)10 до трьох цифр, то знайдемо, що
-2
2 -2
round(х,
3,10) = 10 *[10 *3.375+1/2] = 10 *[337.5+0.5] =
-2
= 10 *(338)
= (3.38).
10 10
Число (3.38)10 в двійковій системі числення дорівнює
(11.0110001)2.
Відмітимо деякі властивості функції округлення.
Властивість 5.1.
round(1, р, b) = 1.
Доведення. Маємо
1-р р-1
1-p р-1
round(1, р,
b) = b *[b + 1/2] = b
*b = 1,
р-1 р-1
р-1
оскільки при р>
1 b
> 1 і [b + 1/2] = b. ¦
Властивість 5.2.
round(- х, р, b) = - round(х, р,
b).
Доведення випливає з sign(- х)
= - sign(х).¦
Властивість 5.3.
round(b*х, р, b) = b*round(х, р, b).
r-1 r
Доведення. Нехай b <¦х¦<
b , тоді для b*х маємо
r
r+1
b <¦b*х¦< b , звідки
r+1-p p-r-1
round(b*х, р, b) = sign(b*х)*b *[b *¦b*х¦ + 1/2] =
r-p p-r
-1
= b*sign(х)*b
*[b *b *b*¦х¦ + 1/2] =
= b*round(х, р,
b).¦
Оцінимо міру точності арифметики
наближених обчислень.
Візьмемо число х>0
r-1 r-2 r-p r-p-1
х
= а *b + а *b +...+ а *b
+ а *b +...,
1 2 р р+1
тоді
r-1 r-2 r-p
round(х,
р, b) = а *b +
а *b +...+ c *b ,
1 2 р
де
_ r-p
¦ а, 0 <= z
< 1/2*b ,
¦
р р
c = < r-p r-p
р ¦ а
+1, 1/2*b <= z < b
,
¦_
р р
r-p-1 r-p-2
z
= а *b + а
*b +...
р р+1 р+2
Далі
r-p
r-p
¦x-round(х, р, b)¦ = ¦ а *b - c *b + z ¦ =
р р
р
_ _
¦
¦z ¦, c =
а ¦
¦
р р р ¦ r-p
= < r-p > <= 1/2*b .
¦
¦z - b ¦, c = а +1 ¦
¦_
р р р _¦
Величина Е=¦x-round(х, р,
b)¦ називається абсолютною похибкою округлення. Отримана нерівність дає її оцінку
r-p
Е <= 1/2 * b .¦
Величина
абсолютної похибки залежить, взагалі кажучи,
від порядку числа x. Для того, щоб
виключити залежність похибки від
порядку величини, що округляється розглядають
відносну похибку.
Виберемо
d так, щоб
1-р
round(х,
р, b)-х = d*х*b ,
тоді
1- р r-p
¦d¦*¦х¦*b
< 1/2*b.
r-1 r
Оскільки
b <¦х¦< b , то
r-p-1+р
r-1 r-1
¦d¦ <= 1/2*b /¦х¦
<= 1/2*b /b = 1/2.
1- р
Величина dp (х)
= d*b називається відносною похибкою округлення.
Отже, ми довели
Твердження 5.1. Відносна похибка округлення, задана співвідношенням round(х, р, b) = х*(1+dp(х)), задовольняє оцінці
1-р
¦dp(х)¦
< 1/2 * b .¦
Визначимо тепер наближені р-розрядні
арифметичні операції над дійсними
числами, вважаючи
u +
v = round(u+v, р, b); u - v
= round(u-v, р, b);
р р
u *
v = round(u*v, р, b); u / v
= round(u/v, р, b).
р р
На
жаль, наближені р-розрядні арифметичні
операції не задовольняють деяким законам звичайної
(точної) арифметики. Спочатку відмітимо
співвідношення, які залишаються справедливими
Твердження
5.2. Справедливі тотожності
a) u +
v = v + u, u * v = v *
u;
р р р р
b) u -
v = u + -v;
р р
c) -(u +
v) = - u + -v, -(u *
v) = (- u) * v;
р р р р
d) u +
v = 0 <=> u = -v;
р
e) u * v = 0 <=> u=0 V v=0;
р
f) (- u) / v = u / (- v) = -(u /
v);
р р р
h) u /
u = 1,
р
де символ
<=> означає рядок "тоді і тільки тоді, коли".
Доведення тотожності
виходять безпосередньо з означень р-розрядних
арифметичних операцій, функції округлення
та її властивостей.¦
Наслідок 5.1. Відносні похибки
наближених арифметичних операцій
u +
v = (u+v)*(1+dp(u+v)); u
- v = (u-v)*(1+dp(u-v));
р р
u *
v = (u*v)*(1+dp(u*v)); u
/ v = (u/v)*(1+dp(u/v)),
р р
1-р
за абсолютною
величиною не перевершують 1/2*b .¦
Зауваження 5.2. Асоціативний і
дистрибутивний закони, взагалі кажучи, місця не мають. Дійсно
(11111113. +8 -11111111.) +8
7.5111111 =
= 2.0000000 +8 7.5111111 =
9.5111111;
11111113. +8 (-11111111. +8
7.5111111) =
= 11111113. +8 -11111103. =
10.000000.
Аналогічно,
(20000.000 *8 -6.0000000) +8
(20000.000 *8 6.0000003) =
= -120000.00 +8 120000.01 =
0.01000000;
20000.000 *8 (-6.0000000 +8
6.0000003) =
= 20000.000 *8 0.00000030 =
0.00600000.¦
Оцінимо міру відхилення в законі асоціативності
множення. Двократним застосуванням наслідку 5.1 отримуємо
(u *
v) * w = ((u*v)*(1+d )) * w = u*v*w*(1+d )*(1+d );
р р 1
р 1 2
u *
(v * w) = u * ((v*w)*(1+d )) =
u*v*w*(1+d )*(1+d ),
р р р 3 3 4
причому
1-р
¦d ¦ < 1/2*b , k=1,2,3,4.
k
Тоді
(u * v) *
w (1+d )*(1+d )
р р 1
2
------------- = ------------- = 1+d,
u *
(v * w) (1+d )*(1+d )
р р 3
4
де
(1+d )*(1+d ) - (1+d )*(1+d )
1 2
3 4
d = ----------------------------- <
(1+d )*(1+d )
3 4
1-р 2 1-p 2 1-p
(1+1/2*b ) -
(1-1/2*b ) 2*b
< ----------------------------- =
-------------.
1-р 2 1-p 2
(1-1/2*b )
(1-1/2*b )
Отже, ми
довели
Твердження 5.3. Відносна похибка d
асоціативного закону наближеного
множення
(u *
v) * w = u * (v * w)*(1+d)
р р р р
задовольняє
оцінці
1-р
2*b
¦d¦ < -------------. ¦
1-р 2
(1-1/2*b )
Похибки додавання виявляються більш
відчутними.
Приклад
5.1. Розв’язати квадратне рівняння х2-400*х+1=0, використовуючи шести- та тризначні наближені арифметичні операції.
Розв’язок. Знайдемо спочатку більш точний розв’язок
___________________
________
х = 200.000 +
Ö 40000.0 -
1.00000 = 200.000 + Ö 39999.0
=
1 6 6 6
= 200.000 + 199.997 = 399.997;
6
х = 200.000 -
199.997 = 0.00300.
2 6
Тепер
скористаємося тризначною арифметикою
________________ ________
é 2 é 2
x' = 200. + Ö 400.*10
- 1.00 = 200. + Ö 400.*10
=
1 3 3 3
= 200. + 200. = 400.;
3
x' = 200. - 200. = 0.
2 3
Обчислимо
відносні похибки двох наближень
¦ x' - х ¦
¦
1 1 ¦ 0.003 -6 -5
¦d ¦ = ----------- = -------- = 7.5 *
10 < 10;
1
¦ х ¦
399.997
¦ 1 ¦
¦ x' - х ¦
¦
2 2 ¦ 0.003
¦d ¦ = ----------- = ------- = 1.
2
¦ х ¦
0.003
¦ 2 ¦
У одній і тій же задачі ми отримали перший корінь рівняння досить точно: похибка набагато менше
відносної похибки округлення (d = 1/2 *10-2); у другому корені при використанні тризначної
арифметики не отримано жодної вірної
цифри.
Цікаво,
що користуючись тією ж тризначною
арифметикою, за теоремою Вієта другий корінь знаходиться
значно точніше
x'' = 1 / x' = 0.0025 = 0.003,
2 1
¦ x'' - х ¦
¦
2 2 ¦ 0.003 - 0.0025
¦d ¦ = ------------ = -------------- = 0.17.
2
¦ х ¦
0.003
¦ 2 ¦
Приклад 5.2. Дослідити асоціативність
наближеного тризначного додавання на прикладі обчислення
суми
S = 100 + 0.499 +. .. + 0.499.
¦___________________¦
100 раз
Розв’язок. Точне значення S = 100+100*0.499 = 149.9.
Згрупуємо всі дужки ліворуч
S
= (...((100. + 0.499) + 0.499) +
...) + 0.499 = 100.
1 3 3
3 3
Інше угрупування дужок дає
S
= 100. + ((0.499 + 0.499) + (0.499 + 0.499) + ...) =
2 3 3 3
3 3
= 100. + (0.998 + 0.998 + ...) =
3 3
3
= 100. + ( 2.00 +
... ) = 100. + 50.0 = 150.
3 3 3
Приклад
показує, що тільки за рахунок зміни
порядку додавання відносну похибку обчислень можна зменшити з
49.9
¦d ¦ = ------- = 0.33
1
149.9
до
0.1 -3
¦d ¦ = ------- = 0.66 * 10 ,
2
149.9
тобто
приблизно в 500 раз.