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: 28 Feb 1995 01:10:05 GMT
Organization: College of Arts and Sciences, Univ. of Tokyo
Lines: 22
Message-ID: <MAKINO.95Feb28101041@xsi09.komaba.c.u-tokyo.ac.jp>
References: <JIRASAK.95Feb27143828@alpha.ics.nitech.ac.jp>
	<3is44n$6p7@isnews.is.s.u-tokyo.ac.jp>
	<MAKINO.95Feb27220145@xsi09.komaba.c.u-tokyo.ac.jp>
NNTP-Posting-Host: xsi09.komaba.c.u-tokyo.ac.jp
In-reply-to: makino@komaba.c.u-tokyo.ac.jp's message of 27 Feb 1995 13:01:11 GMT

自己フォロー（訂正）です、、、
In article <MAKINO.95Feb27220145@xsi09.komaba.c.u-tokyo.ac.jp>
makino@komaba.c.u-tokyo.ac.jp (Jun Makino) writes:
>   iteration のたびに割算を使うなんていうのは、割算用のハードをもった機械
>   でなければ現実的ではないと思います。sqrt(x) のかわりに sqrt(1/x)をニュー
>   トン法で求めて、求まった答えに x を掛けるやり方なら割算は不要となりま
>   す。
>
>   たしか 1987年くらいの CACM の Programming pearls というコラムにこのへ
>   んをいろいろいじり回す話がでてました。（これは本になって日本語訳もあっ
>   たような気がします）

日本語訳は近代科学社「プログラマのうちあけ話」J.E.ベントリー著でしたが、
割算なしでやるアルゴリズムは紹介されていませんでした。一応式を書くと、
f(x) = a - 1/x^2 として、ニュートン法の式 x_new = x_old - f(x)/f'(x)
に入れると割算のない式が出てきます。

Computer Arithmetic Systems, Amos R. Omondi, Prentice Hall 1994 には上
の方法が出てます（その他の方法もいっぱいでてます）。 Cray-2 ではこれが
つかわれているとのことでした。 

牧野＠東大駒場