Math for Programming Learn the Math, Write Better Code (Ronald T. Kneusel) (Z-Library)

MATH FOR PROGRAMMING Learn the Math, Write Better Code by Ronald T. Kneusel no starch press® San Francisco

MATH FOR PROGRAMMING. Copyright © 2025 by Ronald T. Kneusel. All rights reserved. No part of this work may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording, or by any information storage or retrieval system, without the prior written permission of the copyright owner and the publisher. First printing 29 28 27 26 25 1 2 3 4 5 ISBN-13: 978-1-7185-0358-8 (print) ISBN-13: 978-1-7185-0359-5 (ebook) Published by No Starch Press®, Inc. 245 8th Street, San Francisco, CA 94103 phone: +1.415.863.9900 www.nostarch.com; info@nostarch.com Publisher: William Pollock Managing Editor: Jill Franklin Production Manager: Sabrina Plomitallo-González Production Editor: Miles Bond Developmental Editor: Eva Morrow Cover Illustrator: Garry Booth Interior Design: Octopod Studios Technical Reviewer: Michael Galloy Copyeditor: Sharon Wilkey Proofreader: Lisa McCoy Library of Congress Control Number: 2024044258 For customer service inquiries, please contact info@nostarch.com. For information on distribution, bulk sales, corporate sales, or translations: sales@nostarch.com. For permission to translate this work: rights@nostarch.com. To report counterfeit copies or piracy: counterfeit@nostarch.com. No Starch Press and the No Starch Press iron logo are registered trademarks of No Starch Press, Inc. Other product and company names mentioned herein may be the trademarks of their respective owners. Rather than use a trademark symbol with every occurrence of a trademarked name, we are using the names only in an editorial fashion and to the benefit of the trademark owner, with no intention of infringement of the trademark.

The information in this book is distributed on an “As Is” basis, without warranty. While every precaution has been taken in the preparation of this work, neither the author nor No Starch Press, Inc. shall have any liability to any person or entity with respect to any loss or damage caused or alleged to be caused directly or indirectly by the information contained in it.

About the Author Ronald T. Kneusel works in industry building deep learning (AI) systems. He also has extensive experience with medical imaging and the development of medical devices. His PhD in computer science is from the University of Colorado, Boulder, and he also holds a master’s degree in physics from Michigan State University and an undergraduate degree in physics and mathematics from Valparaiso University. His interests vary greatly but always orbit science, math, and technology. A child of the personal computer revolution in the late 1970s and early 1980s, Ron has been coding for longer than he’s been able to drive. And, remarkably, it remains as fresh an enterprise now as it was all those decades ago.

About the Technical Reviewer Michael Galloy is a software developer focusing on high-performance computing and visualization in scientific programming. He is currently a software engineer at the National Center for Atmospheric Research, where he works on data from ground-based solar telescopes at the Mauna Loa Solar Observatory in the High Altitude Observatory. Previously, he was a research mathematician at Tech-X Corporation. He maintains and develops several open source projects in IDL and is the author of Modern IDL (2011). Follow his updates at https://michaelgalloy.com.

BRIEF CONTENTS Foreword Acknowledgments Introduction Chapter 1: Computers and Numbers Optimize storage, perform arithmetic operations, and prevent overflow or precision errors Chapter 2: Sets and Abstract Algebra Data structures, cryptography, error detection and correction, and algorithm design Chapter 3: Boolean Algebra Logic gates as well as conditional statement, control structure, and algorithm development Chapter 4: Functions and Relations Define algorithms, understand dependencies between data, and design software components Chapter 5: Induction Prove algorithm correctness, particularly those that involve recursion or iterative processes Chapter 6: Recurrence and Recursion Algorithm performance and problem-solving Chapter 7: Number Theory Cryptography, hash functions, and efficient algorithm development Chapter 8: Counting and Combinatorics

