- 浏览: 1665637 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (335)
- uml (11)
- java (318)
- python (11)
- socket (2)
- ant (1)
- data structures (58)
- algorithms (67)
- concurrency (16)
- multithreading (16)
- mysql (2)
- ubuntu (2)
- c语言 (1)
- lucene (0)
- elasticsearch (0)
- django (1)
- 读书 观点 (2)
- 读书 (4)
- 观点 (4)
- collections (8)
- nio (1)
- io (2)
- 系统集成 (1)
- activemq (2)
- restful (0)
- web service (0)
- HttpClient (1)
- serializable (0)
- annotation (1)
- jdbc (3)
- classloader (0)
- regular expression (1)
- jpa (4)
- jvm (0)
- reflection (1)
- commons-pool2 (2)
- javamail (1)
- velocity (1)
- mathematics (3)
- graph (13)
- LeetCode (159)
- scala (0)
- spring (24)
- maven (5)
- spring batch (1)
- quartz (2)
- IOC (2)
- ORM (3)
- hibernate (2)
- aop (4)
- redis (0)
- zookeeper (0)
- spring mvc (4)
- ELK (1)
- string (1)
- gradle (1)
- mybatis (5)
- docker (0)
- servlet (0)
- log4j2 (1)
- html (0)
- css (0)
最新评论
-
nucleus:
貌似是因为图片的路径是http的缘故:http://dl2.i ...
spring container 实现分析:BeanWrapper -
nucleus:
nucleus 写道BeanWrapper这一块相关的类结构如 ...
spring container 实现分析:BeanWrapper -
nucleus:
BeanWrapper这一块相关的类结构如下图:文中提到的上述 ...
spring container 实现分析:BeanWrapper -
leshy:
inventory.sort(Comparator.compa ...
java8 lambda表达式学习总结 -
Leisurez:
di1984HIT 写道xuexile~hahaha~
activemq的几种基本通信方式总结
问题描述
最近在学习一些资料的时候正好看到一些和大整数求余数相关的问题,这些问题粗粗看来似乎有点麻烦。但是当结合一些有关数学的特性来分析时,会觉得很有意思。
问题1: 求一个整数X的N次方除以某个整数P的余数。用数学公式表示则如下:
其中N >= 0, P > 0.
这个问题需要考虑的就是如果N比较大的时候,很可能就超出我们所用一般数据类型所能表示的范围。如果直接去求X的N次方,就算有数据能保存的下来,肯定也会消耗大量的时间和空间。
问题2: 给定一个很大的数,求它除以某个整数P的余数。这个数因为足够大到没办法用普通的数据类型来表示,所以需要用一个整数类型的数组或字符串来保存。结果也是要求X mod P
问题1分析
最初分析
我们先来看第一个问题。这个问题假定X和P并不是太大,可以用一个计算机的常用数据类型来表示。一种最简单直白的方法就是我们直接将所有N个X相乘,然后再对被除数P相除,求余数。当然,这是基于一个前提,我们有能够保存足够大的数据类型。如果我们对这种思路的时间和空间复杂度做一个粗略的估计的话,会发现,假设X是int类型的整数,占4个字节,而最坏的情况就是每次相乘的结果就占用的结果增加4个字节,这样N次乘积就需要占用4N字节的空间。而如果算上每次相乘的中间结果,占用的空间就达到N*N的量级。再看时间复杂度,假定两个int类型的整数乘积的运算时间单位为1的话,在没有任何优化假定的前提下,一个32位整数和64位整数乘积的时间则为原来的两倍。如果以这个标准来分析的话,后面的时间复杂度也到了N*N量级。
第一步改进
可见,虽然前面这种办法虽然理论上可行,但是实际上时间和空间复杂度太大,不太合适。现在我们再来看看另外一种思路。因为问题的关键就是指数N比较大,如果能将指数能够降下来,将其转换成对等的表达式,则问题就好解决了。我们看前面求乘积的过程,假定是最简单的情况,N =2,则相当于求(X * X) mod D. 如果利用整数求余数的性质,我们发现他们满足下面的性质:
这个等式的证明可以参照相关的数学材料或者文章后面的补充证明部分。通过这个性质,至少我们可以发现,对于两个数的乘积求余数,我们可以先求一个数的余数,然后再将这个余数乘以另外一个数再求余数。这样就可以求出来两个数乘积的余数。那么,如果对于3个,4个甚至更多的数的乘积求余数呢?我们可以将这个等式扩展一下,对于3个数的乘积,我们可以先求出前面两个数乘积的余数,再和第三个数相乘求。依次类推,重复N次就可以求出N次方的结果。于是,基于这种思路,我们可以写出如下的代码:
public static long power(long x, long n, long p) { if(n == 0) return 1; long tmp = x % p; for(long i = 0; i < n - 1 ; i++) { tmp = (x * tmp) % p; } return tmp; }
这种方法和前面的思路比起来,有一个进步的地方,就是每次运算的时候都对中间结果求模运算,使得结果都在普通数据类型可以保存的范围内,这样不会需要额外的存储空间。而时间的复杂度主要取决于运算的指数,所以时间复杂度为o(N)。这样我们就找到了一个还不错的解决方法了。
再进一步考虑
前面的办法虽然是已经在一个o(N)的范围了,可是如果N很大的话,我们还是要做一个很大的循环运算。还有没有可能使得我们的方法更加有效率呢?我们求X的N次方,可以根据N的性质做如下的分析:
当N为偶数的情况下:
那么,就有如下的等式成立:
后面这一部分的等式成立是基于模运算的这么一个特性:
当N为奇数的情况下,则有:
那么,结合前面讨论的公式,对奇数情况下求模,则结果为如下等式:
综合前面的两种情况,我们可以发现,当N为偶数时,我们可以求X的平方再取模,如果是奇数的话则要再乘以X,然后取模。这样,一次运算下来,我们就将指数N折半了。按照这个过程,整个过程的时间复杂度可以降低到对数的级别上来。
根据讨论的递归关系,我们可以得出如下递归方式的代码:
public static long power(long x, long n, long p) { if(n == 0) return 1; long tmp = power((x * x) % p, n / 2, p); if(n % 2 != 0) tmp = (tmp * x) % p; return tmp; }
将递归版本转换成循环实现的方式的代码如下:
public static long loopPower(long x, long n, long p) { x %= p; long tmp = 0; while(n > 0) { tmp = (x * x) % p; if(n % 2 != 0) tmp = (tmp * x) % p; n /= 2; } return tmp; }
问题2分析
结合前面的情况,因为问题2中本身需要求模运算的数字比较特殊,不是用一个普通的数据类型来保存,而是用的整型数组或者字符串数组。在这种情况下,我们需要考虑的是利用一些模运算的特性,使得整个运算的过程拆分成可运算的各个小的步骤。在这里,我们先假设是10进制的数字,比如说一个int数组[1, 2, 3, 4, 5, 6],那么他们实际对应的这个数字应该是如下:
这就相当于转换成了一个多项式求和的问题。对于一个整型的数组表示的长数据,我们按照多项式方式求和的典型代码如下:
public static long sum(int[] array) { long sum = 0; for(int i = 1; i < array.length; i++) { sum = sum * 10 + array[i]; } return sum; }
如果再结合一些模运算的性质来考虑,比如,对多个数字的相加再求模和先对中间部分结果求模再相加之后求模的结果是一样的。那么,我们可以得出一个通用的求模运算的方法:
public static long sum(int[] array, int base, int p) { long sum = 0; for(int i = 1; i < array.length; i++) { sum = sum * base + array[i]; sum %= p; } return sum; }
这里,base表示数的进制,可以是10以外的其他进制。
总结:
前面针对大整数的两种情况进行了讨论,一种是给定一个整数,然后有一个比较大的指数,这种情况下需要考虑将指数变小给降下来。这里要利用到模运算里底数可以结合的特性。而针对一个很长的整数,我们可以将他转换成多项式求和的形式。这里就利用了多个数字求和取模和部分结果先取模再求和取模的结果一致这个特性。问题本身不是很复杂,主要是要把这几种特性想清楚,给用好了。总的来看,确实有点绕。
补充证明:
我们先来证明如下的等式成立:
因为X, Y都要对P求模,而实际上X, Y 都可以表示成 X = A*P + B 的形式,其中B就是X mod P的结果。那么前面的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)] mod P。后面这部分的证明可以类似推导出来。
我们再证明下面的等式成立:
按照前面一部分的讨论,我们可以假设X = A * P + B, 那么原来的等式则转化为:
在右边的等式中,如果我们按照二项式定理将它展开,那么他们将成为很多项乘积的和。但是所有和A*P相乘的项都可以被P整除,那么这些项的结果最终都是0,只有不含有A*P的项对最后的结果有效。展开后唯一有效的部分就是B^N。而B本身就是X mod P。那么我们也就证明了上面等式的成立。
参考材料:
data structures and problem solving using java
发表评论
-
spring源代码分析:aop的实现
2018-10-03 23:32 686简介 在之前的文章里我们讨论过一些程序构建Pro ... -
java annotation基础
2018-06-30 16:41 833简介 之前有一篇简短的文章讨论过annotati ... -
spring源代码分析:annotation支持的实现
2018-09-03 23:31 2454简介 在之前的文章里,我们讨论了spring I ... -
spring container 实现分析:BeanFactory and ApplicationContext
2018-06-02 18:29 1399简介 在之前的文章里,我们讨论过作为spring ... -
spring aop: ProxyFactory
2018-04-30 16:45 782简介 在之前的文 ... -
日志与log4j2的配置和应用总结
2018-02-15 15:47 12187简介 通常我们在日常的应用开发中,日志起到一个非 ... -
Java servlet学习总结
2018-01-02 21:14 0简介 应用系统架构的演化(从CS到BS) ... -
spring container 实现分析:BeanWrapper
2018-02-19 18:10 1853简介 在之前的一篇文章里, 我们基于《Exper ... -
spring propertyeditor
2017-10-26 09:17 0pro spring 5 chapter 4, page ... -
spring bean life cycle
2018-02-25 13:30 868简介 在使用spring bean的过程中,有一个 ... -
spring container的设计与实现分析
2017-10-08 21:31 2649简介 在之前的一 ... -
jdbc数据访问的封装和演化
2017-09-16 17:00 2593简介 在使用传统jdbc的方式来访问数据的时候, ... -
Boyer Moore算法分析总结
2017-03-31 18:42 3477简介 在之前的文章里,对于字符串的搜索算法,我曾 ... -
mybatis学习总结:mybatis和spring, spring boot的集成
2017-03-04 18:07 2458简介 在前面的讨论里已经提到了mybatis的各种配置 ... -
mybatis学习总结:annotation与xml结合示例
2017-02-25 21:09 3644简介 在之前的文章里讨论过mybatis纯xml或者 ... -
mybatis学习总结:对象关系映射的xml配置实现
2017-02-19 23:03 4003简介 在之前的文章里已经讨论过mybatis的基本配 ... -
mybatis学习总结:annotation示例改进
2017-01-24 09:06 3383简介 在前一篇文 ... -
mybatis学习总结:基础示例
2017-01-21 23:30 839简介 mybatis是一个比较流行的ORM框架, ... -
gradle学习总结
2016-12-18 21:01 4525简介 Java的自动化构建工具比较多,从最开始的an ... -
String sort的几种方法
2016-10-16 23:07 2109简介 在之前的一 ...
相关推荐
字符串可能的余数LeetCode-活动 整数到罗马数字代码和描述 将整数转换为罗马数字 我目前正在教 AP 计算机科学 A(我的第一年),我选择这个作业是因为我认为我的学生也可以编码。 我们刚刚了解了用户定义的类和 ...
题目:古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 1.程序分析: 兔子的规律为数列1,1,2,3,5,8,13,21.... ...
0102 使用DivMod函数返回两个操作数相除的商和余数 68 0103 使用Power函数返回底数的任何次幂 69 0104 使用Round函数将实数四舍五入为整数 69 0105 使用Sqr函数计算指定数的平方 70 0106 使用Mean函数计算...
二进制、八进制、十进制、十六进制之间转换 二进制、八进制、十进制、十六进制之间转换 一、 十进制与二进制之间的转换 (1) 十进制转换为二进制,分为整数部分和小数部分 整数部分 方法:除2取余法,即每次将整数...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
例1 求两个正整数m,n的最大公因子 算法1-1 欧几里得算法 输入:正整数m和n 输出:m和n的最大公因子 第一步:求余数。r m%n 第二步:判断r=0?,若是,终止(n为答案),否则,转第三步。 第三步:互换,m n,n r,返回第...
9.2输入两个整数,求它们相除的余数。用带参的宏来实现,编程序。 67 9.3 67 9.4给年份year定义一个宏,以判断该年份是否为闰年。 68 9.5请分析以下一组宏所定义的输出格式: 68 9.6请设计输出实数的格式。实数用...
10.3 在除数不是2的幂时求带符号除法及余数 183 10.3.1 除以3 183 10.3.2 除以5 184 10.3.3 除以7 185 10.4 除数大于等于2的带符号除法 185 10.4.1 算法 187 10.4.2 算法可行性证明 187 10.4.3 证明乘积正确...
(1)十进制整数转换为二进制整数(除基取余法) 十进制整数转换为二进制整数的规则是:除以基数(2)取余数,先得到的余数为低位,后得到的余数为高位。 具体的做法是:用2连续去除十进制整数,直到商等于0为止,...
任意输入最少2组除数和余数,中间用英文逗号隔开,组间也用英文逗号隔开,能求出符合条件的整数; 今后这种题用此工具就迎刃而解了。 (3)-验证哥德巴赫猜想, 输入大于4一个偶数,显示两个素数和,这就是1+1(1个素数...
(29)某公司在传输数据过程中为了安全要对数据进行加密,若传递的是四位的整数,对其进行加密的规则为:每位数字都加上5,然后用和除以10的余数代替该数字,再将第一位和第四位交换,第二位和第三位交换。...
它深入浅出地介绍了大量的算法及相关的数据结构,以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等),重点在于算法的分析和设计。对于每一个专题,作者都试图提供目前最新的研究成果及样例...
范例2-2 求长整型整数的绝对值 399 ∷相关函数:labs函数 2.1.2 求浮点数的绝对值 400 范例2-2 求浮点数的绝对值 400 ∷相关函数:fabs函数 2.1.4 求反余弦 400 范例2-4 求反余弦 400 ∷相关函数:acos函数 ...
范例2-2 求长整型整数的绝对值 399 ∷相关函数:labs函数 2.1.2 求浮点数的绝对值 400 范例2-2 求浮点数的绝对值 400 ∷相关函数:fabs函数 2.1.4 求反余弦 400 范例2-4 求反余弦 400 ∷相关函数:acos函数 ...
配书光盘Readme文件 C 语言通用范例开发金典 第1章 数据结构.... 1.1 数组和字符串 2 ...1.2.4 进制转换问题 61 ...范例2-2 求长整型整数的绝对值 399 ∷相关函数:labs函数 2.1.2 求浮点数的...
31.9 整数的因子分解 思考题 本章注记 第32章 字符串匹配 32.1 朴素字符串匹配算法 32.2 Rabin\Karp算法 32.3 利用有限自动机进行字符串匹配 32.4 Knuth?Morris?Pratt算法 思考题 本章注记 ...
“取余”,就是Python中的余数运算,最后输出结果为两数相除后的余数 编写代码 思路一 不妨设一个变量sum为0,然后利用for循环不断将符合“取余5结果为3的整数”的值与原sum的值相加重新赋值给新的变量sum。最后,
将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题。 解答:按除2取余法,得到的余数依次是1、0、1、1,则十进制数转化为二进制数为1101。 分析:由于最先得到的余数是转化结果的最低位,最后...
5.1.20 求整除余数 5.1.21 求自然对数 5.1.22 求以10为底的对数 5.1.23 求幂 5.2 字符串函数 5.2.1 计算字符串长度 5.2.2 字符串转换为小写 5.2.3 字符串转换为大写 5.2.4 截去字符串左侧空格 ...
5.1.20 求整除余数 5.1.21 求自然对数 5.1.22 求以10为底的对数 5.1.23 求幂 5.2 字符串函数 5.2.1 计算字符串长度 5.2.2 字符串转换为小写 5.2.3 字符串转换为大写 5.2.4 截去字符串左侧空格 ...