独自の平方根関数を作成する

質問

整数の最も正確な平方根を求めるための独自の関数をどのように書けばよいのでしょうか？

ググってみたところ この (その オリジナル・リンク を参照）、第一に、完全に理解できなかったこと、第二に、これも近似値であることです。

平方根を最も近い整数（実際の根に）または浮動小数点数として仮定する。

どのように解決するのですか？

以下は、N > 0 に対して floor(sqrt(N)) を計算するものです。

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

これはCrandall & Pomerance, "Prime Numbersで示されたNewtonの方法のバージョンである。A Computational Perspective"で述べられているニュートンの方法のバージョンです。この方法を使うべき理由は、この方法が平方根の底に正確に収束することを、よく知っている人たちが証明しているからである。また、高速でもあります（さらに高速なアルゴリズムを構築することは可能ですが、それを正しく行うことははるかに複雑です）。適切に実装されたバイナリサーチは非常に小さな N に対してより高速になりますが、そこではルックアップテーブルを使用したほうがよいでしょう。

に丸めるには 最も近い 整数に丸めるには、上記のアルゴリズムで t = floor(sqrt(4N)) を計算すればよいのです。tの最下位ビットが設定されていれば、x = (t+1)/2を選択し、そうでなければt/2を選択します。余りが0でないかどうか（すなわち、t^2 == 4Nであるかどうか）を見ることによって、切り捨てる（または偶数に丸める）こともできます。

浮動小数点演算を使用する必要がないことに注意してください。実際、使うべきではありません。このアルゴリズムは完全に整数を使用して実装されるべきです（特に、floor()関数は、通常の整数の除算が使用されるべきであることを示すだけです）。