==

减法:   按照数学定义 x-y 等价于 x+(-y), 因此实现上先将 y 求其对应负数, 然后 用已经实现的加法就可完成减法的运算.

  因此只需要研究如何求负数即可.

  求一个数的负数 neg(), 等于将该数字二进制求补码, 也即先反转所有二进制位

然后加上 1. 代码示例如下:

  int carry = 1; // 整个数反转后要+1, 所以初始为 1.

  for (int i = 0; i < len; ++i) {     carry += (~src.arr[i]) // 二进制反转, ~ 为求反运算.         & 0xff; // 取 byte 部分.     dest[i] = (byte)carry; // 取低位.     carry >>>= 8;  // 进位部分   }   boolean overflow = src[len-1] < 0 && dest[len-1] < 0;   if (overflow) dest[len++] = 0;   return new mp_int (len, dest); // 结果

  关于 overflow 标志, 举例如数字 = -128=0x80 时, 取反得到 0x7F, 加上1

又回到 0x80, 此时称为 overflow. 这种情况只发生在最高位为 1, 其余所有位 都是 0 的情况. 此时求负之后的数字要当做无符号数看待, 在最高位补上一个 0 (dest[len++] = 0 即为最高位补0).

==

乘法   为简化问题, 只考虑正数的乘法, 如果x,y 有负数, 先对齐求负转换为正数, 然后再进行乘法.

  类似于我们手写数字乘法竖式, 我们将各个位逐个相乘, 并累加到结果上,

有进位的继续向高一位累加. 这样一个 m位的数字乘上一个 n位的数字, 得到的 结果为 m*n 位的. 伪代码如下:

  mul(byte[] dest, byte[] x, int xlen, byte[] y, int ylen)

  // 计算乘积, 使得 dest = x*y     for (int i = 0; i < ylen; ++i) {       int yword = (int)y[i] & 0xff; // 取y 的第 i位.       int carry = 0; // 进位.       for (int j = 0; j < xlen; ++j) {         carry += ((int)x[i] & 0xff) // 取 x 的第 j 位.     * yword ; // 乘上 y 的第 i 位     + ((int)dest[i+j] & 0xff); // 加上现有第 i+j 位.  dest[i+j] = (byte) carry;  // 更新到结果的第 i+j 位  carry >>>= 8; // 得到第 i+j+1 位的进位. 这个进位可能大于 1       }       dest[i+xlen] = (byte)carry;     }

  这里细节可能有些忽略的地方, 但基本原理是每位分别乘积, 最后累加到一起.

==

除法   除法的实现代码看起来是比较复杂. 不如直接看书理解原理容易. 实际上我看 的 Kawa 源代码中也注释写着使用的是基本的 Knuth 经典算法的公式. 所以为 学原理, 这里还是看书更直接些.     为实现除法 u/v, 我们先排除掉一些简单的情况: 1. 如果 u < v, 则除法 u/v 的商(quotient)=0, 余数(remainder)=u 2. 排除掉 u = v 的情况.

  现在 u > v, 先考虑 u 只比 v 多一位的情况, 此时 u 表示为

(u_n, u_(n-1), ... , u_1, u_0) 这里用下划线这里表示后面跟着下标的意思. v 表示为 (v_(n-1), v_(n-2), ..., v_1, v_0) 的形式. 如果找到了求 这种形式的商, 也就能为更多位的 u 进行计算了, 因为可以先计算前 n+1 位, 然后再进一步加上后面的位.

  设 u = q*v + r;  则这里 q 表示商, 满足 q < b; 而 r 表示余数, 满足 r < v.

  要推测 q 的值的合理方法是, 使用 u,v 的最高位的有效数字进行推测. 这里最高位的有效数字, 指高位的 m 个二进制位, 其中最高位是1. (这里都按照 无符号整数看待, 最高位为1 仍然是正数). m 越多, 推测的就越准确.

  Knuth 的书上还有这方面的定理, 以及...证明. 这里说明, 要有好的数学功底,

才能真正理解这背后的原理, 而我数学已经很多年不学从而忘得差不多了. 因此这里, 我们努力理解这些原理, 实在理解不了, 就只能照用了.

  要得到最高位的有效数字, 在代码中我看到是使用了向左移位的方法, 将有效

位都移动到了高位. 这样计算试验商 q 比较准确些. 并且这里使用 int 型而非 byte 型, 可以使二进制位数 m 较多, 从而 q 准确性更高. 实际书上证明了 q'-2 <= q <= q', 这里 q' 表示试验商. 也即试验的商 q' 的误差绝不大于 2.

  到这里, 我们基本可以理解算法D(整数除法)的核心部分: 试商的求取了.

算法D 系统的给出了求取试商以及修正方法, 然后其它一些步骤, 这里略, 请 参考原书.