高精度hash多精度数值的处理

1、多精度数值的处理朱全民Free pascal中整数类型Shortint : -128.127 SmallInt (Integer) :-32768 . 32767 ,2B Longint:-2147483648 . 2147483647,4B Int64 : - 8 . 7 , 8BByte : 0.255, 1BWord : 0.65535, 2BCardinal (Longword) : 0. ,4BQWord: 0 . 15 ,8BBoolean (ByteBool) : false . true ,1Bwordbool: false . true , 2BLongBool : fals

2、e . true , 4BChar : 0.255,1B多精度数值处理需解决的问题1.数据存储用数组或字符串2.计算结果位数确定用数学方法确定。利用对数函数（log）。3.进位与借位处理加法：if ai10 then begin ai=ai-10 ； ai+1=ai+1+1减法：if ai10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;因此，算法描述如下：procedure add(a,b;var c); a,b,c都为数组，a存储被加数，b存储加数，c存储结果 var i,x:integer;begin i:=1 while (i0) or(i

3、=b数组的长度) do begin x := ai + bi + x div 10; 第i位相加并加上次的进位 ci := x mod 10; 存储第i位的值 i := i + 1 位置指针变量 endend;多精度数值相减类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式if aibi then begin ai+1:=ai+1-1;ai:=ai+10 endci:=ai-bi因此，算法描述如下：procedure minu (a,b;var c); a,b,c都为数组，c存储结果 var i,x:integer;Begi

4、n 处理被减数和减数, a存储被加数，b存储加数 i:=1 while (i0) or(i1) do dec(lenc);多精度数值相除1. 多精度数值除以单精度数值,采取逐位上商的方法,得到余数*10+取数,继续循环. x:=0; for i:=1 to lena do begin ci:=(x*10+ai) div b; x:=(x*10+ai) mod b; end;2. 多精度数值除以多精度数值,采取循环相减的方法,得到余数部分添加取数,继续循环.多精度数值运算所需要注意的地方在做两个多精度数运算时候，存储多精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整

5、型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数. 在做运算时,要先进行化简,然后才进行运算,要将加法次数和乘法次数降到最低.示例：123456789 45 = 1 2345 6789 45 = 274 3484 1 div 45 = 0 ， 1 mod 45=1 取12345 div 45 = 274 12345 mod 45 = 15 取156789 div 45 = 3484 答案为2743484, 余数为156789 mod 45 = 9每个小整数段保留尽量多的位一个例子：计算两个15位数的和方法一分为15个小整数段，每段都是1位数，需要15次1位数加法方法二分为5

6、个小整数段，每段都是3位数，需要5次3位数加法方法三int64类型可以直接处理15位的整数，故1次加法就可以了比较用Integer计算1位数的加法和3位数的加法是一样快的故方法二比方法一效率高虽然对int64的操作要比Integer稍慢，但加法次数却大大减少实践证明，方法三比方法二更快使用int64类型高精度运算中，每个小整数段可以用int64类型表示int64有效数位为1920位求两个高精度数的和，每个整数段可以保留17位求高精度数与不超过m位整数的积，每个整数段可以保留18m位求两个高精度数的积，每个整数段可以保留9位 如果每个小整数段保留k位十进制数，实际上可以认为其只保存了1位10k进

7、制数，简称为高进制数 ，称1位高进制数为单精度数实例:求N!N!=N*(N-1)! =1*2*3*N该题当N较大时,显然要采用多精度数值进行处理,每次处理需要在原来的基础上做一次多精度数乘以单精度数。可以采用数组存放当前的数值即i！，下次用i+1乘以i！算法的优化高精度乘法的复杂度分析连乘的复杂度分析设置缓存分解质因数求阶乘二分法求乘幂分解质因数后的调整高精度乘法的复杂度分析计算n位高进制数与m位高进制数的积需要n*m次乘法积可能是n+m1或n+m位高进制数 Back连乘的复杂度分析（1）一个例子：计算5*6*7*8方法一：顺序连乘5*6=30，1*1=1次乘法30*7=210，2*1=2次乘

