C language algorithm quick reference manual complete source code

<> Source Code C Language Algorithm Quick Reference Manual Contents Chapter 1 Introduction 1 1.1 Overview of Programming Languages ​​1 1.1.1 Machine Language 1 1.1.2 Assembly Language 2 1.1.3 High-Level Language 2 1.1.4 C Language 3 1.2 Advantages and Disadvantages of C Language 4 1.2.1 Advantages of C Language 4 1.2.2 Disadvantages of C Language 6 1.3 Algorithm Overview 7 1.3.1 Basic Characteristics of Algorithms 7 1.3.2 Complexity of Algorithms 8 1.3.3 Accuracy of Algorithms 10 1.3.4 Stability of Algorithms 14 Chapter 2 Complex Number Operations 18 2.1 Four Arithmetic Operations of Complex Numbers 18 2.1.1 [Algorithm 1] Complex Number Multiplication 18 2.1.2 [Algorithm 2] Complex Number Division 20 2.1.3 [Example 5] Four Arithmetic Operations of Complex Numbers 22 2.2.1 [Algorithm 3] Complex power 23 2.2.2 [Algorithm 4] Complex root 25 2.2.3 [Algorithm 5] Complex exponent 27 2.2.4 [Algorithm 6] Complex logarithm 29 2.2.5 [Algorithm 7] Complex sine 30 2.2.6 [Algorithm 8] Complex cosine 32 2.2.7 [Example 6] Complex function operations 34 Chapter 3 Polynomial calculations 37 3.1 Polynomial representation 37 3.1.1 Coefficient representation 37 3.1.2 Dot representation 38 3.1.3 [Algorithm 9] Conversion from coefficient representation to dot representation 38 3.1.4 [Algorithm 10] Conversion from dot representation to coefficient representation 42 3.1.5 [Example 7] Conversion between coefficient representation and dot representation 46 3.2 Polynomial operations 47 3.2.1 [Algorithm 11] Multiplication of Polynomials with Complex Coefficients 47 3.2.2 [Algorithm 12] Multiplication of Polynomials with Real Coefficients 50 3.2.3 [Algorithm 13] Division of Polynomials with Complex Coefficients 52 3.2.4 [Algorithm 14] Division of Polynomials with Real Coefficients 54 3.2.5 [Example 8] Multiplication and Division of Polynomials with Complex Coefficients 56 3.2.6 [Example 9] Multiplication and Division of Polynomials with Real Coefficients 57 3.3 Polynomial Evaluation 59 3.3.1 [Algorithm 15] Evaluation of Univariate Polynomials 59 3.3.2 [Algorithm 16] Evaluation of Multiple Groups of Univariate Polynomials 60 3.3.3 [Algorithm 17] Evaluation of Bivariate Polynomials 63 3.3.4 [Example 10] Evaluation of Univariate Polynomials 65 3.3.5 [Example 11] Evaluation of Bivariate Polynomials 66 Chapter 4 Matrix Computation 68 4.1 Matrix Multiplication 68 4.1.1 [Algorithm 18] Real Matrix Multiplication 68 4.1.2 [Algorithm 19] Complex Matrix Multiplication 70 4.1.3 [Example 12] Real Matrix and Complex Matrix Multiplication 72 4.2 Matrix Rank and Determinant 73 4.2.1 [Algorithm 20] Finding the Rank of a Matrix 73 4.2.2 [Algorithm 21] Finding the Determinant of a General Matrix 76 4.2.3 [Algorithm 22] Finding the Determinant of a Symmetric Positive Definite Matrix 80 4.2.4 [Example 13] Finding the Rank and Determinant of a Matrix 82 4.3 Matrix Inversion 84 4.3.1 [Algorithm 23] Finding the Inverse of a General Complex Matrix 84 4.3.2 [Algorithm 24] Finding the Inverse of a Symmetric Positive Definite Matrix 90 4.3.3 [Algorithm 25] Trench Method for Finding the Inverse of a Tobelitz Matrix 92 4.3.4 [Example 14] Verify the Matrix Inversion Algorithm 97 4.3.5 [Example 15] Verify the T Matrix Inversion Algorithm 99 4.4 Matrix Decomposition and Similarity Transformation 102 4.4.1 [Algorithm 26] LDL Decomposition of Real Symmetric Matrices 102 4.4.2 [Algorithm 27] ​​Cholesky Decomposition of Symmetric Positive Definite Real Matrices 104 4.4.3 [Algorithm 28] All-Pivot LU Decomposition of General Real Matrices 107 4.4.4 [Algorithm 29] QR Decomposition of General Real Matrices 112 4.4.5 [Algorithm 30] Similarity Transformation of Symmetric Real Matrices to Symmetric Tridiagonal Matrices 116 4.4.6 [Algorithm 31] Similarity Transformation of General Real Matrices to Upper Hessen-Burg Matrices 121 4.4.7 [Example 16] QR Decomposition of General Real Matrices 126 4.4.8 [Example 17] Similarity Transformation of Symmetric Matrices 127 4.4.9 [Example 18] General Real Matrix Similarity Transformation 129 4.5 Matrix Eigenvalue Computation 130 4.5.1 [Algorithm 32] QR Method for Finding All Eigenvalues ​​of the Upper Hessen-Burg Matrix 130 4.5.2 [Algorithm 33] Finding All Eigenvalues ​​of a Symmetric Tridiagonal Matrix 137 4.5.3 [Algorithm 34] Jacobi Method for Finding Eigenvalues ​​of a Symmetric Matrix 143 4.5.4 [Algorithm 35] Jacobi Pass Method for Finding Eigenvalues ​​of a Symmetric Matrix 147 4.5.5 [Example 19] Finding Eigenvalues ​​of the Upper Hessen-Burg Matrix 151 4.5.6 [Example 20] Finding Eigenvalues ​​of a Symmetric Matrix Using Two Jacobi Methods Respectively 152 Chapter 5 Solving Systems of Linear Algebraic Equations 154 5.1 Gaussian Elimination Method 154 5.1.1 [Algorithm 36] Full Pivot Gaussian Elimination Method for Solving Systems of Complex Coefficients 155 5.1.2 [Algorithm 37] Selected Pivot Gaussian Elimination for Solving Systems of Equations with Real Coefficients 160 5.1.3 [Algorithm 38] Selected Pivot Gaussian-Jordan Elimination for Solving Systems of Equations with Complex Coefficients 163 5.1.4 [Algorithm 39] Selected Pivot Gaussian-Jordan Elimination for Solving Systems of Equations with Real Coefficients 168 5.1.5 [Algorithm 40] Gaussian-Jordan Elimination for Solving Systems of Equations with Large Sparse Coefficient Matrices 171 5.1.6 [Algorithm 41] Chasing Method for Solving Systems of Tridiagonal Equations 174 5.1.7 [Algorithm 42] Method for Solving Systems of Band-Type Equations 176 5.1.8 [Example 21] Solving Systems of Linear Equations with Real Coefficients 179 5.1.9 [Example 22] Solving Systems of Linear Equations with Complex Coefficients 180 5.1.10 [Example 23] Solving Systems of Tridiagonal Equations 182 5.2 Matrix Decomposition Method 184 5.2.1 [Algorithm 43] LDL Decomposition Method for Solving Symmetric Systems of Equations 184 5.2.2 [Algorithm 44] Cholesky Decomposition Method for Solving Symmetric Positive Definite Systems of Equations 186 5.2.3 [Algorithm 45] QR Decomposition Method for Solving Linear Least Squares Problems 188 5.2.4 [Example 24] Solving Symmetric Positive Definite Systems of Equations 191 5.2.5 [Example 25] Solving Linear Least Squares Problems 192 5.3 Iterative Methods 193 5.3.1 [Algorithm 46] Solving Ill-Conditioned Systems of Equations 193 5.3.2 [Algorithm 47] Jacobi Iteration Method 197 5.3.3 [Algorithm 48] Gauss-Seidel Iteration Method 200 5.3.4 [Algorithm 49] Super-Relaxation Method 203 5.3.5 [Algorithm 50] Conjugate Gradient Method for Solving Symmetric Positive Definite Systems of Equations 205 5.3.6 [Algorithm 51] Levinson method for solving the Tobelitz equations 209 5.3.7 [Example 26] Solving ill-conditioned equations 214 5.3.8 [Example 27] Solving equations using iteration 215 5.3.9 [Example 28] Solving the Tobelitz equations 217 Chapter 6 Solving nonlinear equations and equation systems 219 6.1 Basic process for finding roots of nonlinear equations 219 6.1.1 Determine the initial approximate value of the real root of a nonlinear equation or the interval where the root lies 219 6.1.2 Find the exact solution of the root of a nonlinear equation 221 6.2 Method for finding a real root of a nonlinear equation 221 6.2.1 [Algorithm 52] Bisection method 221 6.2.2 [Algorithm 53] Newton\'s method 223 6.2.3 [Algorithm 54] Interpolation method 226 6.2.4 [Algorithm 55] Aitkin Iteration Method 229 6.2.5 [Example 29] Using Bisection Method to Find Real Roots of Nonlinear Equations 232 6.2.6.2.7 [Example 31] Using interpolation method to find real roots of nonlinear equations 235 6.2.8 [Example 32] Using Aitkin iteration method to find real roots of nonlinear equations 237 6.3 Method for finding all roots of polynomial equations with real coefficients 238 6.3.1 [Algorithm 56] QR method 238 6.3.2 [Example 33] Using QR method to solve all roots of polynomials 240 6.4 Method for finding a set of real roots of nonlinear equations 241 6.4.1 [Algorithm 57] Gradient method 241 6.4.2 [Algorithm 58] Quasi-Newton method 244 6.4.3 [Example 34] Using gradient method to calculate a set of real roots of nonlinear equations 250 6.4.4 [Example 35] Using quasi-Newton method to calculate a set of real roots of nonlinear equations 252 Chapter 7 Algebraic interpolation method 254 7.1 Lagrange interpolation 254 7.1.1 [Algorithm 59] Linear interpolation 255 7.1.2 [Algorithm 60] Quadratic parabola interpolation 256 7.1.3 [Algorithm 61] Full interval interpolation 259 7.1.4 [Example 36] Lagrange interpolation 262 7.2 Hermite interpolation 263 7.2.1 [Algorithm 62] Hermite unequal interval interpolation 263 7.2.2 [Algorithm 63] Hermite equidistant interpolation 267 7.2.3 [Example 37] Hermite interpolation 270 7.3 Aitkin stepwise interpolation 271 7.3.1 [Algorithm 64] Aitkin unequal interval interpolation 272 7.3.2 [Algorithm 65] Aitkin equidistant interpolation 275 7.3.3 [Example 38] 7.4 Smooth Interpolation 279 7.4.1 [Algorithm 66] Smooth Unequal Interpolation 279 7.4.2 [Algorithm 67] Smooth Equidistant Interpolation 283 7.4.3 [Example 39] Smooth Interpolation 286 7.5 Cubic Spline Interpolation 287 7.5.1 [Algorithm 68] Cubic Spline Interpolation for the First Boundary Condition 287 7.5.2 [Algorithm 69] Cubic Spline Interpolation for the Second Boundary Condition 292 7.5.3 [Algorithm 70] Cubic Spline Interpolation for the Third Boundary Condition 296 7.5.4 [Example 40] Spline Interpolation 301 7.6 Continued Fraction Interpolation 303 7.6.1 [Algorithm 71] Continued Fraction Interpolation 304 7.6.2 [Example 41] Function to Verify Continued Fraction Interpolation 308 Chapter 8 Numerical Integration 309 8.1 Variable Step Size Quadrature Method 310 8.1.1 [Algorithm 72] Variable Step Size Trapezoidal Quadrature Method 310 8.1.2 [Algorithm 73] Adaptive Trapezoidal Quadrature Method 313 8.1.3 [Algorithm 74] Variable Step Size Simpsen Quadrature Method 316 8.1.4 [Algorithm 75] Variable Step Size Simpsen Double Integration Method 318 8.1.5 [Algorithm 76] Romberg Integration 322 8.1.6 [Example 42] Single Integration Using Variable Step Size Integration Method 325 8.1.7 [Example 43] Double Integration Using Variable Step Size Simpsen Integration Method 326 8.2 Gauss Quadrature Method 328 8.2.1 [Algorithm 77] Legendre-Gauss Quadrature Method 328 8.2.2 [Algorithm 78] Chebyshev Quadrature Method 331 8.2.3 [Algorithm 79] Laguerre-Gauss Quadrature Method 334 8.2.4 [Algorithm 80] Hermite-Gauss Quadrature Method 336 8.2.5 [Algorithm 81] Adaptive Gauss Quadrature Method 337 8.2.6 [Example 44] Gauss Quadrature Method on Finite Interval 342 8.2.7 [Example 45] Gauss Quadrature Method on Semi-Infinite Interval 343 8.2.8 [Example 46] Gauss Quadrature Method on Infinite Interval 345 8.3 Continued Fraction Method 346 8.3.1 [Algorithm 82] Continued Fraction Method for Single Integral 346 8.3.2 [Algorithm 83] Continued Fraction Method for Double Integral 350 8.3.3 [Example 47] Continued Fraction Method for Single Integral 354 8.3.4 [Example 48] Continued Fraction Method for Double Integral 355 8.4 Monte Carlo method 356 8.4.1 [Algorithm 84] Monte Carlo method for single integral 356 8.4.2 [Algorithm 85] Monte Carlo method for double integral 358 8.4.3 [Example 49] Monte Carlo method for single integral 360 8.4.4 [Example 50] Monte Carlo method for double integral 361 Chapter 9 Solving initial value problems of ordinary differential equations (groups) 363 9.1 Euler method 364 9.1.1 [Algorithm 86] Fixed-step Euler method 364 9.1.2 [Algorithm 87] Variable-step Euler method 366 9.1.3 [Algorithm 88] Improved Euler method 370 9.1.4 [Example 51] Euler method for numerical solutions of ordinary differential equations 372 9.2 Runge-Kutta method 376 9.2.1 [Algorithm 89] Fixed-step Runge-Kutta method 376 9.2.2 [Algorithm 90] Variable-step Runge-Kutta method 379 9.2.3 [Algorithm 91] Variable-step Keel method 383 9.2.4 [Example 52] Runge-Kutta method for initial value problems of ordinary differential equations 386 9.3 Linear multi-step method 390 9.3.1 [Algorithm 92] Adams prediction-correction method 390 9.3.2 [Algorithm 93] Hamming method 394 9.3.3 [Algorithm 94] Two-sided method for full interval integration 399 9.3.4 [Example 53] Linear multi-step method for initial value problems of ordinary differential equations 401 Chapter 10 Fitting and approximation 405 10.1 Fitting of univariate polynomials 405 10.1.1 [Algorithm 95] Least squares fitting 405 10.1.2 [Algorithm 96] 10.1.3 [Example 54] Fitting a univariate polynomial 417 10.2 Fitting a rectangular region surface 419 10.2.1 [Algorithm 97] Fitting a rectangular region surface by least squares 419 10.2.2 [Example 55] Fitting a bivariate polynomial 428 Chapter 11 Special Functions 430 11.1 Continued Fraction Series and Exponential Integral 430 11.1.1 [Algorithm 98] Evaluation of Continued Fraction Series 430 11.1.2 [Algorithm 99] Exponential Integral 433 11.1.3 [Example 56] Evaluation of Continued Fraction Series 436 11.1.4 [Example 57] Evaluation of Exponential Integral 438 11.2 Gamma Function 439 11.2.1 [Algorithm 100] Gamma Function 439 11.2.2 [Algorithm 101] Beta function 441 11.2.3 [Algorithm 102] Factorial 442 11.2.4 [Example 58] Gamma and Beta function evaluation 443 11.2.5 [Example 59] Factorial evaluation 444 11.3 Incomplete Gamma function 445 11.3.1 [Algorithm 103] Incomplete Gamma function 445 11.3.2 [Algorithm 104] Error function 448 11.3.3 [Algorithm 105] Chi-square distribution function 450 11.3.4 [Example 60] Incomplete Gamma function evaluation 451 11.3.5 [Example 61] Error function evaluation 452 11.3.6 [Example 62] Chi-square distribution function evaluation 453 11.4 Incomplete Beta function 454 11.4.1 [Algorithm 106] Incomplete Beta Function 454 11.4.2 [Algorithm 107] Student Distribution Function 457 11.4.3 [Algorithm 108] Cumulative Binomial Distribution Function 458 11.4.4 [Example 63] Incomplete Beta Function Evaluation 459 11.5 Bessel Function 461 11.5.1 [Algorithm 109] Integer-Order Bessel Functions of the First Kind 461 11.5.2 [Algorithm 110] Integer-Order Bessel Functions of the Second Kind 466 11.5.3 [Algorithm 111] Variant of the first kind integer order Bessel function 469 11.5.4 [Algorithm 112] Variant of the second kind integer order Bessel function 473 11.5.5 [Example 64] Bessel function evaluation 476 11.5.6 [Example 65] Variant of Bessel function evaluation 477 11.6 Carlson elliptic integral 479 11.6.1 [Algorithm 113] Elliptic integral of the first kind 479 11.6.2 [Algorithm 114] Degenerate form of elliptic integral of the first kind 481 11.6.3 [Algorithm 115] Elliptic integral of the second kind 483 11.6.4 [Algorithm 116] Elliptic integral of the third kind 486 11.6.5 [Example 66] Evaluation of Legendre elliptic function integral of the first kind 490 11.6.6 [Example 67] Evaluation of Legendre elliptic function integral of the second kind 492 Chapter 12 Extreme Value Problems 494 12.1 One-Dimensional Extreme Value Solution 494 12.1.1 [Algorithm 117] Determine the Interval of the Minimum Point 494 12.1.2 [Algorithm 118] One-Dimensional Golden Section Search 499 12.1.3 [Algorithm 119] One-Dimensional Brent Method 502 12.1.4 [Algorithm 120] Brent Method Using First-Order Derivatives 506 12.1.5 [Example 68] Using the Golden Section Search Method to Find Extreme Values ​​511 12.1.6 [Example 69] Using Brent’s Method to Find Extreme Values ​​513 12.1.7 [Example 70] Using Brent’s Method with Derivatives to Find Extreme Values ​​515 12.2 Finding Extreme Values ​​of Multivariate Functions 517 12.2.1 [Algorithm 121] One-Dimensional Search Without Derivatives 517 12.2.2 [Algorithm 122] One-dimensional search requiring derivatives 519 12.2.3 [Algorithm 123] Powell’s method 522 12.2.4 [Algorithm 124] Conjugate gradient method 525 12.2.5 [Algorithm 125] Quasi-Newton method 531 12.2.6 [Example 71] Verifying one-dimensional search without derivatives 536 12.2.7 [Example 72] Finding extreme values ​​using Powell’s algorithm 537 12.2.8 [Example 73] Finding extreme values ​​using conjugate gradient method 539 12.2.9 [Example 74] Finding extreme values ​​using quasi-Newton method 540 12.3 Simplex method 542 12.3.1 [Algorithm 126] Simplex method for finding n-dimensional extreme values ​​without constraints 542 12.3.2 [Algorithm 127] Simplex method for finding n-dimensional extreme values ​​with constraints 548 12.3.3 [Algorithm 128] Simplex Method for Solving Linear Programming Problems 556 12.3.4 [Example 75] Using the Simplex Method to Find the Extreme Value of N Dimensions without Constraints 568 12.3.5 [Example 76] Using the Simplex Method to Find the Extreme Value of N Dimensions with Constraints 569 12.3.6 [Example 77] Solving Linear Programming Problems 571 Chapter 13 Random Number Generation and Statistical Description 574 13.1 Uniformly Distributed Random Sequence 574 13.1.1 [Algorithm 129] Generate a Random Number Uniformly Distributed Between 0 and 1 574 13.1.2 [Algorithm 130] Generate a Random Number Sequence Uniformly Distributed Between 0 and 1 576 13.1.3 [Algorithm 131] Generate a Random Integer Uniformly Distributed in Any Interval 577 13.1.4 [Algorithm 132] Generate a Random Integer Sequence Uniformly Distributed in Any Interval 578 13.1.5 [Example 78] Generate a sequence of uniformly distributed random numbers between 0 and 1 580 13.1.6 [Example 79] Generate a sequence of uniformly distributed random integers in any interval 581 13.2 Normally distributed random sequences 582 13.2.1 [Algorithm 133] Generate a random number with arbitrary mean and variance from a normal distribution 582 13.2.2 [Algorithm 134] Generate a sequence of normally distributed random numbers with arbitrary mean and variance 585 13.2.3 [Example 80] Generate a random number with arbitrary mean and variance from a normal distribution 587 13.2.4 [Example 81] Generate a sequence of normally distributed random numbers with arbitrary mean and variance 588 13.3 Statistical description 589 13.3.1 [Algorithm 135] Moments of distribution 589 13.3.2 [Algorithm 136] t distribution test for equal variances 591 13.3.3 [Algorithm 137] t-distribution test for different variances 594 13.3.4 [Algorithm 138] F-test for variance 596 13.3.5 [Algorithm 139] Chi-square test 599 13.3.6 [Example 82] Calculating the moment of a random sample 601 13.3.7 [Example 83] t-distribution test 602 13.3.8 [Example 84] F-distribution test 605 13.3.9 [Example 85] Algorithm for testing the chi-square test 607 Chapter 14 Search 609 14.1 Basic search 609 14.1.1 [Algorithm 140] Binary search of an ordered array 609 14.1.2 [Algorithm 141] Finding the largest and smallest elements in an unordered array at the same time 611 14.1.3 [Algorithm 142] Finding the Mth smallest element in an unordered array 613 14.1.4 [Example 86] 14.2 Searching Structures and Disk Files 617 14.2.1 [Algorithm 143] Sequential Search of Unordered Structure Arrays 617 14.2.2 [Algorithm 144] Sequential Search of Records in Disk Files 618 14.2.3 [Example 87] Searching in Structure Arrays and Files 619 14.3 Hash Search 622 14.3.1 [Algorithm 145] String Hash Function 622 14.3.2 [Algorithm 146] Hash Function 626 14.3.3 [Algorithm 147] Inserting Elements into a Hash Table 628 14.3.4 [Algorithm 148] Searching Elements in a Hash Table 629 14.3.5 [Algorithm 149] Deleting Elements from a Hash Table 631 14.3.6 [Example 88] Constructing a Hash Table and Searching It 632 Chapter 15 Sorting 636 15.1 Insertion Sort 636 15.1.1 [Algorithm 150] Direct Insertion Sort 636 15.1.2 [Algorithm 151] Shell Sort 637 15.1.3 [Example 89] Insertion Sort 639 15.2 Exchange Sort 641 15.2.1 [Algorithm 152] Bubble Sort 641 15.2.2 [Algorithm 153] Quick Sort 642 15.2.3 [Example 90] Exchange Sort 644 15.3 Selection Sort 646 15.3.1 [Algorithm 154] Direct Selection Sort 646 15.3.2 [Algorithm 155] Heap Sort 647 15.3.3 [Example 91] Selection Sort 650 15.4 Linear Time Sort 651 15.4.1 [Algorithm 156] Counting Sort 651 15.4.2 [Algorithm 157] 15.4.3 [Example 92] Linear Time Sorting 656 15.5 Merge Sort 657 15.5.1 [Algorithm 158] Two-Way Merge Sort 658 15.5.2 [Example 93] Two-Way Merge Sort 660 Chapter 16 Mathematical Transformations and Filtering 662 16.1 Fast Fourier Transform 662 16.1.1 [Algorithm 159] Complex Data Fast Fourier Transform 662 16.1.2 [Algorithm 160] Inverse Complex Data Fast Fourier Transform 666 16.1.3 [Algorithm 161] Real Data Fast Fourier Transform 669 16.1.4 [Example 94] Function to Verify Fourier Transform 671 16.2 Other Common Transformations 674 16.2.1 [Algorithm 162] Fast Walsh Transform 674 16.2.2 [Algorithm 163] Fast Hadamard Transform 678 16.2.3 [Algorithm 164] Fast Cosine Transform 682 16.2.4 [Example 95] Verify Walsh transform and Hadamard function 684 16.2.5 [Example 96] Verify discrete cosine transform function 687 16.3 Smoothing and filtering 688 16.3.1 [Algorithm 165] Five-point cubic smoothing 689 16.3.2 [Algorithm 166] α-β-γ filtering 690 16.3.3 [Example 97] Verify five-point cubic smoothing 692 16.3.4 [Example 98] Verify α-β-γ filtering algorithm 693