狠狠撸

计算机理论入门5

2012年度後期
垂水共之
tarumi@ems.okayama-u.ac.jp
計算誤差

計算誤差
? 計算機固有の誤差について

– 丸め誤差

– 桁落ち

? 2次方程式の解放

? 分散（統計）の計算

１からｎまでの和
? １＋２＋３＋???＋（ｎ－１）＋ｎ

? ｎ＋（ｎ－１）＋???＋３＋２＋１

1 1 1 1 1
?
1 2 3 n 1 n

1 1 1 1 1
?
n n 1 n 2 2 1

Cプログラム
#include <stdio.h>
void main() {
int n,i;
float sum1, sum2;
printf("nNumber of terms = ? ");
scanf("%d", &n);
for( i=1; i<=n; ++i)
sum1 += 1./i;
for( i=n; i>=1; --i)
sum2 += 1./i;
printf("nsum1=%10.6ensum2=%10.6endiff=%10.6en",
sum1, sum2, sum1-sum2);
}

結果
Number of terms = ? 10
sum1=2.928968e+00
sum2=2.928968e+00
diff=0.000000e+00

Number of terms = ?
sum1=5.187378e+00
sum2=5.187377e+00
diff=9.536743e-07

sum1=7.485478e+00
sum2=7.485472e+00
diff=6.675720e-06

sum1=9.787613e+00
sum2=9.787604e+00
diff=8.583069e-06

0.1の和（足し算）
? 0.1 を100 回なり10000 回なり加えてみよう！
#include <stdio.h> 10 1.000000e+01
1000 9.999029e+02
void main() { 20 2.000004e+01
int n,i; 2000 1.999659e+03
30 3.000008e+01
float sum; 3000 3.000576e+03
n=0; 40 3.999996e+01
4000 4.001553e+03
sum=0; 50 4.999981e+01
while(n>=0) { 5000 5.002529e+03
60 5.999966e+01
for( i=1; i<=100; ++i) sum += 0.1; 6000 6.003506e+03
70 6.999950e+01
n += 10; 7000 7.004482e+03
printf("%10d %10.6en", n, sum); 80 7.999935e+01
8000 8.005459e+03
} 90 8.999920e+01
} 9000 9.002463e+03
100 9.999905e+01
10000 9.998557e+03
200 2.000030e+02
20000 1.995949e+04
300 3.000091e+02
30000 2.992043e+04
400 4.000152e+02
40000 4.002085e+04
500 5.000213e+02
50000 5.017710e+04
600 6.000005e+02
60000 6.033335e+04
700 6.999761e+02
70000 7.048959e+04
800 7.999517e+02
80000 8.064584e+04
900 8.999273e+02

どうして？
? 固定小数点表現
– 整数計算では誤差なし

? 浮動小数点表現
– 有限桁で切り捨て

– 話を簡単に
? 有効桁数 10進数で3ケタの場合

有効桁数３桁の例

i 1/i 1/i(3 桁) 和 i 1/i 1/i(3 桁) 和
---------------------- ----------------------
1 1.0000 1.00 1.00 10 0.1 .100 .100
2 0.5000 .500 1.50 9 0.1111 .111 .211
3 0.3333 .333 1.83 8 0.125 .125 .336
4 0.25 .250 2.08 7 0.1428 .142 .478
5 0.2 .200 2.28 6 0.1666 .166 .644
6 0.1666 .166 2.44 5 0.2 .200 .844
7 0.1428 .142 2.58 4 0.25 .250 1.09
8 0.125 .125 2.70 3 0.3333 .333 1.42
9 0.1111 .111 2.81 2 0.5000 .500 1.92
10 0.1 .100 2.91 1 1.0000 1.00 2.92

? 小さな値から加える方が切り捨てられる値が少な
い

123+0.125=？

123 123
+) 0.125 +) 0.125
123.125 123.125
有効桁数
３桁

? 簡単のために10進数で説明したが、実際は2進数
? ３２ｂｉｔｓでは仮数部24bits、10進数で6ケタ程
度
? 64bits倍精度、128bits4倍精度もあるが、有限桁で
あることは同じ。

