« シラン | トップページ | ツバキ »

2015年1月28日 (水)

√2 の話:その15:√2の求め方。★ちょっと凝った考え方:その1「二分法」

Simpleの次ですから、Sophisticated Methodのつもりです。
今回は
●二分法
解説は√2について行います。
√2はf(x) = x^2 - 2 という曲線がx軸と交わる点の座標です。
√2の真値を挟むaとbという区間を考えます。
実用上はa=0、b=2で構いません。
0<√2<2 ですので。
aとbが真値を挟んでいることはf(a)*f(b)<0でわかるわけですね。
これと同じ論法を使います。
Nibun1
aとbの中点をcとしましょう。このとき
f(a)*f(c)>0なら、cは真値の左側にありますので、cを新たなaとして繰り返します。
Nibun2
f(a)*f(c)<0なら、cは真値の右側にありますので、cを新たなbとして繰り返します。
区間を半分にして、真値がどちら側にあるかを調べて、またその新たな区間を半分にする、ということです。
これだけ。考え方は実にシンプル。

******************************
!二分法
DECLARE EXTERNAL FUNCTION f

!root(2) = 1.4142135623730950488016887242097
!root(3) = 1.7320508075688772935274463415059

INPUT PROMPT "n = ": n
LET a = 0
IF n > 1 THEN
   LET b = n
ELSE
   LET b = 1
END IF

FOR i = 1 TO 20 STEP 1
   LET c = (a + b) / 2
   IF f(a, n)*f(c, n) < 0 THEN
      LET b = c
   ELSE
      LET a = c
   END IF
   PRINT i;
   PRINT c;
   PRINT c*c
NEXT i
END

EXTERNAL FUNCTION f(x, n)
LET f = x*x - n
END FUNCTION
******************************
実行結果
n = 2
1  1  1
2  1.5  2.25
3  1.25  1.5625
4  1.375  1.890625
5  1.4375  2.06640625
6  1.40625  1.9775390625
7  1.421875  2.021728515625
8  1.4140625  1.99957275390625
9  1.41796875  2.01063537597656
10  1.416015625  2.00510025024414
11  1.4150390625  2.00233554840088
12  1.41455078125  2.00095391273499
13  1.414306640625  2.00026327371597
14  1.4141845703125  1.99991799890995
15  1.41424560546875  2.00009063258767
16  1.41421508789063  2.0000043148175
17  1.41419982910157  1.99996115663091
18  1.4142074584961  1.999982735666
19  1.41421127319337  1.99999352522721
20  1.414213180542  1.99999892001872

こんなふうにして真値を挟むようにして接近していきます。

1000桁モードで1000回やると
300桁くらい正しいようです。
片側から近づく方法や、真値の周辺を行ったり来たりしながら近づいていく方法の時は
1000回で約170~180桁くらいでしたから、真値に近づくスピードはかなり速いようです。
2つに分けて探っていくというのは、かなり速いものでして、プログラミングの世界でも「2分探索」というようなアルゴリズムがあります。2つに分けるなんて大したことはないような気もしますが、どうしてどうして。
昔、私が小学生の頃、NHKラジオで「二十の扉」という番組がありました。「それは動物ですか?」とか「それは○○ですか?」という問いを20回行うことで、隠された答えを当てるというものです。
2^20=1048576ですから、20回の問で原理的には100万もの識別ができようというものです。
2分法による√2の探索もなかなかのものでした。

1000
1.
4142135623 7309504880 1688724209 6980785696 7187537694
8073176679 7379907324 7846210703 8850387534 3276415727
3501384623 0912297024 9248360558 5073721264 4121497099
9358314132 2266592750 5592755799 9505011527 8206057147
0109559971 6059702745 3459686201 4728517418 6408891986
0955232923 0484308714 3214508397 6260362799 5251407989
8266667953 3176240536 2505455576 9131245589 7105727317
以下略

2.
0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000
0000000000 0000000000 0000000000 0000000000 0000000000
3943206386 7776945289 9974296479 5829890218 4931321519
以下略

« シラン | トップページ | ツバキ »

理科おじさん」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

« シラン | トップページ | ツバキ »

2017年9月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
サイト内検索
ココログ最強検索 by 暴想
無料ブログはココログ