8、法210*8=1680，3*1=3次乘法方法二：非顺序连乘5*6=30，1*1=1次乘法7*8=56，1*1= 1次乘法30*56=1680，2*2=4次乘法 共6次乘法共6次乘法特点：n位数*m位数=n+m位数连乘的复杂度分析（2）若“n位数*m位数=n+m位数”，则n个单精度数，无论以何种顺序相乘，乘法次数一定为n(n-1)/2次证明：设F(n)表示乘法次数，则F(1)=0，满足题设设kn时，F(k)=k(k-1)/2，现在计算F(n)设最后一次乘法计算为“k位数*(n-k)位数”，则F(n)=F(k)+F(n-k)+k (n-k)=n(n-1)/2（与k的选择无关）Back设置缓存（1）

9、一个例子：计算9*8*3*2方法一：顺序连乘9*8=72，1*1=1次乘法72*3=216，2*1=2次乘法216*2=432，3*1=3次乘法方法二：非顺序连乘9*8=72，1*1=1次乘法3*2=6，1*1=1次乘法72*6=432，2*1=2次乘法特点：n位数*m位数可能是n+m-1位数共6次乘法共4次乘法设置缓存（2）考虑k+t个单精度数相乘a1*a2*ak*ak+1*ak+t设a1*a2*ak结果为m位高进制数（假设已经算出）ak+1*ak+t结果为1位高进制数若顺序相乘，需要t次“m位数*1位数” ，共mt次乘法可以先计算ak+1*ak+t，再一起乘，只需要m+t次乘法在设置了缓存

10、的前提下，计算m个单精度数的积，如果结果为n位数，则乘法次数约为n(n1)/2次，与m关系不大设S=a1a2 am，S是n位高进制数可以把乘法的过程近似看做，先将这m个数分为n组，每组的积仍然是一个单精度数，最后计算后面这n个数的积。时间主要集中在求最后n个数的积上，这时基本上满足“n位数*m位数=n+m位数”，故乘法次数可近似的看做n(n-1)/2次设置缓存（3）缓存的大小设所选标准数据类型最大可以直接处理t位十进制数设缓存为k位十进制数，每个小整数段保存tk位十进制数设最后结果为n位十进制数，则乘法次数约为k/(nk) (i=1.n/k)i=(n+k)n/(2k(tk)，其中k远小于n要乘

11、法次数最少，只需k (tk)最大，这时k=t/2因此，缓存的大小与每个小整数段大小一样时，效率最高故在一般的连乘运算中，可以用int64作为基本整数类型，每个小整数段为9位十进制数，缓存也是9位十进制数Back分解质因数求阶乘例：10!=28*34*52*7n!分解质因数的复杂度远小于nlogn，可以忽略不计与普通算法相比，分解质因数后，虽然因子个数m变多了，但结果的位数n没有变，只要使用了缓存，乘法次数还是约为n(n-1)/2次因此，分解质因数不会变慢（这可以通过实践来证明）分解质因数之后，出现了大量求乘幂的运算，我们可以优化求乘幂的算法。这样，分解质因数的好处就体现出来了Back二分法求乘

12、幂二分法求乘幂，即：a2n+1=a2n*aa2n=(an)2其中，a是单精度数复杂度分析假定n位数与m位数的积是n+m位数设用二分法计算an需要F(n)次乘法F(2n)=F(n)+n2，F(1)=0设n=2k，则有F(n)=F(2k)=(i=0.k1)4i=(4k1)/3=(n21)/3与连乘的比较用连乘需要n(n-1)/2次乘法，二分法需要(n21)/3连乘比二分法耗时仅多50%采用二分法，复杂度没有从n2降到nlogn二分法求乘幂之优化平方算法怎样优化(a+b)2=a2+2ab+b2例：123452=1232*10000+452+2*123*45*100把一个n位数分为一个t位数和一个n-

13、t位数，再求平方怎样分设求n位数的平方需要F(n)次乘法F(n)=F(t)+F(n-t)+t(n-t)，F(1)=1用数学归纳法，可证明F(n)恒等于n(n+1)/2 所以，无论怎样分，效率都是一样将n位数分为一个1位数和n1位数，这样处理比较方便二分法求乘幂之复杂度分析复杂度分析前面已经求出F(n)=n(n+1)/2，下面换一个角度来处理S2=(0in)ai10i)2=(0in)ai2102i+2(0ijn)aiaj10i+j一共做了n+C(n,2)=n(n+1)/2次乘法运算普通算法需要n2次乘法，比改进后的慢1倍改进求乘幂的算法如果在用改进后的方法求平方，则用二分法求乘幂，需要(n+4)

