Press, Teukolsly, Vetterling, Flannery - Numerical Recipes in C, страница 4

You will receive by return mail a license authorizing you to makecopies of the programs for use by your students, and/or to transfer the programs toa machine accessible to your students (but only for the duration of the course).About Copyrights on Computer ProgramsLike artistic or literary compositions, computer programs are protected bycopyright. Generally it is an infringement for you to copy into your computer aprogram from a copyrighted source. (It is also not a friendly thing to do, since itdeprives the program’s author of compensation for his or her creative effort.) UnderxviiiLicense Informationcopyright law, all “derivative works” (modified versions, or translations into anothercomputer language) also come under the same copyright as the original work.Copyright does not protect ideas, but only the expression of those ideas ina particular form.

In the case of a computer program, the ideas consist of theprogram’s methodology and algorithm, including the necessary sequence of stepsadopted by the programmer. The expression of those ideas is the program sourcecode (particularly any arbitrary or stylistic choices embodied in it), its derived objectcode, and any other derivative works.If you analyze the ideas contained in a program, and then express thoseideas in your own completely different implementation, then that new programimplementation belongs to you. That is what we have done for those programs inthis book that are not entirely of our own devising.

When programs in this book aresaid to be “based” on programs published in copyright sources, we mean that theideas are the same. The expression of these ideas as source code is our own. Webelieve that no material in this book infringes on an existing copyright.TrademarksSeveral registered trademarks appear within the text of this book: Sun is atrademark of Sun Microsystems, Inc. SPARC and SPARCstation are trademarks ofSPARC International, Inc. Microsoft, Windows 95, Windows NT, PowerStation,and MS are trademarks of Microsoft Corporation. DEC, VMS, Alpha AXP, andULTRIX are trademarks of Digital Equipment Corporation. IBM is a trademark ofInternational Business Machines Corporation.

Apple and Macintosh are trademarksof Apple Computer, Inc. UNIX is a trademark licensed exclusively through X/OpenCo. Ltd. IMSL is a trademark of Visual Numerics, Inc. NAG refers to proprietarycomputer software of Numerical Algorithms Group (USA) Inc. PostScript andAdobe Illustrator are trademarks of Adobe Systems Incorporated. Last, and no doubtleast, Numerical Recipes (when identifying products) is a trademark of NumericalRecipes Software.AttributionsThe fact that ideas are legally “free as air” in no way supersedes the ethicalrequirement that ideas be credited to their known originators.

