近岡です。

>ところで、Google で「開平法」を調べたら、風変わりなのが、、、
>
>/* 2^30 <= x < 2^32 について root を計算する */
>unsigned long isqrt(unsigned long x)
>{
>    unsigned long a, b;
>    a = 143257 - 202860544/(1582+(x>>22));
>    a = (a + x/a)/2;
>    b = (a + x/a)/2;
>    return a > b ? b : a;
>}
>
>出所はなんと [ruby-list:1313] で、書いたのは私なのですが、書いた
>憶えが無い。(^^; どうやら痴呆らしい。そこには「証明がある」とか
>「ニュートン法を1回に減らせる」とかありますが、どなたかその記事
>を持っていないですかね。日経MIXらしいのですが、私は紛失してい
>まいました。

今、仮に十分大きな自然数 m について
x=(m+1)^2−1=m^2+2m とすると isqrt(x)=m です。
ここで、
 a>m+1のとき、b=(a+x/a)/2≧m+1
 a=m+1のとき、b=(a+x/a)/2=m
 a<m+1のとき、b=(a+x/a)/2≧m+1
が成り立ちますから、
1回で終らせるためには a=m または a=m+1 である必要があります。

2^30 <= x < 2^32の範囲内で
x=(m+1)^2−1=m^2+2m と表されるすべての整数に対して、
a=m または a=m+1 であるようなaを求める簡便な式が
存在するのでしょうか?

# それとも1回のループで、b=m+1となるよう調節しておき、
# b-1を帰すのでしょうか?

0----+----1----+----2----+----3----+----4----+----5----+----6
近岡 宣吉  Chikaoka, Nobuyoshi
富山県立高岡西高等学校(数楽科)
 E-mail : chikaoka-nobuyoshi / tym.ed.jp