《3大整数求余数的问题分析》由会员分享，可在线阅读，更多相关《3大整数求余数的问题分析（4页珍藏版）》请在金锄头文库上搜索。
1、大整数求余数的问题分析问题描述最近在学习一些资料的时候正好看到一些和大整数求余数相关的问题，这些问题粗粗看来似乎有点麻烦。 但是当结合一些有关数学的特性来分析时，会觉得很有意思。问题1:求一个整数X的N次方除以某个整数P的余数。用数学公式表示则如下：XmodP)其中 N 0, P 0.这个问题需要考虑的就是如果N比较大的时候，很可能就超出我们所用一般数据类型所能表示的范围。 如果直接去求X的N次方，就算有数据能保存的下来，肯定也会消耗大量的时间和空间。问题2:给定一个很大的数，求它除以某个整数P的余数。这个数因为足够大到没办法用普通的数据类型来表 示，所以需要用一个整数类型的数组或字符串来保存
2、。结果也是要求X mod P问题1分析最初分析我们先来看第一个问题。这个问题假定X和P并不是太大，可以用一个计算机的常用数据类型来表示。 一种最简单直白的方法就是我们直接将所有N个X相乘，然后再对被除数P相除，求余数。当然，这是基于一 个前提，我们有能够保存足够大的数据类型。如果我们对这种思路的时间和空间复杂度做一个粗略的估计的话， 会发现，假设X是int类型的整数，占4个字节，而最坏的情况就是每次相乘的结果就占用的结果增加4个字 节，这样N次乘积就需要占用4N字节的空间。而如果算上每次相乘的中间结果，占用的空间就达到N*N的量 级。再看时间复杂度，假定两个int类型的整数乘积的运算时间单位为
3、1的话，在没有任何优化假定的前提下， 一个32位整数和64位整数乘积的时间则为原来的两倍。如果以这个标准来分析的话，后面的时间复杂度也到 了 N*N量级。第一步改进可见，虽然前面这种办法虽然理论上可行，但是实际上时间和空间复杂度太大，不太合适。现在我们再 来看看另外一种思路。因为问题的关键就是指数N比较大，如果能将指数能够降下来，将其转换成对等的表达 式,则问题就好解决了。我们看前面求乘积的过程，假定是最简单的情况，N =2，则相当于求(X * X) mod D.如 果利用整数求余数的性质，我们发现他们满足下面的性质：(X Y)X(Y mod P) modF = (X niodP)(Y mod
4、P) modF这个等式的证明可以参照相关的数学材料或者文章后面的补充证明部分。通过这个性质，至少我们可以发 现，对于两个数的乘积求余数，我们可以先求一个数的余数，然后再将这个余数乘以另外一个数再求余数。这 样就可以求出来两个数乘积的余数。那么，如果对于3个，4个甚至更多的数的乘积求余数呢？我们可以将这 个等式扩展一下，对于3个数的乘积，我们可以先求出前面两个数乘积的余数，再和第三个数相乘求。依次类 推，重复N次就可以求出N次方的结果。于是，基于这种思路，我们可以写出如下的代码：Java代码二_1- public static long power(long x, long n, long p)
5、2. 3. if (n = 0)4. return 1;5.6.long tmp = x % p;7.for(long i = 0; i 0)6. 7. tmp = (x * x) % p;8. if (n % 2 != 0)10-tmp = (tmp * x) % p;8. n /= 2;9. 13.10. return tmp;11. 问题2分析结合前面的情况，因为问题2中本身需要求模运算的数字比较特殊，不是用一个普通的数据类型来保存， 而是用的整型数组或者字符串数组。在这种情况下，我们需要考虑的是利用一些模运算的特性，使得整个运算 的过程拆分成可运算的各个小的步骤。在这里，我们先假设是1
6、0进制的数字，比如说一个int数组1, 2, 3, 4, 5, 6,那么他们实际对应的这个数字应该是如下：121456=1 X105 2xl04 +3x 103 + 4x 102+5x 10L + 总龙10。这就相当于转换成了一个多项式求和的问题。对于一个整型的数组表示的长数据，我们按照多项式方式求和的 典型代码如下：Java代码*1. public static long sum(int array)2. 3.long sum = 0;4.for(int i = 1; i array.length; i+)5.6.sum = sum * 10 + arrayi;7.8.return sum;
7、9. 如果再结合一些模运算的性质来考虑，比如，对多个数字的相加再求模和先对中间部分结果求模再相加之后 求模的结果是一样的。那么，我们可以得出一个通用的求模运算的方法：Java代码旦1.public static long sum(intarray, int base, int p)2. 3.4.5.6.7.&9.long sum = 0;for(int i = 1; i array.length; i+)sumsumsum * base + arrayi;%= p；return sum;10. 这里,base表示数的进制，可以是10以外的其他进制。总结:前面针对大整数的两种情况进行了讨论，一种
8、是给定一个整数，然后有一个比较大的指数，这种情况下 需要考虑将指数变小给降下来。这里要利用到模运算里底数可以结合的特性。而针对一个很长的整数，我们可 以将他转换成多项式求和的形式。这里就利用了多个数字求和取模和部分结果先取模再求和取模的结果一致这 个特性。问题本身不是很复杂，主要是要把这几种特性想清楚，给用好了。总的来看，确实有点绕。补充证明:我们先来证明如下的等式成立：(X ) modP X(y mod P) modP = (X rnodP) (Y modP) modP因为X, Y都要对P求模，而实际上X, Y都可以表示成X = A*P + B的形式，其中B就是X mod P的结果。 那么前
9、面的A*P这部分则是对于P可整除的。(X * Y) = (A * P + B * Y = A * P * Y + B * Y 如果对这个等式的右边求模的话，显然A*P*Y这一部分是P的倍数，求模后的结果为0，则结果为(B * Y) mod P，前面我们知道B = X mod P。这样我们就证明了 (X * Y) mod P = X(Y mod P) mode P后面这部分的证明 可以类似推导出来。我们再证明下面的等式成立：XN modF二(X modP)N mod P按照前面一部分的讨论，我们可以假设X = A * P + B那么原来的等式则转化为：XN mod在右边的等式中，如果我们按照二项式定理将它展开，那么他们将成为很多项乘积的和。但是所有和A*P 相乘的项都可以被P整除，那么这些项的结果最终都是0，只有不含有A*P的项对最后的结果有效。展开后唯 一有效的部分就是BN。而B本身就是X mod P。那么我们也就证明了上面等式的成立。参考材料:data structures and problem solving using java
