Numerical
Methods,
Algorithms
and Tools in
C#
© 2010 by Taylor and Francis Group, LLC
Numerical
Methods,
Algorithms
and Tools in
C#
Waldemar Dos Passos
Boca Raton London New York
CRC Press is an imprint of the
Taylor & Francis Group, an informa business
© 2010 by Taylor and Francis Group, LLC
All the source codes for the material contained in this book can be downloaded directly from the publisher’s
website: http://www.crcpress.com/product/isbn/9780849374791 followed by selecting the option for “Downloads & Updates.”
CRC Press
Taylor & Francis Group
6000 Broken Sound Parkway NW, Suite 300
Boca Raton, FL 33487-2742
© 2010 by Taylor and Francis Group, LLC
CRC Press is an imprint of Taylor & Francis Group, an Informa business
No claim to original U.S. Government works
Printed in the United States of America on acid-free paper
10 9 8 7 6 5 4 3 2 1
International Standard Book Number: 978-0-8493-7479-1 (Hardback)
This book contains information obtained from authentic and highly regarded sources. Reasonable efforts
have been made to publish reliable data and information, but the author and publisher cannot assume
responsibility for the validity of all materials or the consequences of their use. The authors and publishers
have attempted to trace the copyright holders of all material reproduced in this publication and apologize to
copyright holders if permission to publish in this form has not been obtained. If any copyright material has
not been acknowledged please write and let us know so we may rectify in any future reprint.
Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented,
including photocopying, microfilming, and recording, or in any information storage or retrieval system,
without written permission from the publishers.
For permission to photocopy or use material electronically from this work, please access www.copyright.
com (http://www.copyright.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood
Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and
registration for a variety of users. For organizations that have been granted a photocopy license by the CCC,
a separate system of payment has been arranged.
Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used
only for identification and explanation without intent to infringe.
Library of Congress Cataloging‑in‑Publication Data
Dos Passos, Waldemar.
Numerical methods, algorithms, and tools in C# / Waldemar Dos Passos.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-8493-7479-1 (hardcover : alk. paper)
1. Numerical analysis--Data processing. 2. Algorithms. 3. C# (Computer program
language) I. Title.
QA297.D684 2010
518.0285’5133--dc22
Visit the Taylor & Francis Web site at
http://www.taylorandfrancis.com
and the CRC Press Web site at
http://www.crcpress.com
© 2010 by Taylor and Francis Group, LLC
2009031461
Preface
Today, more than at any other time in the history of mankind, computers are increasingly and successfully being exploited to gain a better understanding of our physical
world and as a result, also deepen our appreciation and reverence for God’s Creation.
Consequently, as computers evolve, so must the means to control them through advancements not just in hardware but also in software.
In order to satisfy this demand for better software, Microsoft released an entirely
new programming language called C# that incorporates the best features of all the
other existing popular programming languages such as Java, C/C++, and Visual Basic. In spite of considerable resistance by some people who persist on clinging on to
the past and continue to program computers the hard way, C# has now firmly established itself worldwide as arguably the preferred language for software application
development. Although many excellent books on the topic of general programming
in C# have been written, there is still a considerable lack of published material on
the topic of numerical methods in C#.
Accordingly, Numerical Methods, Algorithms and Tools in C# is a book containing a large collection of very useful ready-to-use mathematical routines, algorithms
and other computational tools aimed at programmers, mathematicians, statisticians,
scientists, engineers and anyone else interested in developing mathematically oriented computer applications in the relatively new and easy-to-learn object-oriented
C# programming language from Microsoft. With a heavy emphasis on using well
established numerical methods, object-oriented techniques and the latest state-ofthe-art Microsoft .NET programming environment, this book provides readers with
working C# code including practical examples that can be easily customized and implemented to solve complex engineering and scientific problems typically found in
real-world applications.
For the benefit of those readers who are not yet familiar with C#, Chapter 1 provides a brief outline of the .NET Framework, the C# programming language and the
basic concepts of Object Oriented Programming (OOP). Special attention is given to
topics that illustrate how to best utilize these and other tools to develop accurate and
robust numerical methods in C#.
Chapter 2 is entirely focused on the .NET Framework Math Class Library which
already comes built into Microsoft’s Visual Studio software development system.
Additional material is introduced where appropriate in order to supplement, complete or otherwise enhance the features already available with this library.
Chapter 3 introduces data structures along with their associated functions that are
particularly useful for programming and working with vectors and matrices. These
iii
© 2010 by Taylor and Francis Group, LLC
iv
Numerical Methods, Algorithms and Tools in C#
routines are often used in more advanced applications in later chapters.
Chapter 4 is entirely dedicated to the topic of complex numbers. Since timing
issues can sometimes pose a substantial problem when doing numerical calculations,
complex number functions are presented using both elegant state-of-the-art objectoriented methods which, although slick, can at times carry some overhead and the
old fashioned but proven methods which at times have been found to actually run
faster on some computers. In addition, important overflow and underflow issues are
also discussed and alternative solutions to avoid those problems are proposed.
Chapter 5 is devoted solely to sorting and searching algorithms. Computers are
often required to perform various types of data sorting for which many different
algorithms exist. Consequently, choosing the most efficient sorting algorithm is a
very important decision that developers frequently have to make. In this chapter,
readers are provided with both a wide selection of sorting and searching algorithms
from which to choose along with a brief explanation of how each algorithm works.
Chapter 6 is centered on the topic of bit manipulation which is typically used in
a variety of programming applications ranging anywhere from computer interfacing
to image processing.
Chapter 7 is focused on interpolation methods. Equations that cannot be solved
analytically often need to be solved using some kind of interpolation scheme, and
this chapter has plenty of practical examples to illustrate how one might handle this
kind of problem.
Chapter 8 centers on the numerical manipulation of linear algebraic equations.
This is actually a huge topic by itself and quite worthy of its own book. Nevertheless, a substantial amount of useful information can be readily obtained from just a
handful of these powerful tools.
Chapter 9 is focused on numerical methods for calculating approximate solutions
to nonlinear equations which often appear naturally in various branches of science
and engineering.
Chapter 10 is devoted exclusively to the topic of random numbers. Although C#
comes with its own internal random number generator function, it is not regarded to
be sufficiently robust for use in advanced secured applications or in computer simulations that require thousands and sometimes even millions of random numbers in
order to produce reliable and accurate results. Alternate ways to obtain both computer generated pseudo-random numbers and real random numbers obtained from
naturally occurring physical phenomena are also discussed. In addition, routines are
also provided for generating random numbers that follow a particular probability
distribution function.
Chapter 11 describes various methods for approximating numerical differentiation
of functions. This is a very tricky and controversial topic whose approximations can
give fairly good to atrociously bad results. Nevertheless, numerical methods do exist
for calculating these types of functions. The trick is really in learning to recognize the
difference between good and bad results and in choosing the best available method
for use in a particular situation.
Chapter 12 centers on developing numerical methods for approximating integrals
of specific functions as well as from collections of raw data points. Other more exotic
© 2010 by Taylor and Francis Group, LLC
Preface
v
ways of calculating integrals, such as by using Monte Carlo methods, are also briefly
discussed.
Chapter 13 contains a considerable number of routines for use in performing statistical analysis of data.
Chapter 14 is devoted to developing numerical methods for approximating special
functions which are typically found in various branches of mathematics, physics and
engineering.
Chapter 15 is focused on least squares and numerical curve fitting methods that
are frequently used in analyzing experimental data. A brief discussion of the χ 2
goodness-of-fit test is also included.
Chapter 16 centers on developing routines to find numerical solutions to ordinary
differential equations. Although this is really a huge topic, there are some basic
numerical methods which can be used successfully to solve a lot of these types of
equations in many real-world applications.
Chapter 17 introduces some numerical methods for solving partial differential
equations. Although this is also a huge topic by itself and quite deserving of its
own book, there are some standard types of partial differential equations that arise
naturally in many areas of science and engineering, and whose solutions can be approximated by well established numerical methods.
Chapter 18 focuses on optimization methods which are primarily aimed at the
minimization or maximization of functions and thus have many practical scientific
and engineering applications. Since this is still a very active area of ongoing research,
the examples presented here are more narrowly focused on just a few established
topics with the explicit purpose of illustrating how such methods may be individually
customized and then applied towards solving more advanced problems.
Lastly, I would like to point out that most of the numerical methods described in
this book have actually been around in one form or another for years, and sometimes
even for centuries, and it is only their computer implementation in C# that makes
this book uniquely different from some other book on the topic of numerical analysis. Accordingly, I have made every effort to track down and give proper credit to
original sources whenever possible as the size of this book’s reference section can
easily attest. In addition, I have also made every effort to provide my readers with
accurate, reliable information to help them in their efforts to successfully complete
their programming projects. Unfortunately, unwanted mistakes including typographical errors may inadvertently creep up somewhere in this book. As a result, I would
greatly appreciate if my readers would be so kind as to bring to my attention if such
errors are ever found so that I may promptly have the problem corrected for any future editions of this book. Also, as with just about everything we do in life, there is
always room for improvement. Accordingly, I would also very much welcome any
constructive criticism that my readers may have regarding this book so that I can perhaps make appropriate changes. Finally, there is an old saying that states, “an author
never finishes a book, but merely abandons it.” I have certainly come to appreciate
that observation after working on this project for so long and making countless revisions. Nevertheless, this has certainly been a very enjoyable project where just about
every word was carefully chosen and every topic was meticulously researched and
© 2010 by Taylor and Francis Group, LLC
vi
Numerical Methods, Algorithms and Tools in C#
documented. Therefore, if it is indeed true that I have willingly chosen to abandon
writing this book, it is only with the modest hope that it may be useful to my readers
in spite of any possible shortcomings.
Waldemar Dos Passos, Ph.D.
Concord, California
e-mail:
[email protected]
website: www.waldemardospassos.com
Acknowledgements
It gives me great pleasure to thank the many people who made this book possible.
First, I would very much like to thank my publisher, Nora Konopka, for not only accepting this book for publication but also for her exceptional patience as I underwent
a series of unforeseen tumultuous events in my life during the course of writing this
book which unfortunately led to some regrettable delays in its original publication
target date. I would also like to particularly thank both my project director, Theresa
Delforn, and my editor, Amy Rodriguez, for their excellent expert guidance in various aspects of this project. I would also like to thank Dawn Snider for her excellent
artistic skills in designing the cover for this book. Many thanks to Ashley Gasque
for guiding me through the necessary bureaucratic paperwork and to Shashi Kumar
for some expert LATEX tips he gave me. I would also like to thank all those other
wonderful people at Taylor & Francis who have worked tirelessly behind the scenes
to make this project a success but whose exact names I may likely never come to
know.
I am also very grateful for the support I received from the H.E. Martin Foundation
under grant 13011938. Without their most kind and extraordinary generous financial
assistance, the writing of this book would not have been possible.
I am especially grateful to my third grade teacher, Miss Daly, for all her help,
patience, kindness, and enthusiasm which ultimately sparked my interest in mathematics and eventually, physics. Looking back over all these years that have elapsed
since I was a student in her class, I can now say unequivocally that Miss Daly was
by far the very best and most caring teacher, professor, or instructor I ever had.
Lastly, I would also like to express my deepest and most heartfelt thanks to my
parents, Helenice and Waldemar Dos Passos (Sr.)
© 2010 by Taylor and Francis Group, LLC
This book is dedicated with all my love and care to my parents,
Helenice and Waldemar Dos Passos (Sr.)
for all their hard work, genuine love, and selfless sacrifices
made on my behalf throughout my entire life.
“In this life we cannot do great things; only small things with great love.”
Mother Teresa
Ad Majorem Dei Gloriam
© 2010 by Taylor and Francis Group, LLC
Contents
1
Introduction
1.1 C# and the .NET Framework . . . . . . . . . . . . . . . .
1.2 Installing C# and the .NET Framework . . . . . . . . . . .
1.3 Overview of Object-Oriented Programming (OOP) . . . .
1.4 Your First C# Program . . . . . . . . . . . . . . . . . . .
1.5 Overview of the IDE Debugger . . . . . . . . . . . . . . .
1.6 Overview of the C# Language . . . . . . . . . . . . . . .
1.6.1 Data Types . . . . . . . . . . . . . . . . . . . . .
1.6.2 Value Types . . . . . . . . . . . . . . . . . . . . .
1.6.3 Reference Types . . . . . . . . . . . . . . . . . .
1.6.4 Type-Parameter Types . . . . . . . . . . . . . . .
1.6.5 Pointer Types . . . . . . . . . . . . . . . . . . . .
1.6.6 Variable Declaration . . . . . . . . . . . . . . . .
1.6.7 Constant Declaration . . . . . . . . . . . . . . . .
1.6.8 Nullable Types . . . . . . . . . . . . . . . . . . .
1.6.9 Scope . . . . . . . . . . . . . . . . . . . . . . . .
1.6.10 Characters . . . . . . . . . . . . . . . . . . . . . .
1.6.11 Strings . . . . . . . . . . . . . . . . . . . . . . .
1.6.12 Formatting of Output Data . . . . . . . . . . . . .
1.6.13 Type Conversion . . . . . . . . . . . . . . . . . .
1.6.14 Reading Keyboard Input Data . . . . . . . . . . .
1.6.15 Basic Expressions and Operators . . . . . . . . . .
1.6.16 Program Flow Mechanisms . . . . . . . . . . . . .
1.6.17 Jump Statements . . . . . . . . . . . . . . . . . .
1.6.18 Arrays . . . . . . . . . . . . . . . . . . . . . . . .
1.6.19 Enumerations . . . . . . . . . . . . . . . . . . . .
1.6.20 Structures . . . . . . . . . . . . . . . . . . . . . .
1.6.21 Exceptions . . . . . . . . . . . . . . . . . . . . .
1.6.22 Classes . . . . . . . . . . . . . . . . . . . . . . .
Constructors and Destructors . . . . . . . . . . . . .
Properties . . . . . . . . . . . . . . . . . . . . . . .
Methods . . . . . . . . . . . . . . . . . . . . . . .
1.6.23 Indexers . . . . . . . . . . . . . . . . . . . . . . .
1.6.24 Overloading Methods, Constructors and Operators
1.6.25 Delegates . . . . . . . . . . . . . . . . . . . . . .
1.6.26 Events . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
3
3
4
9
11
12
13
14
16
17
17
18
18
18
18
19
19
20
23
24
27
29
30
32
32
33
34
37
38
38
42
42
43
46
ix
© 2010 by Taylor and Francis Group, LLC
x
Numerical Methods, Algorithms and Tools in C#
1.6.27 Collections . . . . . . . . . . . . . . . . . . . . . . . . .
1.6.28 File Input/Output . . . . . . . . . . . . . . . . . . . . . .
1.6.29 Output Reliability, Accuracy and Precision . . . . . . . .
2
The .NET Framework Math Class Library
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 The .NET Framework Math Class - Fields . . . . . . . . . . . .
2.2.1 The Math.PI and Math.E Fields . . . . . . . . . . . . .
2.3 The .NET Framework Math Class - Methods . . . . . . . . . . .
2.3.1 The Minimum and Maximum Methods . . . . . . . . .
2.3.2 The Power, Exponential and Logarithmic Methods . . .
2.3.3 Special Multiplication, Division and Remainder Methods
2.3.4 The Absolute Value Method . . . . . . . . . . . . . . .
2.3.5 The Sign Method . . . . . . . . . . . . . . . . . . . . .
2.3.6 Angular Units of Measurement . . . . . . . . . . . . . .
2.3.7 The Trigonometric Functions . . . . . . . . . . . . . . .
2.3.8 The Inverse Trigonometric Functions . . . . . . . . . .
2.3.9 The Hyperbolic Functions . . . . . . . . . . . . . . . .
2.3.10 The Inverse Hyperbolic Functions . . . . . . . . . . . .
2.3.11 Rounding Off Numeric Data . . . . . . . . . . . . . . .
The Ceiling Method . . . . . . . . . . . . . . . . . . . .
The Floor Method . . . . . . . . . . . . . . . . . . . . .
The Truncation Method . . . . . . . . . . . . . . . . . .
The Round Method . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
57
60
65
73
73
73
73
74
74
74
76
77
78
78
81
82
86
88
89
89
90
90
91
3
Vectors and Matrices
97
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.2 A Real Number Vector Library in C# . . . . . . . . . . . . . . . . 98
3.3 A Real Number Matrix Library in C# . . . . . . . . . . . . . . . . 106
4
Complex Numbers
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Fundamental Concepts . . . . . . . . . . . . . . . . . .
4.3 Complex Number Arithmetic . . . . . . . . . . . . . . .
4.4 Elementary Functions of a Complex Number . . . . . . .
4.4.1 Exponentials . . . . . . . . . . . . . . . . . . .
4.4.2 Logarithms . . . . . . . . . . . . . . . . . . . .
4.4.3 Powers and Roots . . . . . . . . . . . . . . . . .
4.4.4 Trigonometric and Hyperbolic Functions . . . .
4.4.5 Inverse Trigonometric and Hyperbolic Functions
4.5 A Complex Number Library in C# . . . . . . . . . . . .
4.6 A Complex Number Vector Library in C# . . . . . . . .
4.7 A Complex Number Matrix Library in C# . . . . . . . .
4.8 Generic vs. Non-Generic Coding . . . . . . . . . . . . .
© 2010 by Taylor and Francis Group, LLC
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
121
121
121
123
125
125
125
127
128
130
132
151
158
168
Table of Contents
5
6
7
xi
Sorting and Searching Algorithms
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . . .
5.3 Comparison Sorts . . . . . . . . . . . . . . . . . . . . . . . .
5.3.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . .
5.3.2 Cocktail Sort . . . . . . . . . . . . . . . . . . . . . .
5.3.3 Odd-Even Sort . . . . . . . . . . . . . . . . . . . . .
5.3.4 Comb Sort . . . . . . . . . . . . . . . . . . . . . . .
5.3.5 Gnome Sort . . . . . . . . . . . . . . . . . . . . . . .
5.3.6 Quicksort . . . . . . . . . . . . . . . . . . . . . . . .
5.3.7 Insertion Sort . . . . . . . . . . . . . . . . . . . . . .
5.3.8 Shell Sort . . . . . . . . . . . . . . . . . . . . . . . .
5.3.9 Selection Sort . . . . . . . . . . . . . . . . . . . . . .
5.3.10 Merge Sort . . . . . . . . . . . . . . . . . . . . . . .
5.3.11 Bucket Sort . . . . . . . . . . . . . . . . . . . . . . .
5.3.12 Heap Sort . . . . . . . . . . . . . . . . . . . . . . . .
5.4 Count Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.5 Radix Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.6 Search Algorithms . . . . . . . . . . . . . . . . . . . . . . . .
5.6.1 Linear Search . . . . . . . . . . . . . . . . . . . . . .
5.6.2 Binary Search . . . . . . . . . . . . . . . . . . . . . .
5.6.3 Interpolation Search . . . . . . . . . . . . . . . . . .
5.6.4 Searching for the Maximum and Minimum Values . .
5.6.5 Searching for the N-th Largest or M-th Smallest Value
5.6.6 Some Useful Utilities . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
171
171
172
175
175
178
178
179
180
181
182
183
184
185
186
187
188
189
191
192
193
193
194
195
196
Bits and Bytes
6.1 Introduction . . . . . . . . . . . . . . .
6.2 Numeric Systems . . . . . . . . . . . .
6.3 Bit Manipulation and Bitwise Operators
6.4 Assorted Bits and Bytes . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
199
199
199
202
223
Interpolation
7.1 Introduction . . . . . . . . . . . . . . . . . . . . .
7.2 Linear Interpolation . . . . . . . . . . . . . . . . .
7.3 Bilinear Interpolation . . . . . . . . . . . . . . . .
7.4 Polynomial Interpolation . . . . . . . . . . . . . .
7.4.1 Lagrange Interpolation . . . . . . . . . . .
7.4.2 Barycentric Interpolation . . . . . . . . . .
7.4.3 Newton’s Divided Differences Interpolation
7.5 Cubic Spline Interpolation . . . . . . . . . . . . .
7.5.1 Natural Cubic Splines . . . . . . . . . . .
7.5.2 Clamped Cubic Splines . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
229
229
230
231
234
234
236
238
242
244
247
© 2010 by Taylor and Francis Group, LLC
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xii
8
Numerical Methods, Algorithms and Tools in C#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
251
251
253
254
256
259
259
261
264
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
271
271
272
274
276
277
279
280
10 Random Numbers
10.1 Introduction . . . . . . . . . . . . . . . . .
10.2 The C# Built-In Random Number Generator
10.3 Other Random Number Generators . . . . .
10.4 True Random Number Generators . . . . .
10.5 Random Variate Generation Methods . . . .
10.6 Histograms . . . . . . . . . . . . . . . . .
10.7 Random Variate Generation . . . . . . . . .
10.7.1 Discrete Distributions . . . . . . . .
Bernoulli Distribution . . . . . . . .
Binomial Distribution . . . . . . . .
Geometric Distribution . . . . . . . .
Negative Binomial Distribution . . .
Poisson Distribution . . . . . . . . .
Uniform Distribution (discrete) . . .
10.7.2 Continuous Distributions . . . . . .
Beta Distribution . . . . . . . . . . .
Beta Prime Distribution . . . . . . .
Cauchy Distribution . . . . . . . . .
Chi Distribution . . . . . . . . . . .
Chi-Square Distribution . . . . . . .
Erlang Distribution . . . . . . . . . .
Exponential Distribution . . . . . . .
Extreme Value Distribution . . . . . .
Gamma Distribution . . . . . . . . .
Laplace Distribution . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
283
283
284
290
295
299
309
312
312
312
315
317
320
322
326
328
328
330
332
334
337
340
343
345
347
349
9
Linear Equations
8.1 Introduction . . . . . . . . . . . .
8.2 Gaussian Elimination . . . . . . .
8.3 Gauss-Jordan Elimination . . . . .
8.4 LU Decomposition . . . . . . . .
8.5 Iteration Methods . . . . . . . . .
8.5.1 Gauss-Jacobi Iteration . .
8.5.2 Gauss-Seidel Iteration . .
8.6 Eigenvalues and Jacobi’s Algorithm
Nonlinear Equations
9.1 Introduction . . . . . . . .
9.2 Linear Incremental Method
9.3 Bisection Method . . . . .
9.4 The Secant Method . . . .
9.5 False Positioning Method .
9.6 Fixed Point Iteration . . . .
9.7 Newton-Raphson Method .
© 2010 by Taylor and Francis Group, LLC
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Table of Contents
xiii
Logistic Distribution . . . . . . .
Lognormal Distribution . . . . .
Normal Distribution . . . . . . .
Pareto Distribution . . . . . . . .
Rayleigh Distribution . . . . . . .
Student-t Distribution . . . . . . .
Triangular Distribution . . . . . .
Uniform Distribution (continuous)
Weibull Distribution . . . . . . .
10.8 Shuffling Algorithms . . . . . . . . . .
10.9 Adding Random Noise to Data . . . . .
10.10 Removing Random Noise from Data . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
352
354
356
359
361
363
365
368
370
372
376
379
11 Numerical Differentiation
11.1 Introduction . . . . . . . . . . . . . . . . . .
11.2 Finite Difference Formulas . . . . . . . . . .
11.2.1 Forward Difference Method . . . . .
11.2.2 Backward Difference Method . . . .
11.2.3 Central Difference Method . . . . . .
11.2.4 Improved Central Difference Method
11.3 Richardson Extrapolation . . . . . . . . . . .
11.4 Derivatives by Polynomial Interpolation . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
383
383
383
385
387
390
392
395
401
12 Numerical Integration
12.1 Introduction . . . . . . . . . . . . . .
12.2 Newton-Cotes Formulas . . . . . . . .
12.2.1 Rectangle Method . . . . . .
12.2.2 Midpoint Method . . . . . . .
12.2.3 Trapezoidal Method . . . . .
12.2.4 Simpson’s Method . . . . . .
Simpson’s 1/3 Method . . . . .
Simpson’s 3/8 Method . . . . .
12.3 Romberg Integration . . . . . . . . .
12.4 Gaussian Quadrature Methods . . . .
12.4.1 Gauss-Legendre Integration .
12.4.2 Gauss-Hermite Integration . .
12.4.3 Gauss-Leguerre Integration . .
12.4.4 Gauss-Chebyshev Integration
12.5 Multiple Integration . . . . . . . . . .
12.6 Monte Carlo Methods . . . . . . . . .
12.6.1 Monte Carlo Integration . . .
12.6.2 The Metropolis Algorithm . .
12.7 Convolution Integrals . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
405
405
406
406
408
409
411
411
412
414
416
417
419
421
423
424
426
427
428
431
© 2010 by Taylor and Francis Group, LLC
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xiv
Numerical Methods, Algorithms and Tools in C#
13 Statistical Functions
13.1 Introduction . . . . . . . . . . . . . . . . . . . .
13.2 Some Useful Tools . . . . . . . . . . . . . . . .
13.3 Basic Statistical Functions . . . . . . . . . . . .
13.3.1 Mean and Weighted Mean . . . . . . . .
13.3.2 Geometric and Weighted Geometric Mean
13.3.3 Harmonic and Weighted Harmonic Mean
13.3.4 Truncated Mean . . . . . . . . . . . . . .
13.3.5 Root Mean Square . . . . . . . . . . . .
13.3.6 Median, Range and Mode . . . . . . . .
13.3.7 Mean Deviation . . . . . . . . . . . . . .
13.3.8 Mean Deviation of the Mean . . . . . . .
13.3.9 Mean Deviation of the Median . . . . . .
13.3.10 Variance and Standard Deviation . . . . .
13.3.11 Moments About the Mean . . . . . . . .
13.3.12 Skewness . . . . . . . . . . . . . . . . .
13.3.13 Kurtosis . . . . . . . . . . . . . . . . . .
13.3.14 Covariance and Correlation . . . . . . . .
13.3.15 Miscellaneous Utilities . . . . . . . . . .
13.3.16 Percentiles and Rank . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
435
435
435
438
438
439
440
441
441
442
444
444
445
445
447
448
449
451
453
456
14 Special Functions
14.1 Introduction . . . . . . . . . . . .
14.2 Factorials . . . . . . . . . . . . .
14.3 Combinations and Permutations .
14.3.1 Combinations . . . . . . .
14.3.2 Permutations . . . . . . .
14.4 Gamma Function . . . . . . . . .
14.5 Beta Function . . . . . . . . . . .
14.6 Error Function . . . . . . . . . . .
14.7 Sine and Cosine Integral Functions
14.8 Laguerre Polynomials . . . . . . .
14.9 Hermite Polynomials . . . . . . .
14.10 Chebyshev Polynomials . . . . . .
14.11 Legendre Polynomials . . . . . . .
14.12 Bessel Functions . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
461
461
461
464
464
467
470
472
472
474
475
476
477
479
480
15 Curve Fitting Methods
15.1 Introduction . . . . . . . . . . . .
15.2 Least Squares Fit . . . . . . . . .
15.2.1 Straight-Line Fit . . . . .
15.3 Weighted Least Squares Fit . . . .
15.3.1 Weighted Straight-Line Fit
15.4 Linear Regression . . . . . . . . .
15.4.1 Polynomial Fit . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
483
483
484
485
488
488
492
496
© 2010 by Taylor and Francis Group, LLC
Table of Contents
xv
15.4.2 Exponential Fit . . . . . . . . . . . . . . . . . . . . . . . 497
15.5 The χ 2 Test for Goodness of Fit . . . . . . . . . . . . . . . . . . 499
16 Ordinary Differential Equations
16.1 Introduction . . . . . . . . . . . . . . . . .
16.2 Euler Method . . . . . . . . . . . . . . . .
16.3 Runge-Kutta Methods . . . . . . . . . . . .
16.3.1 Second-Order Runge-Kutta Method
16.3.2 Fourth-Order Runge-Kutta Method
16.3.3 Runge-Kutta-Fehlberg Method . . .
16.4 Coupled Differential Equations . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
503
503
505
506
507
508
510
513
17 Partial Differential Equations
17.1 Introduction . . . . . . . . . . . . . . .
17.2 The Finite Difference Method . . . . . .
17.3 Parabolic Partial Differential Equations .
17.3.1 The Crank-Nicolson Method . .
17.4 Hyperbolic Partial Differential Equations
17.5 Elliptic Partial Differential Equations . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
517
517
520
521
525
527
532
18 Optimization Methods
18.1 Introduction . . . . . . . . . . . . . .
18.2 Gradient Descent Method . . . . . . .
18.3 Linear Programming . . . . . . . . .
18.3.1 The Revised Simplex Method
18.4 Simulated Annealing Method . . . . .
18.5 Genetic Algorithms . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
539
539
541
544
546
550
555
References
© 2010 by Taylor and Francis Group, LLC
.
.
.
.
.
.
571
1
Introduction
The main objective of this first chapter is to provide my readers with a brief outline
of the .NET Framework, the C# programming language and the basic concepts of
Object Oriented Programming (OOP). Special attention will be given to materials
that illustrate how to best utilize these tools to develop accurate and robust numerical
methods in C# primarily for use in scientific and engineering applications.
1.1 C# and the .NET Framework
In the late 1990s, Microsoft embarked on a project to update and improve its flagship software application development system, more commonly known as Visual
Studio, and as a result of this effort, an entirely new programming language named
C# emerged that, among other things, essentially incorporates the best features of
all the other popular programming languages of the time such as Java, C/C++ and
Visual Basic. Consequently, since its first release in July of 2000, C# has quickly
established itself worldwide as perhaps the preferred language for software application development. Besides being a very powerful general purpose, object-oriented
programming language, C# enjoys the full advantage and benefits of being fully integrated with the Microsoft .NET Framework system.
The Microsoft .NET Framework is a fundamental Windows operating system
component that supports building and running both software applications as well
as Web services. It consists of a large set of class libraries of pre-coded solutions to
common programming problems and also provides a new environment for building applications that can be deployed and executed across multiple architectures
and operating systems. The .NET Framework was designed to be installed on top
of the Windows operating system and is divided into two key components: a runtime environment called the Common Language Runtime (CLR), which provides
the runtime services to manage and execute applications originally written in any
one of the .NET programming languages, and a large library of pre-coded object oriented classes called the Framework Class Library (FCL) which provides the required
services for developing .NET applications. Conceptually, .NET applications reside
above the .NET Framework architecture and can be illustrated abstractly as shown
in Table 1.1.
The C# language specification [1] has been standardized by ECMA International,
1
© 2010 by Taylor and Francis Group, LLC
2
Numerical Methods, Algorithms and Tools in C#
TABLE 1.1
Outline of the .NET Framework Architecture
Visual Basic
.NET Applications
Visual C#
Visual C++
.NET Framework Class Library (FCL)
Common Language Runtime (CLR)
Operating System
which is an industry association dedicated to the standardization of information
and communication systems. As a result, consumers can now choose to buy their
C# compilers from among several different manufacturers such as Microsoft [2],
SharpDevelop [3], DotGNU [4] and Mono [5]. However, the most popular C# compiler on the market today comes bundled with Microsoft’s Visual Studio software
development system which, in addition to having a C# compiler, also provides a
full featured integrated development environment (IDE) that standardizes support
for many of the other popular programming languages like Visual Basic and Visual
C++. Accordingly, all the code and examples contained in this book were written
and tested using the latest version of Microsoft Visual Studio.
As part of the natural evolution of programming languages, C# has incorporated
and exploited familiar features from C/C++ and Java that already had a proven record
of success. In addition, C# also has a number of unique new features that make it a
very attractive programming language. For example, C# controls access to hardware
and memory resources and, by default, does not allow for the explicit usage and manipulation of pointers as C and C++ do except for sections of code that have been
specifically designated as unsafe. This feature, along with the support of a more powerful garbage collector that automatically manages all aspects of memory allocation
and de-allocation during runtime, has now made frustrating memory leaks and dangling pointers, often hard to find and debug in C/C++ programs, a thing of the past.
In addition, improvements made in exception handling provide a well structured
and extensible approach to error detection and recovery. C# is also designed with
type-safe features that make it impossible to have non-initialized variables, to index
arrays beyond their bounds, or to perform unchecked type casts. The C# language
also supports more advanced features such as multi-threading and Just-in-Time (JIT)
compilation from byte code to native code to name a few.
© 2010 by Taylor and Francis Group, LLC
Introduction
3
1.2 Installing C# and the .NET Framework
You can buy Visual C# either by itself or as part of the Visual Studio IDE, which also
includes, in addition to Visual C#, support for other programming languages such as
Visual Basic and Visual C++. Visual C# comes in several editions. If you want
Visual C# all by itself, you have only one choice: the Express edition. However,
if you buy Visual C# as part of the Visual Studio package, you have three choices:
Standard, Professional and Team editions to accommodate every budget, work environment and skill level. There is also the Academic version of the Professional
edition which is available at a substantial discount for students and teachers. The
key differences between these various editions center primarily on the number of
development environment features available to the programmer. If you do computer
programming as a hobby, the Express edition should work just fine for most of the
applications described in this book. However, if you do a significant amount of software development in various languages and platforms, then you will likely derive
most benefit from the multipurpose Professional edition.
The Visual C# installation kit may consist of one or more CDs depending on the
edition chosen. The installation itself is relatively easy and is simply a matter of following the directions displayed on the screen. If you do not have the required .NET
Framework already installed on your system, the installation program will perform
that task automatically for you prior to doing anything else. Due to the huge size
of the program, it may take some time to install. But patience is a virtue in programming and it begins with the installation of Microsoft Visual Studio. Installing
the latest version of the MSDN reference libraries directly on your computer is also
highly recommended so that help files can be retrieved and promptly consulted as
needed.
1.3 Overview of Object-Oriented Programming (OOP)
There are primarily two methods of programming in use today: procedural and
object-oriented. Procedural programming has its roots in the earliest forms of programming languages and essentially involves creating and naming computer memory
locations that can hold data which can then be changed and manipulated through a
series of sequential steps. The named computer memory locations are called variables because they hold values that might vary at some point during the life of the
program. Sometimes a finite number of these sequential steps used in computer
programs can be grouped into smaller logical units called procedures. Hence the
objective of procedural programming is to focus on the creation of procedures to operate and potentially alter data. If, at some later point in time, the program’s original
© 2010 by Taylor and Francis Group, LLC
4
Numerical Methods, Algorithms and Tools in C#
specifications somehow change significantly enough to warrant a corresponding fundamental change in the program’s original data structure then the original code must
also be changed and rewritten to accept the new data format. Unfortunately, such
changes often result in additional work for programmers and this may ultimately
lead to potential project release delays, higher production costs and perhaps most
importantly, can also increase the chances for unwanted bugs to appear in the code.
Object-oriented programming can be thought of as a major significant improvement of procedural programming. Whereas procedural programming is focused on
creating procedures to manipulate data, object-oriented programming centers on creating abstract, self-contained software entities called objects that contain both attributes and methods, previously also known as data and procedures. The attributes
of an object provide information about its characteristics whereas the methods of an
object provide information about how to manipulate those attributes. More formally,
an object is said to be an instance of a class and a class is said to be a template or
a blueprint for describing how an object is created and how it behaves at runtime.
Hence, a class defines behavior, properties and other attributes of an object that is an
instance, or example, of that class.
Object-oriented programs have attributes and methods that are said to be encapsulated into objects. Encapsulation is the object oriented principle associated with
hiding the internal structural details of an object from the outside world so that programmers can only use a well defined interface to interact with an object’s internal
structure. This feature is intended to prevent programmers from easily and perhaps
even recklessly altering an object’s internal structure or behavior. Polymorphism is
the object-oriented programming principle that allows the creation of methods that
act appropriately depending on the context within which a particular task is carried
out. Inheritance is an object oriented principle relating to how one class, called the
derived or child class, can share the characteristics and behavior from another class,
called the base or parent class. In addition to its own new and unique attributes and
methods, the derived class is said to inherit and thus contain nearly all the attributes
and methods of the existing base class.
Therefore, besides retaining all the familiar and well established concepts of data
(i.e. attributes) and procedures (i.e. methods), object-oriented programming also
contains six additional unique features that are called: objects, classes, encapsulation, interfaces, polymorphism, and inheritance.
1.4 Your First C# Program
There are at least four general types of applications that can be created with C#:
Console applications, Windows Form applications, Web Services and ASP.NET applications. Console applications run from the command line and are the most fundamental and easiest applications to understand. Consequently, console applications
© 2010 by Taylor and Francis Group, LLC