精度 accuracy(正確度), precision(精密度)
? 0.1(10)の精度はどの程度？
1 0.0 31 0.0999999996 2747097015 3808593750 0
2 0.00 32 0.0999999998 6030161380 7678222656 25
3 0.000 33 0.0999999999 7671693563 4613037109 375
4 0.0625 34 0.0999999999 7671693563 4613037109 3750
5 0.09375 35 0.0999999999 7671693563 4613037109 37500
6 0.093750 36 0.0999999999 9126885086 2979888916 015625
7 0.0937500 37 0.0999999999 9854480847 7163314819 3359375
8 0.09765625 38 0.0999999999 9854480847 7163314819 33593750
9 0.099609375 39 0.0999999999 9854480847 7163314819 335937500
10 0.0996093750 40 0.0999999999 9945430317 8936243057 2509765625
11 0.0996093750 0 41 0.0999999999 9990905052 9822707176 2084960937 5
12 0.0998535156 25 42 0.0999999999 9990905052 9822707176 2084960937 50
13 0.0999755859 375 43 0.0999999999 9990905052 9822707176 2084960937 500
14 0.0999755859 3750 44 0.0999999999 9996589394 8683515191 0781860351 5625
15 0.0999755859 37500 45 0.0999999999 9999431565 8113919198 5130310058 59375
16 0.0999908447 265625 46 0.0999999999 9999431565 8113919198 5130310058 593750
17 0.0999984741 2109375 47 0.0999999999 9999431565 8113919198 5130310058 5937500
18 0.0999984741 21093750 48 0.0999999999 9999786837 1792719699 4423866271 97265625
19 0.0999984741 210937500 49 0.0999999999 9999964472 8632119949 9070644378 662109375
20 0.0999994277 9541015625 50 0.0999999999 9999964472 8632119949 9070644378 6621093750
21 0.0999999046 3256835937 5 51 0.0999999999 9999964472 8632119949 9070644378 6621093750 0
22 0.0999999046 3256835937 50 52 0.0999999999 9999986677 3237044981 2151491641 9982910156 25
23 0.0999999046 3256835937 500 53 0.0999999999 9999997779 5539507496 8691915273 6663818359 375
24 0.0999999642 3721313476 5625 54 0.0999999999 9999997779 5539507496 8691915273 6663818359 3750
25 0.0999999940 3953552246 09375 55 0.0999999999 9999997779 5539507496 8691915273 6663818359 37500
26 0.0999999940 3953552246 093750 56 0.0999999999 9999999167 3327315311 3259468227 6248931884 765625
27 0.0999999940 3953552246 0937500 57 0.0999999999 9999999861 2221219218 5543244704 6041488647 4609375
28 0.0999999977 6482582092 28515625 58 0.0999999999 9999999861 2221219218 5543244704 6041488647 46093750
29 0.0999999996 2747097015 380859375 59 0.0999999999 9999999861 2221219218 5543244704 6041488647 460937500
30 0.0999999996 2747097015 3808593750 60 0.0999999999 9999999947 9582957206 9578716764 2265558242 7978515625

桁落ち
? 2次方程式の解と係数の関係
2 input "a,b,c";a,b,c
ax bx c 0 d=b*b-4*a*c
if d>=0 then
x1=(-b-sqr(d))/(2*a)
x2=(-b+sqr(d))/(2*a)
b b 2 4ac print x1,x2
x else
2a print "can not solve."
endif
end
a=1
b=10.02
c=0.1001
で、どんな値が得られるか試してみよう。このa; b; c は
(x + 10:01)(x + 0:01) = 0

計算過程

d=b*b-4*a*c
=10.02*10.02-4*1*0.1001
=100.4004 -0.4004 有効数字 7桁
=100.0000

sqr(d)=sqr(100.0000)
=10.00

x1=(-b-sqr(d))/(2*a)
=(-10.02-10.00)/2 負の数どおしの足し算
=-20.02/10 有効数字 4桁
=-10.01

x2=(-b+sqr(d))/(2*a)
=(-10.02+10.00)/2 異符号の値の足し算
=-.02/10 すなわち引き算
=-.01 有効数字 1桁へ

桁落ち
? 異符号の足し算(=引き算)で有効桁数が少なること

12345.67890 有効桁１０桁
-)12345.67809 有効桁１０桁
-------------
.00081 有効桁２桁

? 異符号の足し算を避けるようにアルゴリズムを考える

b d b d b d
x2
2a 2a b d
b2 d 4ac 2c 2a c 1
2a ( b d) 2a ( b d) 2a b d a x1

分散（統計学）の計算
? データ
x1 , x2 , ? , xn
? 平均
x1 x2 ? xn
x
n
? 分散
( x1 x ) 2 ( x2 x ) 2 ? ( xn x )2
V1
n
x12 2 2
x2 ? xn
V2 x2
n
数学的にはV1, V2とも同じであるが、桁落ちで同じ値にはならない。

V1が望ましいが、平均の計算と、分散の計算で2回データを必要とする。

分散その２

V3 [
2
{2 x2 ( x1 x2 )} /(2 1)
2
{3x3 ( x1 x2 x3 )} /(3 2)

?
2
{nxn ( x1 x2 x3 ? xn )} /(n (n 1))
] n

実数計算と誤差
? 実数で計算するといつも「誤差」がある？

? 誤差の無い計算もある

? 整数値しか扱わない計算
– 固定小数点で
– 浮動小数点でも

123(10)= 1111011(2)
=0.1111011(2)×27

– 浮動小数点の仮数部の桁数24bits以内であれば誤差なし

– 固定小数点の桁数は32bits、
浮動週数点を使うメリットは無い！

32bitsを超える整数値
? 固定小数点の多倍長計算
– 下手なプログラムはバグの元、計算も遅くなる？

? 浮動小数点
– 64bits倍精度表現、128bits4倍精度表現があり
– 固定小数点より大きな整数値が「誤差無し」で取り扱える！
– 仮数部 52bits、112bits

10進数何桁？

32bits単精度

31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

符指数部（8ビット）仮数部（23ビット、ケチ表現）
号

? 指数部 8ビット
– 下駄 01111111
– 1～254
– 0のとき、仮数部０であればゼロ
– 255のとき、無限大（仮数部０）、またはNaN（仮数部非０
）
? 仮数部 23ビット
– 絶対値表現
– 1.xxxxに正規化し、頭の１は記録しない（ケチ表現）
64bits倍精度 128bits4倍精度
指数部 11ビット指数部 15ビット
仮数部 52ビット仮数部 112ビット

狠狠撸

计算机理论入门05

Recommended

More Related Content

Viewers also liked (20)

Similar to 计算机理论入门05 (20)

More from Tomoyuki Tarumi (8)

Recently uploaded (8)

计算机理论入门05