14、(n1)/6次乘法，约是连乘算法n(n1)/2的三分之一Back分解质因数后的调整（1）为什么要调整计算S=211310，可以先算211，再算310，最后求它们的积也可以根据S=211310=610*2，先算610，再乘以 2即可两种算法的效率是不同的 分解质因数后的调整（2）什么时候调整计算S=ax+kbx=(ab)xak当kax+kbx时，选用(ab)xak，反之，则采用ax+kbx。axbxakax+kbx(bxak)(ax+1)0bxak这时kxlogabBack总结内容小结用int64作为每个小整数段的基本整数类型采用二进制优化算法高精度连乘时缓存和缓存的设置改进的求平方算法二分法求

15、乘幂分解质因数法求阶乘以及分解质因数后的调整应用高精度求乘幂（平方）高精度求连乘（阶乘）高精度求排列组合结束语求N!的高精度算法本身并不难，但我们仍然可以从多种角度对它进行优化。其实，很多经典算法都有优化的余地。我们自己编写的一些程序也不例外。只要用心去优化，说不准你就想出更好的算法来了。在此，以高精度算法为例，谈谈如何优化一个算法。我们想说明的只有一点：那就是算法是可以优化的。实例：求下列表达式的值给出下列表达式,对给定的N，求出后表达式结果的后k位数。其中：1n1000，1k100。输入：在输入文件中有二个整数，分别为N和K。输出：在输出文件中仅有一行,为上述表达式结果的后k位数。实例：i

16、nput.txt 3 2output.txt 12分析这道题是一道高精度计算题。由于直接计算原表达式比较复杂，很难在规定时间内出解，因此，在高精度计算前必须对公式进行化简。定理1 ：1*C(n,1)+2*C(n,2)+n*C(n,n)=n*2n-1。证明:设S=1*C(n,1)+2*C(n,2)+n*C(n,n)，逆序相加得2S=2*n*C(n,n)+1*C(n,1)+(n-1)*C(n,n-1)+2*C(n,2)+(n-2)*C(n,n-2) +(n-1)*C(n,n-1)+1*C(n,1)，C(n,k)=C(n,n-k),C(n,n)=1，2S=2*n+n*C(n,1)+n*C(n,2)+

17、n*C(n,n-1) =n*(2+C(n,1)+C(n,2)+C(n,n-1)，C(n,0)=C(n,n)=1，2=C(n,0)+C(n,n)，2S=n*(C(n,0)+C(n,1)+C(n,n-1)+C(n,n)=n*2n，S=n*2n-1。算法因此，本题实际上是计算n*2n-1的后k位数。为了提高效率，可使用二分法计算an，即以下递推关系式n=0an=1，n mod 2=1an=a*an-1，n0 and n mod 2=0an=(an div 2)2。算法描述Proc Power(a,n:Integer;var x:THigh); 计算x=anbegin if n=0 then x:=1

18、 else if n mod 2=1 then begin Power(a,n-1,x); MulX(x,a,x) end else if n mod 2=0 then begin Power(a,n div 2,x); Mul(x,x,x) endend;问题讨论一、高精度实数减法编程实现两个高精度实数减法，两数分别由键盘输入，均不超过240位。 输入数据均不需判错。二、高精度实数的除法编程求解两个高精度正实数的除法。要求精确至小数点后20后，若20位内有循环节，请标出。三、求精确计算：1n+2n+mn的后K位数，其中1=n=9999，1=m=9999，1=K=99。四、你能利用计算机搜索到最大的素数是多少? 给你一个很大的偶数,你能否验证一下歌德巴赫猜想？五、高精度开根你所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下你所负责的部分：实数的高精度开m次根。因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。你现在要做的只是这项工作的第一步：只对自然数进行开整数次根，求出它的一个非负根，并且不考虑结果的小数部分，只要求把结果截断取整即可。【任务描述】你的程序需要根据给定的输入，给出符