Analyze algorithm complexity and resource allocation, and solve permutation and probability problems Chapter 9: Graphs Network design, route optimization, connectivity solutions, and model relationships Chapter 10: Trees Essential for efficient searching, sorting, and parsing operations Chapter 11: Probability Model uncertainty, manage risk, and develop algorithms for randomized processes Chapter 12: Statistics Data analysis, model validation, decision-making, and machine learning algorithm development Chapter 13: Linear Algebra Computer graphics algorithms, machine learning models, and scientific computations Chapter 14: Differential Calculus Optimize functions, model change, and develop ML algorithms for training models Chapter 15: Integral Calculus Compute areas under curves, solve differential equations, and model continuous processes Chapter 16: Differential Equations Model and solve problems related to change and dynamic systems Index

CONTENTS IN DETAIL FOREWORD ACKNOWLEDGMENTS INTRODUCTION Who Is This Book For? What I Expect You to Know Already What Can You Expect to Learn? How to Use This Book 1 COMPUTERS AND NUMBERS Numbers and Number Bases Binary, Octal, and Hexadecimal Numbers Conversions Between Number Bases How Computers Represent Numbers Integers Floating-Point Numbers What You Need to Know About Floating-Point Arithmetic Round-Off Error Unrepresentable Numbers Summary 2 SETS AND ABSTRACT ALGEBRA Concerning Sets

Special Sets Set Operations Set Operations in Python Venn Diagrams Subsets and Supersets Power Sets The Laws of Set Theory Experimenting with Number Sets in Python Abstract Algebra and Groups Examples of Groups, Magmas, and Monoids Special Groups Cantor: To Infinity and Beyond The Cardinality of Infinite Sets The Continuum Hypothesis and Infinities Without End Computable and Uncomputable Numbers Uncomputable Python Summary 3 BOOLEAN ALGEBRA Definition and Laws Boolean Algebra Leads to Digital Logic Set Theory as a Boolean Algebra Propositional Logic as a Boolean Algebra The Set {0,1} as a Boolean Algebra The Truth Tables of Digital Logic Boolean Functions Duals and Complements Boolean Functions in Code Canonical Normal Forms Sum of Products Product of Sums

Karnaugh Maps Algebraic Simplification of Boolean Expressions Digital Circuits Boolean Functions as Digital Circuits All You Need Is NAND (or NOR) A Binary Adder Logic Gate Construction Summary 4 FUNCTIONS AND RELATIONS Functions Visualization of Functions Onto, One-to-One, and Inverse Functions Composition of Functions Binary Relations Cartesian Products Definition Relations as Matrices Counting Relations Relations on Infinite Sets Composition Converse and Complement Binary Relations as Graphs n-ary Relations Binary Relations in Code Equivalence Relations and Classes Equivalence Classes Number Sets Partial Orderings Summary

5 INDUCTION Weak Induction Strong Induction The Chicken Nuggets Problem The Fundamental Theorem of Arithmetic Cautionary Tales Forgetting the Base Case Reversing the Implication Showing the Inductive Hypothesis Holds for All m Proving with Loop Invariants Integer Square Root Bubble Sort Binary Search Gnome Sort Summary 6 RECURRENCE AND RECURSION Recurrence Relations Linear Recurrence Relations The Collatz Sequence Nonlinear Recurrence Relations Logistic Map Mandelbrot Set Solving Recurrence Relations First-Order Relations Second-Order Relations Recursion Powers Factorials Fibonacci Sequence

Quicksort Towers of Hanoi Summary 7 NUMBER THEORY Primes Proving Euclid’s Theorem Locating Primes Identifying Prime Subsets Exploring Quirky Primes Running the Primality Test Investigating the Goldbach Conjecture Divisibility Divisibility Properties The Least Common Multiple and the Greatest Common Divisor Modular Arithmetic Congruences Modular Equations Diophantine Equations Linear Nonlinear Integer Sequences Euler’s Totient Function Aliquot Sum and Sequence Harshad Numbers Narayana’s Cows Deranged Subfactorials Smith and Ruth–Aaron Numbers Sequence Audio Summary

