博弈问题等高精度计算pp文稿

1、高精度计算与游戏策略问题目 录：一、高精度计算的若干问题1. 高精度乘法与分治算法2. 牛顿迭代法3. 高精度除法4. 高精度开方5. 值计算二、游戏策略问题1. 取奇数游戏2. 取石子游戏3. 称球游戏（略）4. 造币厂问题1. 高精度乘法与分治算法 高精度计算的核心运算是高精度乘法。加减法的计算复杂度是O(n) 阶的，不会有阶上的改进，除法、开方等运算可转换为乘法。 两个高精度数的乘法一般是O(n2) 阶的，采用快速Fourier变换(FFT)或快速数论变换(FNT)可降至O(n*logn) 阶,其算法较复杂。这里介绍一种分治算法，可将计算复杂度降至O(n1.58) 阶。设 A, B 是两

2、个 N(N=2n) 位数，且A=a110N/2+a2 , B=b110N/2+b2则：AB=(a110N/2+a2 )(b110N/2+b2) =a1b110N+(a1b2+a2 b1)10N/2+a2b2 =p10N+(r p q)10N/2+q其中，p=a1b1, q=a2b2, r=(a1+a2 )(b1+b2)这样，计算两个N位数的乘法 AB，可转换为计算个N/2位数的乘法(p, q, r)。设Tn为 N=2n 时所做的位乘法的次数，则 Tn =3Tn-1 =32Tn-2 = 3nT0 =3n,由于N=2n，n=log2N, Tn=3logN=Nlog3 N1.58 当N很大时，其效果

3、还是很明显的。具体处理见附录。 2. 牛顿迭代法给定方程: f(x)=0, 已知 x0 是方程的一个近似根，f(x)是 f(x)的导函数,如果f(x)是多项式：f(x) = anxn + an-1xn-1 + a1x + a0, 则f(x) = nanxn-1 + (n-1)an-1xn-2 + a2x + a0 求该方程的更精确的根的牛顿迭代公式是: 牛顿迭代公式在方程求根和高精度计算中具有重要的应用, 当f(xn)不为零时，对于适当的初值x0，牛顿迭代公式收敛，且具有二阶的收敛速度。即，如果设准确根为,则误差 |xn+1-| C|xn-|2 , 或者说，如果xn有k位有效数字，则xn+1有

4、2k位有效数字。设x=1/b, b是高精度数, 取f(x) = bx2-x = 0, f(x) = 2bx-11, 利用牛顿迭代公式，可得计算x的迭代公式为: xn+1=xn-( bxn-xn)=xn(2- bxn)说明： 1. 若a,b都是高精度数,则a/b=a*(1/b),先按上述公式求出 1/b, 再计算 a*(1/b)。 如果b不是高精度数,可归纳出有关算法，直接相除，不宜先计算 1/b。3. 高精度除法 2. 牛顿法对收敛条件要求较高，建议事先乘以适当的因子, 使b满足：0.1=b1。收敛结束的条件为|xn+1-xn| 10-N，其中N为要计算的位数。 假定 b,xn 等均用长度为N

5、+1的一维数组存放，b0存放b的整数部分，bN存放最后一位小数， xn+1，xn类似，为容纳舍入误差的积累，将数组体积延长到N+k,（例如，k=210)。为检验|xn+1-xn| 10-N，只需对数组xn+1，xn的第 N-r 至第 N 位进行检验。(r：20-100)。 3. 利用牛顿法二阶收敛的特性，可大致确定迭代次数，设初值 x0 有 r 位有效数字，迭代 k 次后，xk应有 r*2k 位有效数字。对于N位数，k可取为log2(N/r), 迭代k次后, 再检验条件|xn+1-xn| 10-N。 在最初的几次迭代中，乘法不一定算满k位。为此可编制一个计算A(M)*B(N)=C(L)的子程序

6、，要求 M=N=L 即可。 参考程序4 . 高精度开方设x=1/ ，b 是高精度数,取f(x) = bx3-x = 0, f(x) = 3bx2-12, 利用牛顿迭代公式，可得计算x的迭代公式为: xn+1 = xn-( bxn2-xn)/2 = xn(3- bxn2)*0.5于是，b=b*(1/b)=b*x 附注：以上两个公式摘自D.H.Bailey 1988年的一篇论文( p.,Vol.50),该论文介绍了作者将计算到29,360,000位小数的相关问题.5. 值计算 这个数渗透了整个数学！ -陈省身值计算的世界纪录：日本东京大学教授 金田康正(Kanada)2002年11月16日计算出圆

7、周率小数点后12411亿位数(上次的纪录是他在1999年9月创造的，为2061亿位数）。 值计算公式1. Machin公式 参看附录1值计算公式（2）下面两个著名公式不能用于 的高精度计算：二、游戏策略问题1.取奇数游戏游戏规则: 操作者先输入一个奇数 N(Ti ，可在第i 堆中取xi-Ti 颗，使对方永远处于T=0的平衡状态，计算机必胜.4. 造币厂问题艾波西蒙(ApSimon)于1984年在他所写的一本书中,介绍了下面的造币厂问题: n 个造币厂生产同一种硬币, 但其中某些厂由于材料问题造出了非标准的硬币.设标准的硬币重c克(已知),非标准的硬币只有一种重量,重c(1+e)克,其中e是个不为0的未知数,可以取正数或负数. 为了查出哪些厂生产的硬币是非标准的,从各厂中抽出一些样品(个数不限)放在一起进行称重,只能称2次.设ai,bi(i=1,.,n)分别为第一次,第二次称重从第i个厂中取得的样品个数.每个厂提供的样品或者都是标准的,或者都是非标准的.设pn=max(ai,bi)为某一称重方案的样品总数,求一种使pn最小的称重方案. 其中表示对于i从1到n求和,即i=1,n(以下同).4. 造币厂问题（2）4. 造币厂问题（3）对于上述问题,艾波西蒙提出了下面的猜想: A.1 是否对每一个n,均有min(pn)2