本书针对工程中常用的行之有效的算法而编写，其主要内容包括多项式的计算、复数运算、随机数的产生、矩阵特征值与特征向量的计算、线性代数方程组的求解、非线性方程与方程组的求解、插值与逼近、数值积分、常微分方程组的求解、数学变换与滤波、特殊函数的计算、排序和查找。书中所有的算法均用C语言描述，并存放在一张光盘上。本书可供广大科研人员、工程技术人员以及管理工作者阅读使用，也可作为高等院校师生的参考书。注意：GAP4.7/4.10.2软件计算矩阵乘法a*b和矩阵秩RankMat(a)的结果均是错误的。目录介绍第1章多项式的计算1.1一维多项式求值1.2一维多项式多组求值1.3二维多项式求值1.4复系数多项式求值1.5多项式相乘、线性卷积
gap>x:=Indeterminate(Integers);a:=2*x^2+x;;b:=x+3;;c:=a*b;PolynomialCoefficientsOfPolynomial(c,1);x_12*x_1^3+7*x_1^2+3*x_1[0,3,7,2]
功能:多项式的乘法格式:polymul(a,b)a=[210]a=[2.000000000000001.000000000000000.00000000000000]b=[13]b=[1.000000000000003.00000000000000]polymul(a,b)a=2*x^2+xb=x+3a*b=2*x^3+7*x^2+3*xans=[2.000000000000007.000000000000003.000000000000000.00000000000000]
1.6复系数多项式相乘1.7多项式相除1.8复系数多项式相除1.9一元多项式环Z[x]的带余除法
root@ubuntu:/home/cpptest#./zpoly1,2,3,41,2,1poly:1x^0+2x^1+3x^2+4x^3=[1,2,3,4]div:1x^0+2x^1+1x^2=[1,2,1]quot:-5x^0+4x^1=[-5,4]rem:6x^0+8x^1=[6,8]div*quot:-5x^0+-6x^1+3x^2+4x^3=[-5,-6,3,4]
a1=[4321]b=[121]polydiv(a1,b)a1=4*x^3+3*x^2+2*x+1b=x^2+2*x+1a1/b=4*x-5polymod(a1,b)a1=4*x^3+3*x^2+2*x+1b=x^2+2*x+1a1%b=8*x+6
1.10多项式环F_p[x]上的带余除法、因子分解、不可约多项式gap>n:=5;;R:=GF(n);;L:=Elements(R);R1:=PolynomialRing(R,1);;x:=Indeterminate(R);;poly:=x^2+1;;IsIrreducibleRingElement(R1,poly);Degree(poly);Factors(poly);
[0*Z(5),Z(5)^0,Z(5),Z(5)^2,Z(5)^3]false2[x_1+Z(5),x_1+Z(5)^3]gap>-Z(5);Z(5)^3gap>-Z(5)^3;Z(5)x^2+1=0在F_5中有两根：x_1=2,x_2=3
gap>LoadPackage("GUAVA");gap>fornin[2,3]doforqin[2..5]doPrint(q,"元域上",n,"次不可约多项式的个数：",IrreduciblePolynomialsNr(n,q),"\n");od;od;2元域上2次不可约多项式的个数：13元域上2次不可约多项式的个数：34元域上2次不可约多项式的个数：65元域上2次不可约多项式的个数：102元域上3次不可约多项式的个数：23元域上3次不可约多项式的个数：84元域上3次不可约多项式的个数：205元域上3次不可约多项式的个数：40
如果n(n>1)次方程f(x)=0在系数域F_q内没有解，则称f(x)在F_q[x]上不可约。方程，因式分解，解x^2+1=0，不可分解，无解x^2+2=0，(x+1)(x+2)，x=1,x=2x^2+x+1=0，(x+2)(x+2)，x=1x^2+x+2=0，不可分解，无解x^2+2x+1=0，(x+1)(x+1)，x=2x^2+2x+2=0，不可分解，无解F_3[x]中的6个2次多项式有3个是不可约的gap>IrreduciblePolynomialsNr(2,3);3F_2[x]中的6个2~3次多项式有3个是不可约的gap>IrreduciblePolynomialsNr(2,2);1gap>IrreduciblePolynomialsNr(3,2);2方程，因式分解，解x^3+1=0，在F_2中有一根：x_1=1x^3+x+1=0，在F_2中无根x^3+x^2+1=0，在F_2中无根x^3+x^2+x+1=0，在F_2中有一根：x_1=1x^2+1=0，在F_2中有一根：x_1=1x^2+x+1=0，在F_2中无根
1.11根据n次多项式f(x)构造特征为p的p^n阶多项式剩余类环F_p[x]/f(x)1.12根据本原n次单位根计算n次分圆多项式
gap>fornin[1..5]dob1:=(CF(n)=Rationals);b4:=(CF(n)=GaussianRationals);Print("b1=",b1,",b4=",b4,",");od;b1=true,b4=false,b1=true,b4=false,b1=false,b4=false,b1=false,b4=true,b1=false,b4=false,gap>fornin[1..5]dob1:=(CF(n)=Rationals);b4:=(CF(n)=GaussianRationals);Print("b1=",b1,",b4=",b4,"\n");od;b1=true,b4=falseb1=true,b4=falseb1=false,b4=falseb1=false,b4=trueb1=false,b4=falsegap>fornin[1..5]dof:=CyclotomicPolynomial(Rationals,n);b:=IsIrreducibleRingElement(f);r:=RootsOfPolynomial(CF(n),f);Print(n,"次分圆多项式：",f,",b=",b,",r=",r,"\n");od;1次分圆多项式：x_1-1,b=true,r=[1]2次分圆多项式：x_1+1,b=true,r=[-1]3次分圆多项式：x_1^2+x_1+1,b=true,r=[E(3),E(3)^2]4次分圆多项式：x_1^2+1,b=true,r=[E(4),-E(4)]5次分圆多项式：x_1^4+x_1^3+x_1^2+x_1+1,b=true,r=[E(5),E(5)^2,E(5)^3,E(5)^4]
1.13计算多项式的伽罗瓦群
第2章复数运算【C++标准库complex早已支持】2.1复数乘法_ocmul@40/_CMul@8复数相乘2.2复数除法_ocdiv@40复数相除CDiv复数相除'(4+8j)/(7+9j)=0.76923+0.1538j'(471+643j)/(9+11j)=56+3j2.3复数乘幂CCPow求复幂指数幂_CPow@12求实幂指数_opowr@28求实幂指数CPow((16+81j),3)=-310832+(-469233)j2.4复数的n次方根_ontrt@28复数求根2.5复数指数_ocexp@24求复幂指数的特殊情形e^z2.6复数对数_oclog@24求复数的对数CLn求自然对数2.7复数正弦_ocsin@24求复数的正弦2.8复数余弦_occos@24求复数的余弦2.9复数正切CCTan求正切CTan(0.25+0.25j)=0.2391+(-0.26j)2.10复数求模CAbs/_cabs/_CAbs@4复数求模
2.11复黎曼zeta函数2.12复伽马函数Γ(x+yi)2.13算术几何平均agm2.14勒让德第一类完全椭圆积分K2.15雅可比theta函数theta_11=JT1、theta_10=JT2、theta_00=JT3、theta_01=JT42.16复椭圆正弦sn、复椭圆余弦cn、复椭圆正切dn2.17魏尔斯特拉斯P、P'（花体）函数、不变量g_2,g_3、平稳值e_1,e_2,e_3
第3章随机数的产生3.1产生0到1之间均匀分布的一个随机数3.2产生0到1之间均匀分布的随机数序列3.3产生任意区间内均匀分布的一个随机整数3.4产生任意区间内均匀分布的随机整数序列3.5产生任意均值与方差的正态分布的一个随机数3.6产生任意均值与方差的正态分布的随机数序列第4章矩阵运算4.1实矩阵相乘算voidbrmul(doublea[],doubleb[],intm,intn,intk,double*c);//实矩阵相乘
功能:矩阵相乘格式:mul(a,b)a=[13-204-2-15-720841-53-32-41]a=[1.000000000000003.00000000000000-2.00000000000000.000000000000004.00000000000000-2.0000000000000-1.00000000000005.00000000000000-7.00000000000002.000000000000000.000000000000008.000000000000004.000000000000001.00000000000000-5.00000000000003.00000000000000-3.00000000000002.00000000000000-4.00000000000001.00000000000000]b=[45-12-2678103-598-6]b=[4.000000000000005.00000000000000-1.00000000000002.00000000000000-2.00000000000006.000000000000007.000000000000008.000000000000001.000000000000000.000000000000003.00000000000000-5.00000000000009.000000000000008.00000000000000-6.0000000000000]c=mul(a,b)c=[32.000000000000015.0000000000000-9.000000000000043.000000000000027.000000000000024.0000000000000-1.0000000000000-21.00000000000077.000000000000029.000000000000033.0000000000000-5.0000000000000]
4.2复矩阵相乘voidbcmul(doublear[],doubleai[],doublebr[],doublebi[],intm,intn,intk,doublecr[],doubleci[]);//复矩阵相乘4.3一般实矩阵求逆intbrinv(doublea[],intn);//实矩阵求逆的全选主元高斯约当法（Gauss-Jordan）
gap>a:=[[0.2368,0.2471,0.2568,1.2671],[1.1161,0.1254,0.1397,0.149],[0.1582,1.1675,0.1768,0.1871],[0.1968,0.2071,1.2168,0.2271]];;a^-1;a^-1=Inverse(a);[[-0.0859208,0.937944,-0.0684372,-0.0796077],[-0.10559,-0.0885243,0.905983,-0.0991908],[-0.127073,-0.111351,-0.116967,0.878425],[0.851606,-0.135456,-0.140183,-0.143807]]true
功能:方阵求逆,其采用的是LU分解算法格式:inv(a)//a为方阵变量a=[0.23680.24710.25681.26711.11610.12540.13970.1490.15821.16750.17680.18710.19680.20711.21680.2271]a=[0.236800000000000.247100000000000.256800000000001.267100000000001.116100000000000.125400000000000.139700000000000.149000000000000.158200000000001.167500000000000.176800000000000.187100000000000.196800000000000.207100000000001.216800000000000.22710000000000]b=inv(a)b=[-0.08592075047800.93794426823404-0.0684372042645-0.0796077151837-0.1055899132073-0.08852432350040.90598255638825-0.0991908105397-0.1270733117900-0.1113511370480-0.11696670648840.878425290943840.85160581464323-0.1354556628418-0.1401825503018-0.1438074804470]
4.4一般复矩阵求逆intbcinv(doublear[],doubleai[],intn);//复矩阵求逆的全选主元高斯约当法4.5对称正定矩阵的求逆intbssgj(doublea[],intn);//对称正定矩阵的求逆4.6托伯利兹矩阵求逆的特兰持方法intbtrch(doublet[],doublett[],intn,doubleb[]);//托伯利兹矩阵求逆的特兰持方法4.7求一般行列式的值doublebsdet(doublea[],intn);//求行列式值的全选主元高斯消去法
gap>a:=[[24.670817016005,97.0357947969045,89.6194347132088],[2.72601312153321,14.5667740211667,58.9581970399982],[6.19456609999508,60.2519491967987,8.23347480419719]];;DeterminantMat(a);DeterminantMatDestructive(a);-44785.9-44785.9
功能:求方阵行列式.此方法精度高,但运算的方阵的阶数最好不要超过5.
格式:Det(a)
说明:a为方阵
例子:
a=
[24.67081701600597.035794796904589.6194347132088
2.7260131215332114.566774021166758.9581970399982
6.1945660999950860.25194919679878.23347480419719]
执行命令
b=det(a)
后输出
b=
[-44785.8743735347]
4.8求矩阵的秩intbrank(doublea[],intm,intn);//求矩阵秩的全选主元高斯消去法4.9对称正定矩阵的乔里斯基分解与行列式求值intbchol(doublea[],intn,double*det);//对称正定矩阵的乔里斯基分解与行列式的求值4.10矩阵的三角分解intblluu(doublea[],intn,doublel[],doubleu[]);//矩阵的三角分解4.11一般实矩阵的QR分解intbmaqr(doublea[],intm,intn,doubleq[]);//一般实矩阵的QR分解4.12一般实矩阵的奇异值分解intbmuav(doublea[],intm,intn,doubleu[],doublev[],doubleeps,intka);//一般实矩阵的奇异值分解4.13求广义逆的奇异值分解法intbginv(doublea[],intm,intn,doubleaa[],doubleeps,doubleu[],doublev[],intka);//求广义逆的奇异值分解法解4.14有限域上的矩阵乘法、行列式、矩阵求逆gap>mat:=[[1,2,3],[0,5,6],[0,0,9]];;inv:=InverseMatMod(mat,17);mat*inv;
[[1,3,9],[0,7,1],[0,0,2]][[1,17,17],[0,35,17],[0,0,18]]GF(17)上的三阶方阵相乘例子：TheoriginMatrixisasfollows:123056009TheInverseMatrixisasfollows:139071002TheMultiplyMatrixisasfollows:100010001
第5章矩阵特征值与特征向量的计算
gap>m:=[[3,0],[1,-1]];;DeterminantMat(m);m^-1;Eigenvalues(Rationals,m);Eigenvectors(Rationals,m);-3[[1/3,0],[1/3,-1]][3,-1][[1,0],[1,-4]]
5.1约化对称矩阵为对称三对角阵的豪斯荷尔德变换法voidcstrq(doublea[],intn,doubleq[],doubleb[],doublec[]);//约化对称矩阵为对称三对角的豪斯荷尔德变换法5.2求对称三对角阵的全部特征值与特征向量intcsstq(intn,doubleb[],doublec[],doubleq[],doubleeps,intl);//实对称三对角阵的全部特征值与特征向量的计算5.3约化一般实矩阵为赫申伯格矩阵的初等相似变换法voidchhbg(doublea[],intn);//约化一般实矩阵为赫申伯格矩阵的初等相似变换法5.4求赫身伯格矩阵全部特征的QR方法intchhqr(doublea[],intn,doubleu[],doublev[],doubleeps,intjt);;//求赫申伯格矩阵全部特征值的QR方法5.5求实对称矩阵特征值与特征向量的雅可比法intcjcbi(doublea[],intn,doublev[],doubleeps,intjt);//求实对称矩阵特征值与特征向量的雅可比法，_cjcbi@24求实对称矩阵的特征值以及由特征向量作为列向量组成的矩阵V5.6求实对称矩阵特征值与特征向量的雅可比过关法voidcjcbj(doublea[],intn,doublev[],doubleeps);//求实对称矩阵特征值与特征向量的雅可比过关法第6章线性代数方程组的求解6.1求解实系数方程组的全选主元高斯消去法intagaus(doublea[],doubleb[],intn);//全选主元高斯消去法
功能:采用高斯消元法求解ax=b这类方程.格式:Gauss(a,b)注意:a是方阵,b是n*1的矩阵
a=[0.23680.24710.25681.26710.19680.20711.21680.22710.15811.16750.17680.18711.11610.12540.13970.1490]a=[0.236800000000000.247100000000000.256800000000001.267100000000000.196800000000000.207100000000001.216800000000000.227100000000000.158100000000001.167500000000000.176800000000000.187100000000001.116100000000000.125400000000000.139700000000000.14900000000000]b=[1.84711.74711.64711.5471]b=[1.847100000000001.747100000000001.647100000000001.54710000000000]x=gauss(a,b)x=[1.040576679419350.987050768392130.935040333933560.88128232948438]
_lgass@24计算正态分布函数lgass(0,1,-1)=0.1586553lgass(0,1,0)=0.5000000lgass(0,1,1)=0.8413447lgass(1,1,2)=0.8413447lgass(0,1,2)=0.9772499lgass(3,2,7)=0.9772499
14.10t-分布函数14.11χ-分布函数14.12F-分布函数14.13正弦积分_lsinn@8计算大写的正弦积分Si(x)，Si(0.00)=0.0000000，Si(1.00)=0.9460831，Si(1000.00)=1.5701391，14.14余弦积分_lcoss@8计算余弦积分
Ci(0.00)=-80.0132626,Ci(0.50)=-0.1777841,Ci(1.00)=0.3374039,Ci(1.50)=0.4703563,Ci(1000.00)=0.0008189
14.15指数积分
_lexpp@8计算指数积分Ei(0.00)=-22.4486353，Ei(0.50)=-0.5597736，Ei(1.00)=-0.2193839，Ei(1.50)=-0.1000196，Ei(1000.00)=0.0000123
14.16第一类椭圆积分_Arcsn@16实第一类勒让德椭圆积分14.17第二类椭圆积分
14.18实黎曼zeta函数14.19实雅可比椭圆函数sn,cn,dn14.20实椭圆双曲正弦snh、实椭圆双曲余弦cnh14.21实双纽线积分Arcsinlemn=Φ(x)=sinlemn^(-1)x、Φ'(x)=coslemn^(-1)x14.22实双纽线正弦sinlemn,实双纽线余弦coslemn数14.23克莱因不变模函数J(tau)
>jacobi(286,563)-1所以同余式x^2≡286(mod563)无解。gap>n:=438;;m:=593;;Legendre(n,m);Jacobi(n,m);-1-1gap>n:=286;;m:=563;;Legendre(n,m);Jacobi(n,m);-1-1gap>m:=11;;fornin[0..m]doi:=Legendre(n,m);j:=Jacobi(n,m);ifi=1andj=1thenPrint(n,",");fi;od;
1,3,4,5,9,
gap>m:=11;;fornin[0..m]doi:=Legendre(n,m);j:=Jacobi(n,m);ifi=-1orj=-1thenPrint(n,",");fi;od;
2,6,7,8,10,11的二次剩余是1,3,4,5,9，二次非剩余是2,6,7,8,10。
19.8F_p上开平方的算法模平方根问题：给出二次剩余方程y^2≡n(modp)中求出一个y的有效算法，其中(n/p)=1，在ECC应用中，p是大素数，y∈[0,p-1]范围内有且仅有两个解，枚举是无效的。
第20章纸牌算法20.1牛牛牌型的组合数无牛牌型的组合数：870920(15.0MBFiveCardListData_1.h)牛一牌型的组合数：171288(2.96MBFiveCardListData_3.h)牛二牌型的组合数：168072牛三牌型的组合数：172248牛四牌型的组合数：169608牛五牌型的组合数：181376牛六牌型的组合数：175328牛七牌型的组合数：189472牛八牌型的组合数：208520牛九牌型的组合数：260136(4.50MBFiveCardListData_11.h)牛牛牌型的组合数：578088(10.0MBFiveCardListData_14.h)银牛牌型的组合数：3824(70.9KBFiveCardListData_15.h)金牛牌型的组合数：1624(30.1KBFiveCardListData_16.h)炸弹牌型的组合数：8998(161KBFiveCardListData_17.h)五小牛牌型的组合数：3008(52.8KBFiveCardListData_18.h)——之前的计算的结果是五小牛牌型的组合数：446854中取5的组合数：3162510法20.2斗地主好牌
第21章加密算法21.1单向散列算法单向散列函数算法也称Hash算法，是一种将任意长度的消息压缩到某一固定长度（消息摘要）的函数（该过程不可逆）。Hash函数可用于数字签名、消息的完整性检测、消息起源的认证检测等。常见的散列算法有MD5、SHA、RIPE-MD、HAVAL、N-Hash等。Hash函数为不可逆算法。通用MD5加密算法
19492009->bdba84f269d342d3cc9be04078f9343c
非通用MD5加密算法
root@ubuntu:/home/cpptest#./md5Usage:md5arg1root@ubuntu:/home/cpptest#./md5123123->3a145908016a95728f769b5c2b43135c(长度:32)
root@ubuntu:/home/cpptest#./md51949200919492009->37312337953f059d3828c42fe2b17b11(长度:32)21.2异或加解密算法
root@ubuntu:/home/cpptest#./xor123123->0332a39197a4a2f155eb(长度:20)root@ubuntu:/home/cpptest#./xor-d0332a39197a4a2f155eb0332a39197a4a2f155eb->123(长度:3)root@ubuntu:/home/cpptest#./xor-e123123->0332a39197a4a2f155eb(长度:20)