√２ の話：その１４：√２の求め方。★Ｓｉｍｐｌｅな考え方：その３

↓http://yamada-kuebiko.cocolog-nifty.com/blog/2015/01/post-3731.html
2015年1月23日 (金)「√２ の話：その１３：√２の求め方。★Ｓｉｍｐｌｅな考え方：その２」

Ｓｉｍｐｌｅな考え方：その１とその２では
●小さい側から始めて、一歩ずつ進み、踏み越えたら一歩戻って、歩幅を小さくして、また進む。
こういう考え方をしました。

★今度は真値への接近法を変えてみたいと思います。
今度は
●小さい側から始めて、一歩ずつ進み（右へ）、踏み越えたら向きを変えて、歩幅を小さくして進む（左へ）（戻る）。
また踏み越えたら、また向きを変えて、歩幅を小さくして進む（右へ）（戻る）。

このように、真値を挟んで、行ったり来たり、右へ左へ向きを変えながら歩幅を小さくして接近していこうという戦略です。

★さて、「踏み越えたら」の判断ですが、小さい側から大きい側へ踏み越えた場合と、逆に大きい側から小さい側へ踏み越えた場合を別々に判断するのは、できるんですけど、鬱陶しい。統一的にできた方がスマートだ。

図を見てください。
aとbを近似値として。
真値の同じ側にaとbがある場合は f(a)とf(b)も両方とも負か、両方とも正です。
ですから、f(a)*f(b) は正です。
（踏み越えて）aとbが真値を挟んだ場合、f(a)とf(b)は必ず符号が異なりますので、
f(a)*f(b) は負です。

これを使いましょう。
「踏み越えたら向きを変えて、歩幅を小さくして進む」ということの「踏み越えたら」の判断はこれ一つで済みます。

もう一つ工夫を。
「向きを変えて」なのですが。
a = a + stp
これで一歩ずつ進むのでした。
これを
a = a + flg * stp
とします。
flg は flag です。旗を立てるんですね。
出発時 flg=1 とます。
a = a + flg * stp
は大きい方へ向かって一歩ずつ進むということになります。

踏み越えたという判断が出たら
flg = flg * (-1)
とします。すると
a = a + flg * stp
は小さい方へ向かって一歩ずつ進むということになります。
向きが変わるたびに、flgに(-1)をかけてやると、進む向きが反転するのです。
よくやるテクニックです。

★さて、これらをプログラムにすると
********************
!行きすぎたら向きを変えて戻る。平方根のみ。
!平方数には対応せず。
DECLARE EXTERNAL FUNCTION f

INPUT PROMPT "n = ": n
LET stp =1
LET flg = 1                         !進む向きを与える「flag」。正なら右へ、負なら左へ。
LET a = 0
FOR i = 1 TO 100
   LET tmp = f(a, n)                !a での関数値
   LET a = a + flg*stp              !一歩先   
   LET b = f(a, n)                  !一歩先での関数値
   LET tmp = tmp * b                !関数値の積

   IF tmp < 0 THEN                  !積が負なら。（真の値を挟んだ！）
      PRINT i;
      PRINT a;
      PRINT a*a
      LET stp = stp / 10            !歩幅を1/10に
      LET flg = flg * (-1)          !向きを反転
   ELSE
      IF tmp = 0 THEN               !平方数が与えられた時の処置
         PRINT i;
         PRINT a;
         PRINT a*a
         EXIT FOR                   !FORループを強制的に脱出
      END IF
   END IF
NEXT i

END

EXTERNAL FUNCTION f(x, n)
LET f = x*x - n
END FUNCTION
********************

★では実行結果を
n = 2
2  2  4
8  1.4  1.96
10  1.42  2.0164
16  1.414  1.999396
19  1.4143  2.00024449
28  1.41421  1.9999899241
32  1.414214  2.000001237796
37  1.4142135  1.99999982358225
44  1.41421357  2.00000002157214
52  1.414213562  1.99999999894473
56  1.4142135624  2.0000000000761
59  1.41421356237  1.99999999999125
63  1.414213562374  2.00000000000256
73  1.414213562373  1.99999999999973
83  1.4142135623731  2.00000000000001

行きつ戻りつしていることがよくわかります。
また１０００桁モードで１０００回まわして最後のところだけお目にかけましょう。
1000
1.
4142135623 7309504880 1688724209 6980785696 7187537694
8073176679 7379907324 7846210703 8850387534 3276415727
3501384623 0912297024 9248360558 5073721264 4121497099
9358314132 2266592750 5592755799 9505
1.
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999999 9999967394 3995095884
8443272076 7502274119 0610612930 3694650907 8971505951
2711679600 6160303012 0458538212 0796152915 8899120799
2261135475 0238544673 7071803584 7881320550 9824399061
5379957175 80245025

(参考)
★Ｓｉｍｐｌｅな考え方：その２ で得た結果と比較してください。ほぼ同じといっていいのでしょう。
993
1.
4142135623 7309504880 1688724209 6980785696 7187537694
8073176679 7379907324 7846210703 8850387534 3276415727
3501384623 0912297024 9248360558 5073721264 4121497099
9358314132 2266592750 55927557

1.
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999999 9999999999 9999999999
9999999999 9999999999 9999999717 2972914074 9587760834
2065613833 8946232559 2854640200 6918559451 5930651819
5006313683 2928984512 4159757899 0595865375 3300033219
7264611468 8416590196 4540411810 5154967204 7410241631
988249

★大雑把に。
１０００回の繰り返しで、１７０～１８０桁程度の精度。