BigInteger:大整数加减乘除如何实现

  0                                  signum=0  mag=[]
  5                                  signum=1  mag=[5]
  -5                                 signum=-1 mag=[5]
  2147483648                         signum=1  mag=[-2147483648]
  4294967296                         signum=1  mag=[1, 0]
  18446744073709551616               signum=1  mag=[1, 0, 0]
  -18446744073709551616              signum=-1 mag=[1, 0, 0]
  123456789012345678901234567890     signum=1  mag=[1, -1897328650, -1015815954, 1312754386]
  add 返回新对象:x.add(1) == x 吗?true(加 0 时返回自己);x.add(1) == x 吗?false
  mag 是大端的 int[](最高位在前),符号单独存在 signum 里,所以 -2^64 与 2^64 的 mag 相同

     位数(bit)        耗时(ms)相邻两档的指数 log2(t2/t1)/log2(n2/n1)
        2048        0.0106           -
        4096        0.0098       -0.11
        8192        0.0400        2.03
       16384        0.1117        1.48
       32768        0.1953        0.81
       65536        0.3389        0.80
      131072        0.9008        1.41
      262144        2.9641        1.72
      524288        7.3975        1.32
     1048576       20.3938        1.46
     2097152       59.4535        1.54
  指数 2 = 小学乘法(n²);约 1.58 = Karatsuba;约 1.46 = Toom-Cook 3;比这更低说明还有更快的算法或测量噪声

         十进制位数   toString (ms)new BigInteger(s) (ms) toString 指数
         50000            8.82           50.46           -
        100000           14.24          200.73        0.69
        200000           34.99          809.06        1.30
        400000           91.37         3224.15        1.38
        800000          236.08        12880.87        1.37

  模数 2048 位(两个 1024 位素数之积),指数 1024 位:modPow 1.5 ms
  模数 4096 位(两个 2048 位素数之积),指数 2048 位:modPow 10.2 ms
  模数 6144 位(两个 3072 位素数之积),指数 3072 位:modPow 33.0 ms
  模数 8192 位(两个 4096 位素数之积),指数 4096 位:modPow 77.3 ms
  生成一个 1024 位素数(probablePrime):39 ms
  pr.isProbablePrime(64) = true,8.64 ms