Path: sran265!katsu From: katsu@sran14.sra.co.jp (Katsuhiro Watanabe) Message-ID: Date: 16 Oct 91 22:51:54 Organization: Software Research Associates, Inc.,Japan In-reply-to: inoue@tomato.oishi.info.waseda.ac.jp's message of 16 Oct 91 09:26:22 GMT Newsgroups: fj.sci.math Subject: Re: the closest integer to root Distribution: fj References: <1926@commgw.comm.waseda.ac.jp> <1927@commgw.comm.waseda.ac.jp> 平方根にもっとも近い整数を求めるアルゴリズムに関して、 記事 で kunnta@flab.Fujitsu.CO.JP (KOJIMA Hideki) さんいはく > 問題の自然数をＮとします。 > ｍ＾２＞＝Ｎとなる最小の自然数ｍを求めます。 > （ｍ＝１、２、３、４..... と順番に試していけばいいですよね。） > あとは、ｍ＾２と（ｍ−１）＾２のどっちがＮに近いかを調べて終り。 　このやりかたをやる時には、 　m^2 と (m-1)^2 のどちらが n に近いかということ（上の説明に対応）と、 m と m-1 のどちらが n の平方根に近いかということ（問題文に対応）が、 同等であることを示さなければならないと思います。以下にこれを示します。 　n を自然数とする。(m-1)^2 < n <= m^2 を満たす自然数 m は常に存在する。 このとき、 n - (m-1)^2 < m^2 - n ならば、sqrt(n) - (m-1) < m - sqrt(n) であることを示す。 （逆も同じアイデアで示せる。不等号の向きが逆の場合（裏のようなやつ）も 同じアイデアで示せる。不等号の部分が等号になるような場合がないことは、 n^2 - (n-1)^2 が奇数であること、sqrt(n) が整数+(1/2)にならないことから 示せる） n - (m-1)^2 < m^2 - n を整理すると、 n < m^2 - m + 1/2 ところが n と m は自然数だから n <= m^2 - m といってよい。さらに n < m^2 - m + 1/4 n < (m - 1/2)^2 n は自然数だから sqrt(n) < m - 1/2 2 sqrt(n) < 2m - 1 sqrt(n) - (m - 1) < m - sqrt(n) （証明終り） 一方、 記事 で katoh@flab.Fujitsu.co.jp (Hideki KATO) さんいはく > 元の数から 1, 3, 5, ... を順に引き，負になる > 手前でやめれば floor(sqrt(n)) が求まります．round(sqrt(n)) > を求めるための補正が簡単にできるかどうかは検討していません， 　乗算不要なのでかっこいいですね。 　上の証明から、m^2 と n の世界での「もっとも近い」が、 m と sqrt(n) の世界の「もっとも近い」にそのまま対応すると わかったので話は簡単です。 　たった今 2m-1 (m は自然数）を引いた時点だとすると、ここまでの総合計で m^2 ぶんを引いたことになりますよね。次には 2m+1 を引く（そして総合計は (m+1)^2 ）ことを考えて、今現在残っている n が n <= m ならば round(sqrt(n)) は m n > m ならば round(sqrt(n)) は m+1 以上（引き算を続ける） ということになります。 -- ----____----____ 渡邊克宏　ＳＲＡソフトウェア工学研究所