Path: coconuts.jaist!wnoc-tyo-news!news.u-tokyo.ac.jp!komaba!makino
From: makino@komaba.c.u-tokyo.ac.jp (Jun Makino)
Newsgroups: fj.sci.math
Subject: Re: [help]square root computational cost
Date: 27 Feb 1995 13:01:11 GMT
Organization: College of Arts and Sciences, Univ. of Tokyo
Lines: 38
Message-ID: <MAKINO.95Feb27220145@xsi09.komaba.c.u-tokyo.ac.jp>
References: <JIRASAK.95Feb27143828@alpha.ics.nitech.ac.jp>
	<3is44n$6p7@isnews.is.s.u-tokyo.ac.jp>
NNTP-Posting-Host: xsi09.komaba.c.u-tokyo.ac.jp
In-reply-to: tion@is.s.u-tokyo.ac.jp's message of 27 Feb 1995 08:56:55 GMT

In article <3is44n$6p7@isnews.is.s.u-tokyo.ac.jp>
tion@is.s.u-tokyo.ac.jp (T. Yamane) writes:

>   Jirasak> 研究しているアルゴリズムの中に２乗根 (square root) が使われています．
>   頻繁に使われるでしょうね、sqrt くらいなら。
>   Jirasak> ２乗根を求める簡単な方法を探していますが，
>
>   x $\leftarrow$ \frac{x^{2}+c}{2x}
>   では、御不満なのでしょうか。
>
>   Jirasak> なかなか見つからないのです．
>
>   いくら工学系とはいえ、sqrt の Newton-Raphson 法による算出くらいは、
>   ご存知かと思いますが、まぁ、何かの折ですから、念の為書いておきました。

iteration のたびに割算を使うなんていうのは、割算用のハードをもった機械
でなければ現実的ではないと思います。sqrt(x) のかわりに sqrt(1/x)をニュー
トン法で求めて、求まった答えに x を掛けるやり方なら割算は不要となりま
す。

たしか 1987年くらいの CACM の Programming pearls というコラムにこのへ
んをいろいろいじり回す話がでてました。（これは本になって日本語訳もあっ
たような気がします）

>   Jirasak> なお，２乗根を求めるために必要なかけ算と足し算の回数も知
>   Jirasak> りたいのですが． 

といわれても、要求精度とかがわからないと数えようがないですよね。たとえ
ば入力の範囲がわかっていて精度が低くて良ければ、適当な大きさのテーブル
を引けば演算数ゼロで答が求まってしまいます。

>   規定有限回演算で希望精度を求めたいなら、NR はあまり適した方法では
>   ないですね。 

なぜでしょう？初期推定値の誤差がわかっていれば、必要な繰り返し回数はあ
らかじめわかりますが。

牧野＠東大駒場