8 COUNTING AND COMBINATORICS The Principles of Counting An Example: Hats in the Park Women Without Hats Men with (and Without) Hats Loose Ends Sum and Product Rules Inclusion-Exclusion The Pigeonhole Principle Permutations and Combinations Permutations Combinations The Binomial Theorem Summary 9 GRAPHS Basic Graph Concepts Complete Graphs Graph Isomorphisms Representing Graphs in Code Adjacency Lists Adjacency Matrices Breadth-First and Depth-First Traversal and Searching Breadth-First Traversal Depth-First Traversal Traversals as Searches The Shortest Path Between Nodes Unweighted Shortest Path Dijkstra’s Algorithm for Weighted Graphs Directed Acyclic Graphs and Topological Sort

Working Through an Example Coding Topological Sort Summary 10 TREES Defining Trees Spanning Trees Locating Spanning Trees Finding Minimum Spanning Trees Rooted and Ordered Trees Binary Trees Binary Tree Traversals and Searches Using Breadth-First Tree Traversal Using Depth-First Tree Traversal Searching a Tree Binary Trees in Code Creating Traversals in Code Using the Code The Animals Game Summary 11 PROBABILITY Events and Random Variables The Rules of Probability Probability of an Event Sum Rule Product Rule Sum Rule Update Conditional Probability Total Probability

Joint and Marginal Probabilities Joint Probability Tables Chain Rule for Probability Probability Distributions Histograms Discrete Distributions Continuous Distributions The Central Limit Theorem and the Law of Large Numbers Bayes’ Theorem Summary 12 STATISTICS Types of Data Nominal Ordinal Interval Ratio Summary Statistics Means, Median, and Mode Measures of Variation Quantiles and Box Plots Quantiles and Percentiles Box Plots Robustness and Sensitivity to Outliers Correlation Pearson Correlation Spearman Correlation A Cautionary Tale: Anscombe’s Quartet Hypothesis Testing A Gedankenexperiment Independent Samples

Paired Samples Confidence Intervals Confidence Intervals and Hypothesis Tests Confidence Intervals and Sample Size Summary 13 LINEAR ALGEBRA Vectors and Vector Spaces Definitions Vectors as Geometric Objects Vectors in ℝn Row and Column Vectors Vector Operations Treasure Island Redux Vector Space Concepts Subspaces, Linear Combinations, and Spanning Sets Linear Independence and Basis Sets Matrices Exploring Matrix Examples Forming Vector Spaces Solving Systems of Linear Equations Gauss–Jordan Elimination Linear Vector Equations Square Matrices Properties of Square Matrices Matrix Rank Determinants Linear Transformations Affine Transformations Iterated Function Systems Eigenvalues and Eigenvectors

Finding Eigenvalues Finding Eigenvectors Summary 14 DIFFERENTIAL CALCULUS Derivatives Basic Rules Rules for Trigonometric Functions The Chain Rule Rules for Exponentials and Logarithms Minima and Maxima of Functions Using the Second Derivative Test Locating Stationary Points with Newton’s Method Partial Derivatives Mixed Partial Derivatives The Chain Rule for Partial Derivatives Derivatives in Code Numeric Differentiation Automatic Differentiation Symbolic Differentiation Optimization with Gradient Descent Summary 15 INTEGRAL CALCULUS Curves and Areas Indefinite Integrals A Few Indefinite Integrals Antiderivatives A Fistful of Integration Tricks Definite Integrals

The Throwing Darts Metaphor Monte Carlo Integration Trapezoidal Rule Simpson’s Rule Definite Integrals with SymPy Adaptive Numerical Integration Summary 16 DIFFERENTIAL EQUATIONS Ordinary Differential Equations First-Order Second-Order Solving ODEs Numerically Euler’s Method Runge–Kutta Method Worked Examples Simple Pendulum Projectile Motion with Drag SIR Epidemic Model Lorenz Attractor Summary Final Words INDEX