When programs inthis book are based on known sources, whether copyrighted or in the public domain,published or “handed-down,” we have attempted to give proper attribution. Unfortunately, the lineage of many programs in common circulation is often unclear. Wewould be grateful to readers for new or corrected information regarding attributions,which we will attempt to incorporate in subsequent printings.Computer Programsby Chapter and Section1.01.11.11.1flmoonjuldaybadlukcaldatcalculate phases of the moon by dateJulian Day number from calendar dateFriday the 13th when the moon is fullcalendar date from Julian day number2.1gaussj2.32.32.42.42.42.42.52.62.62.62.72.72.72.72.72.72.72.72.72.72.72.82.82.92.92.102.102.102.102.10ludcmplubksbtridagbanmulbandecbanbksmprovesvbksbsvdcmppythagcyclicsprsinsprsaxsprstxsprstpsprspmsprstmlinbcgsnrmatimesasolvevandertoeplzcholdccholslqrdcmpqrsolvrsolvqrupdtrotateGauss-Jordan matrix inversion and linear equationsolutionlinear equation solution, LU decompositionlinear equation solution, backsubstitutionsolution of tridiagonal systemsmultiply vector by band diagonal matrixband diagonal systems, decompositionband diagonal systems, backsubstitutionlinear equation solution, iterative improvementsingular value backsubstitutionsingular value decomposition of a matrixcalculate (a2 + b2 )1/2 without overflowsolution of cyclic tridiagonal systemsconvert matrix to sparse formatproduct of sparse matrix and vectorproduct of transpose sparse matrix and vectortranspose of sparse matrixpattern multiply two sparse matricesthreshold multiply two sparse matricesbiconjugate gradient solution of sparse systemsused by linbcg for vector normused by linbcg for sparse multiplicationused by linbcg for preconditionersolve Vandermonde systemssolve Toeplitz systemsCholesky decompositionCholesky backsubstitutionQR decompositionQR backsubstitutionright triangular backsubstitutionupdate a QR decompositionJacobi rotation used by qrupdt3.13.23.33.33.4polintratintsplinesplintlocatepolynomial interpolationrational function interpolationconstruct a cubic splinecubic spline interpolationsearch an ordered table by bisectionxixxxComputer Programs by Chapter and Section3.43.53.53.63.63.63.63.6huntpolcoepolcofpolin2bcucofbcuintsplie2splin2search a table when calls are correlatedpolynomial coefficients from table of valuespolynomial coefficients from table of valuestwo-dimensional polynomial interpolationconstruct two-dimensional bicubictwo-dimensional bicubic interpolationconstruct two-dimensional splinetwo-dimensional spline interpolation4.24.24.24.34.44.44.44.44.44.44.54.54.54.54.54.54.54.6trapzdqtrapqsimpqrombmidpntqromomidinfmidsqlmidsqumidexpqgausgauleggaulaggauhergaujacgaucoforthogquad3dtrapezoidal ruleintegrate using trapezoidal ruleintegrate using Simpson’s ruleintegrate using Romberg adaptive methodextended midpoint ruleintegrate using open Romberg adaptive methodintegrate a function on a semi-infinite intervalintegrate a function with lower square-root singularityintegrate a function with upper square-root singularityintegrate a function that decreases exponentiallyintegrate a function by Gaussian quadraturesGauss-Legendre weights and abscissasGauss-Laguerre weights and abscissasGauss-Hermite weights and abscissasGauss-Jacobi weights and abscissasquadrature weights from orthogonal polynomialsconstruct nonclassical orthogonal polynomialsintegrate a function over a three-dimensional space5.15.35.35.35.75.85.85.95.95.105.105.115.125.13eulsumddpolypoldivratvaldfridrchebftchebevchderchintchebpcpcshftpcchebpaderatlsqsum a series by Euler–van Wijngaarden algorithmevaluate a polynomial and its derivativesdivide one polynomial by anotherevaluate a rational functionnumerical derivative by Ridders’ methodfit a Chebyshev polynomial to a functionChebyshev polynomial evaluationderivative of a function already Chebyshev fittedintegrate a function already Chebyshev fittedpolynomial coefficients from a Chebyshev fitpolynomial coefficients of a shifted polynomialinverse of chebpc; use to economize power seriesPadé approximant from power series coefficientsrational fit by least-squares method6.16.16.16.1gammlnfactrlbicofactlnlogarithm of gamma functionfactorial functionbinomial coefficients functionlogarithm of factorial functionComputer Programs by Chapter and Sectionxxi6.16.26.26.26.26.26.26.26.36.36.46.46.56.56.56.56.56.56.66.66.66.66.66.66.76.76.76.76.76.86.96.96.106.116.116.116.116.116.116.116.116.126.126.12betagammpgammqgsergcferfferffcerfccexpinteibetaibetacfbessj0bessy0bessj1bessy1bessybessjbessi0bessk0bessi1bessk1besskbessibessjybeschbbessikairysphbesplgndrfrenelcisidawsonrfrdrjrcellfelleellpisncndnhypgeohypserhypdrvbeta functionincomplete gamma functioncomplement of incomplete gamma functionseries used by gammp and gammqcontinued fraction used by gammp and gammqerror functioncomplementary error functioncomplementary error function, concise routineexponential integral Enexponential integral Eiincomplete beta functioncontinued fraction used by betaiBessel function J0Bessel function Y0Bessel function J1Bessel function Y1Bessel function Y of general integer orderBessel function J of general integer ordermodified Bessel function I0modified Bessel function K0modified Bessel function I1modified Bessel function K1modified Bessel function K of integer ordermodified Bessel function I of integer orderBessel functions of fractional orderChebyshev expansion used by bessjymodified Bessel functions of fractional orderAiry functionsspherical Bessel functions jn and ynLegendre polynomials, associated (spherical harmonics)Fresnel integrals S(x) and C(x)cosine and sine integrals Ci and SiDawson’s integralCarlson’s elliptic integral of the first kindCarlson’s elliptic integral of the second kindCarlson’s elliptic integral of the third kindCarlson’s degenerate elliptic integralLegendre elliptic integral of the first kindLegendre elliptic integral of the second kindLegendre elliptic integral of the third kindJacobian elliptic functionscomplex hypergeometric functioncomplex hypergeometric function, series evaluationcomplex hypergeometric function, derivative of7.17.1ran0ran1random deviate by Park and Miller minimal standardrandom deviate, minimal standard plus shufflexxiiComputer Programs by Chapter and Section7.17.17.27.27.37.37.37.47.47.57.57.77.87.87.87.8ran2ran3expdevgasdevgamdevpoidevbnldevirbit1irbit2psdesran4sobseqvegasrebinmiserranptrandom deviate by L’Ecuyer long period plus shufflerandom deviate by Knuth subtractive methodexponential random deviatesnormally distributed random deviatesgamma-law distribution random deviatesPoisson distributed random deviatesbinomial distributed random deviatesrandom bit sequencerandom bit sequence“pseudo-DES” hashing of 64 bitsrandom deviates from DES-like hashingSobol’s quasi-random sequenceadaptive multidimensional Monte Carlo integrationsample rebinning used by vegasrecursive multidimensional Monte Carlo integrationget random point, used by miser8.18.18.18.28.28.38.48.48.48.58.58.58.68.6piksrtpiksr2shellsortsort2hpsortindexxsort3rankselectseliphpseleclasseclazzsort an array by straight insertionsort two arrays by straight insertionsort an array by Shell’s methodsort an array by quicksort methodsort two arrays by quicksort methodsort an array by heapsort methodconstruct an index for an arraysort, use an index to sort 3 or more arraysconstruct a rank table for an arrayfind the N th largest in an arrayfind the N th largest, without altering an arrayfind M largest values, without altering an arraydetermine equivalence classes from listdetermine equivalence classes from procedure9.09.19.19.19.29.29.29.39.49.49.59.5scrshozbraczbrakrtbisrtflsprtseczriddrzbrentrtnewtrtsafelaguerzroots9.59.5zrhqrqrootgraph a function to search for rootsoutward search for brackets on rootsinward search for brackets on rootsfind root of a function by bisectionfind root of a function by false-positionfind root of a function by secant methodfind root of a function by Ridders’ methodfind root of a function by Brent’s methodfind root of a function by Newton-Raphsonfind root of a function by Newton-Raphson and bisectionfind a root of a polynomial by Laguerre’s methodroots of a polynomial by Laguerre’s method withdeflationroots of a polynomial by eigenvalue methodscomplex or double root of a polynomial, BairstowComputer Programs by Chapter and Sectionxxiii9.69.79.79.79.79.7mnewtlnsrchnewtfdjacfminbroydnNewton’s method for systems of equationssearch along a line, used by newtglobally convergent multi-dimensional Newton’s methodfinite-difference Jacobian, used by newtnorm of a vector function, used by newtsecant method for systems of equations10.110.110.210.310.410.410.510.510.510.610.610.610.710.810.810.810.810.910.910.910.910.910.910.910.9mnbrakgoldenbrentdbrentamoebaamotrypowelllinminf1dimfrprmndlinmindf1dimdfpminsimplxsimp1simp2simp3annealrevcstreversetrncsttrnsptmetropamebsaamotsabracket the minimum of a functionfind minimum of a function by golden section searchfind minimum of a function by Brent’s methodfind minimum of a function using derivative informationminimize in N -dimensions by downhill simplex methodevaluate a trial point, used by amoebaminimize in N -dimensions by Powell’s methodminimum of a function along a ray in N -dimensionsfunction used by linminminimize in N -dimensions by conjugate gradientminimum of a function along a ray using derivativesfunction used by dlinminminimize in N -dimensions by variable metric methodlinear programming maximization of a linear functionlinear programming, used by simplxlinear programming, used by simplxlinear programming, used by simplxtraveling salesman problem by simulated annealingcost of a reversal, used by annealdo a reversal, used by annealcost of a transposition, used by annealdo a transposition, used by annealMetropolis algorithm, used by annealsimulated annealing in continuous spacesevaluate a trial point, used by amebsa11.111.111.211.311.511.511.6jacobieigsrttred2tqlibalancelmheshqreigenvalues and eigenvectors of a symmetric matrixeigenvectors, sorts into order by eigenvalueHouseholder reduction of a real, symmetric matrixeigensolution of a symmetric tridiagonal matrixbalance a nonsymmetric matrixreduce a general matrix to Hessenberg formeigenvalues of a Hessenberg matrix12.212.312.312.312.312.3four1twofftrealftsinftcosft1cosft2fast Fourier transform (FFT) in one dimensionfast Fourier transform of two real functionsfast Fourier transform of a single real functionfast sine transformfast cosine transform with endpoints“staggered” fast cosine transformxxivComputer Programs by Chapter and Section12.412.512.612.6fournrlft3fourfsfourewfast Fourier transform in multidimensionsFFT of real data in two or three dimensionsFFT for huge data sets on external mediarewind and permute files, used by fourfs13.113.213.413.613.613.613.713.813.813.813.913.913.1013.1013.1013.1013.10convlvcorrelspctrmmemcoffixrtspredicevlmemperiodfasperspreaddftcordftintwt1daub4pwtsetpwtwtnconvolution or deconvolution of data using FFTcorrelation or autocorrelation of data using FFTpower spectrum estimation using FFTevaluate maximum entropy (MEM) coefficientsreflect roots of a polynomial into unit circlelinear prediction using MEM coefficientspower spectral estimation from MEM coefficientspower spectrum of unevenly sampled datapower spectrum of unevenly sampled larger data setsextirpolate value into array, used by faspercompute endpoint corrections for Fourier integralshigh-accuracy Fourier integralsone-dimensional discrete wavelet transformDaubechies 4-coefficient wavelet filterinitialize coefficients for pwtpartial wavelet transformmultidimensional discrete wavelet transform14.114.214.214.214.214.214.314.314.314.314.314.414.414.514.614.614.614.614.714.714.714.714.8momentttestavevartutesttptestftestchsonechstwoksonekstwoprobkscntab1cntab2pearsnspearcrankkendl1kendl2ks2d1squadctquadvlks2d2ssavgolcalculate moments of a data setStudent’s t-test for difference of meanscalculate mean and variance of a data setStudent’s t-test for means, case of unequal variancesStudent’s t-test for means, case of paired dataF -test for difference of varianceschi-square test for difference between data and modelchi-square test for difference between two data setsKolmogorov-Smirnov test of data against modelKolmogorov-Smirnov test between two data setsKolmogorov-Smirnov probability functioncontingency table analysis using chi-squarecontingency table analysis using entropy measurePearson’s correlation between two data setsSpearman’s rank correlation between two data setsreplaces array elements by their rankcorrelation between two data sets, Kendall’s taucontingency table analysis using Kendall’s tauK–S test in two dimensions, data vs.