« 河津桜・駅前 | トップページ | 梅 »

2015年3月11日 (水)

√2 の話:その31 真値を挟む範囲について:2

★整数平方根というものについて、3回ほど書きました。
「√nを超えない最大の整数を返す関数で、しかもすべて整数だけを使ってプログラムを組む、という関数。」
つまり平方根の整数部を返す関数と同義の自作関数です。
下にリンクしておきます↓
http://yamada-kuebiko.cocolog-nifty.com/blog/2015/02/post-9502.html
2015年2月20日 (金)「√2 の話:その24:整数平方根:1」
奇数を次々に足していくと、平方数になる。
「足した奇数の個数」を自乗した数が得られるわけです。

http://yamada-kuebiko.cocolog-nifty.com/blog/2015/02/post-4745.html
2015年2月23日 (月)「√2 の話:その25:整数平方根:2」
要するに、nを超えない最大の平方数a^2を見つければ、そのaが求めるものであるわけです。
まるっきり効率的ではありませんが、aを2から順に自乗して、nと比べ、nを超えたら、一つ前のaを返せばいい。
単純明快です。

http://yamada-kuebiko.cocolog-nifty.com/blog/2015/02/post-fd40.html
2015年2月24日 (火)「√2 の話:その26:整数平方根:3」
ニュートン法を整数で実行すればよい

★考えてみますと、この関数が返す値をaとすると
a≦√n<a+1
こういう関係になりますよね。
左の不等号が「≦」なのは、nが平方数の場合に「=」になるからです。これはちょっと注意点かもしれない。
とにかく、これで√nの真値を整数aとa+1の間の幅1の区間に挟みこめました。
これ、いいじゃないですか。
ニュートン法を整数で行うタイプの isqrt を使って見積もり、ニュートン法を実数で実行するというのは論理的に気分悪いから、私の「こだわりの」足した奇数の個数を返す、というやつを使ってみることにします。
{いいですけど。整数で実行して範囲を絞り、絞り込んだうえで実数での計算に切り替える、というのは別に自己矛盾をきたしているわけじゃないし。ただ、ちょっと趣味の問題ですかね。いややっぱり「意地」かな。}

!********************
! ニュートン法によって平方根を求める
DECLARE EXTERNAL FUNCTION f
DECLARE EXTERNAL FUNCTION g
DECLARE EXTERNAL FUNCTION isqrt

!1.4142135623730950488016887242097
!1.7320508075688772935274463415059

INPUT PROMPT "n =" :n
IF n >1 THEN
   LET x = isqrt(n)+1
ELSE
   LET x = 1
END IF

FOR i = 1 TO 15
   LET x1 = x - (f(x, n)/g(x))
   PRINT i;
   PRINT x1
   PRINT x1*x1
   LET x = x1
NEXT i
END
!********************
EXTERNAL FUNCTION f(x, n)
LET f = x*x - n
END FUNCTION
!********************
EXTERNAL FUNCTION g(x)
LET g = 2*x
END FUNCTION
!********************
EXTERNAL FUNCTION isqrt(n)
IF (n = 0) THEN
   LET isqrt = 0
Else
   LET a = 1
   LET count = 0
   LET sum = 0
   DO
      LET a = a + 2
      LET sum = sum + a
      LET count = count + 1
   Loop While (sum < n)
   LET isqrt = count
END IF
END FUNCTION
!********************

n=1000で実行してみました。
n =1000
1  31.625
1000.140625
2  31.6227766798419
1000.00000494315
3  31.6227766016838
1000
4  31.6227766016838
1000
なんと、十進15桁では、ループ3回で収束してしまった。

√n<nによって、出発点を1000で始めると
ループ10回で収束ですからさすがに速くなりますね。

★この他、はさみうち法、割線法、二分法も同じように、見積もりの幅を狭くするることができて、大幅に改良されます。
プログラムは掲載しません。整数平方根を組み込んで、範囲の見積もりをする、という方針でやれば難しいことではないので。
リクエストがありましたらお寄せ下さい。そうなれば掲載します。

« 河津桜・駅前 | トップページ | 梅 »

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

コメント

コメントを書く

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

« 河津桜・駅前 | トップページ | 梅 »

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 暴想
無料ブログはココログ