BigIntegerの平方根

BigInteger.csに平方根計算を追加した．
多倍長整数の平方根計算の速度はhttp://mitv2.net/algorithm/intsqrt2.htmlに詳しくある．
ただ，ここにあるような初期値をtoString()使ったりpow()使ったりして10進で求める計算は必要なくて，2進で一桁大きい数を用意してやれば近似比は2で済むし，計算もシフト演算で済む．

public BigInteger Sqrt()
{
    BigInteger a, b = BigInteger.One.ShiftLeft((BitLength + 1) >> 1);
    do
    {
        a = b;
        // 相加平均法
        b = a.Add(this.Divide(a)).ShiftRight(1);
    } while (b < a);

    return a;
}

桁が大きいと10進の場合の半分くらいの時間で値が求まる．
相加平均法は10-近似が2-近似になったくらいで2倍も速くなるほどヤワなものではないと思うので，これは前処理の部分が効いてるんだろう．

BigInteger.cs
ソース置き場