浅谈 BigInteger.Sqrt 方法

01:  using System;
02:  using System.Numerics;
03:  
04:  namespace Skyiv
05:  {
06:    public static class Extensions
07:    {
08:      public static BigInteger Sqrt(this BigInteger x)
09:      {
10:        if (x.Sign < 0) throw new ArgumentOutOfRangeException("x", "must greater than 0");
11:        BigInteger low, high;
12:        GetLowAndHigh(x, out low, out high);
13:        var mid = low;
14:        var cmp = 0;
15:        while (low.CompareTo(high) <= 0)
16:        {
17:          mid = (low + high) / 2;
18:          cmp = (mid * mid).CompareTo(x);
19:          if (cmp < 0) low = mid + 1;
20:          else if (cmp > 0) high = mid + (-1);
21:          else return mid;
22:        }
23:        if (cmp > 0) mid--;
24:        return mid;
25:      }
26:  
27:      static void GetLowAndHigh(BigInteger x, out BigInteger low, out BigInteger high)
28:      {
29:        var n = x.ToByteArray().Length;
30:        if (n < 2)
31:        {
32:          low = 0;
33:          high = x;
34:          return;
35:        }
36:        var bs = new byte[n / 2 + 1];
37:        var k = bs.Length - 2;
38:        if (n % 2 == 0)
39:        {
40:          bs[k] = 0x0B;
41:          low = new BigInteger(bs);
42:          bs[k] = 0xB6;
43:          high = new BigInteger(bs);
44:        }
45:        else
46:        {
47:          bs[k] = 0xB5;
48:          low = new BigInteger(bs);
49:          bs[k] = 0x51;
50:          bs[k + 1] = 0x0B;
51:          high = new BigInteger(bs);
52:        }
53:      }
54:    }
55:  }

上述程序中第 27 到 53 行的 GetLowAndHigh 方法用于获得指定的大整数的平方根的下限和上限，然后在第 8 到 25 行的 Sqrt 方法中使用二分搜索来找出所求的平方根。

BigInteger.ToByteArray 方法将 BigInteger 转换为字节数组。对于大于零的 BigInteger ，转换后的字节数组的长度固定的情况下，最小值为 00-80-00-00-00 形式，最大值为 7F-FF-FF-FF-FF 形式，刚好比下一组最小值小一。如下表所示：

从上表中可以看到，假设 x 转换为字节数组后，长度为 n ，则 Sqrt(x) 转换为字节数组后，其长度为 n / 2 + 1。

对于 n 为偶数的情况(程序中第 40 到 43 行)：

• 最小值大于 00-0B-00-00-...
• 最大值小于 00-B6-00-00-...

对于 n 为奇数的情况(程序中第 47 到 51 行)：

• 最小值大于 00-B5-00-00-...
• 最大值小于 0B-51-00-00-...

在 .NET Framework 2.0 中并没有 BigInteger。我以前自己用 C# 写过 BigInteger，也实现了 Sqrt 方法。可以参见以下随笔：

• Timus 1153. Supercomputer
• 浅谈 BigInteger
• 再谈 BigInteger - 使用快速傅里叶变换
• BigArithmetic - 提供任意精度的算术运算的静态类

使用快速傅里叶变换实现 BigInteger 时，是调用 BigArithmetic 类的静态方法。其中 Sqrt 方法是使用牛顿迭代法计算平方根：

Ui+1 = Ui (3 - VUi2) / 2

则 U∞二次收敛于 1/√V，最后乘以 V 就得到√V。求平方根的速度比本文中的二分搜索法要快。