I started reading Jeremy Kun’s A Programmer’s Introduction to Mathematics. This is just a collection of my notes from Chapter 2, or code/math that I felt like writing/typesetting as an exercise while working through the chapter.
I activated the SuperFences Markdown plugin in the blog’s settings, so it’s really cool to write code for the same thing in different languages side-by-side. (The Java lexer is a little off, though.)
Note: The chapter is divided into the “main material,” an implementation of something that uses the relevant math, and exercises. I had actually gotten through the material and code part of the chapter last week, before I wrote about Markov matrices, and thought I’d be able to publish the complete notes in one go.
However, the exercises are time-consuming and quickly get very difficult, so my impatience compels me to split this post in two, since it’d be strange to be writing about \(\Pi\) notation after covering way more advanced material! I’ll publish my answers to the exercises another week.
\(\sum\) (Summation)
Summation notation wasn’t new to me (I learned it the hard way trying to make sense of the linear regression stuff), nor was the Python equivalent. However, since it was presented in Java, I thought it was good opportunity to see the correspondence between Python and Java. When I first started learning to code (beyond web development), I ran away from Java with my tail between my legs, but now it makes a lot more sense. It’s just terribly verbose and inefficient.
Also, I wanted to use an easy example to get reacquainted with Clojure, my other favorite language, and pick up some R and Julia along the way too.
$$ f(x) = \sum_{i=0}^x i $$
def sum_to(x):
result = 0
for i in range(x + 1):
result += i
return result
In [2]: sum_to(3)
Out[2]: 6
def list_comp_sum_to(x):
return sum([i for i in range(x + 1)])
(defn sum-to [x]
(reduce +
(range 0 (+ x 1))))
user=> (sum-to 3)
6
public class main {
public static int sumTo(int x) {
int i;
int mySum = 0;
for (i = 0; i <= x; i++) {
mySum += i;
}
return mySum;
}
}
jshell> main.sumTo(10)
$9 ==> 55
function sum_to(x)
result = 0
for i = 0:x
result += i
end
result
end
julia> sum_to(3)
6
sum_to <- function(x) {
result <- 0
for (i in 0:x) {
result = result + 1
}
result
}
> sum_to(3)
[1] 4
\(\prod\) (Pi-product)
This was new to me, and so was the existence of the *= operator, which I guess I had never had a need for.
$$ g(x) = \prod_{j=1}^x i $$
def mult_all(x):
result = 1
for i in range(1, x + 1):
result *= i
return result
In [5]: mult_all(5)
Out[5]: 120
(defn mult-all [x]
(reduce *
(range 1 (+ x 1))))
user=> (mult-all 5)
120
public class main {
public static int multAll(int x) {
int i;
int myProd = 1;
for (i = 1; i <= x; i++) {
myProd *= i;
}
return myProd;
}
}
jshell> main.multAll(5)
$10 ==> 120
function mult_all(x)
result = 1
for i = 1:x
result *= i
end
result
end
julia> mult_all(5)
120
mult_all <- function(x) {
result <- 1
for (i in 1:x) {
result = result * i
}
result
}
> mult_all(5)
[1] 120
\(\sum\prod\) (Nested product in sum)
Pretty wild. I tried really hard to translate this into Clojure, but I couldn’t as-is.
$$ f(x) = \sum_{i=0}^n \textrm{bar}(i) \Bigg(\prod_{j \not = i} \textrm{foo}(i, j)\Bigg) $$
result = 0
for i in range(x + 1):
inner = 1
for j in range(x + 1):
if (j == i):
continue
inner *= foo(i, j)
result += bar(i) * inner
return result
int result = 0;
int n;
for (int i = 0; i <= n; i++) {
innerProd = 1;
for (int j = 0; i <= n; j++) {
if (j != i) {
innerProd *= foo(i, j)
}
result += bar(i) * inner
}
}
return result;
Horner’s Method
I had never heard of this until I encountered it in the code for the author’s Polynomial class. It is definitely easier to understand how it works in Python than it is to understand why it works mathematically!
$$ \begin{aligned} \sum_{i=0}^{n-1} a_i x^i &= a_0 + a_1 x + a_2 x^2 + \cdots + a_{n-1} x^{n-1} \\
&= a_0 + x(a_1 + x(a_2 + \cdots + x\,a_{n-1})) \end{aligned} $$
Cooler still, the recursion evident in the Python code means that it can be implemented as a reduce in functional programming, making it extremely concise and loopless.
If \(f(x) = 2x^3 + 4x + 3\), let’s find \(f(2)\) with Horner’s method.
def horners_method(coefficients, x):
result = 0
for c in reversed(coefficients):
result = result * x + c
return result
In [25]: horners_method([3,4,0,2], 2)
Out[25]: 27
(defn horners-method [coefs x]
(reduce #(+ %2 (* x %1)) 0 (reverse coefs)))
user=> (horners-method coefs 2)
27
public class main {
public static float hornersMethod(float[] coefficients, float x) {
float result = 0;
for (int i = coefficients.length - 1; i >= 0; i--) {
result = result * x + coefficients[i];
}
return result;
}
}
jshell> main.hornersMethod(new float[] {3,4,0,2}, 2)
$32 ==> 27.0
Nested polynomials
Speaking of nested polynomials, in the section on interpolating polynomials (normal ones), I was stuck on this line in the function single_term() for a bit:
def single_term(points, i):
theTerm = Polynomial([1.])
xi, yi = points[i]
for j, p in enumerate(points):
if j == i:
continue
xj = p[0]
theTerm = theTerm * Polynomial([-xj / (xi - xj), 1.0 / (xi - xj)])
return theTerm * Polynomial([yi])
This function is supposed to get us the term of the polynomial for point \(i\) of the points we feed it. It’s this, without the summation:
$$ f(x) = \sum_{i=0}^n y_i \Bigg(\prod_{j \not= i} \frac{x - x_j}{x_i - x_j}\Bigg) $$
How does the fraction \(\frac{x - x_j}{x_i - x_j}\) get broken down into Polynomial(\(\frac{-x_j}{x_i - x_j}, \frac{1}{x_i - x_j}\))?
Polynomial([a, b, c]) produces a polynomial \(a\textcolor{lightgray}{x^0} + b\textcolor{orange}x\textcolor{lightgray}{^1} + c\textcolor{orange}{x^2}\), so Polynomial([-xj / (xi - xj), 1.0 / (xi - xj)]) yields
$$\frac{-\textcolor{maroon}{x_j}}{\textcolor{teal}{x_i} - \textcolor{maroon}{x_j}} + \frac{1}{\textcolor{teal}{x_i} - \textcolor{maroon}{x_j}}\textcolor{orange}x = \frac{\textcolor{orange}x - \textcolor{maroon}{x_j}}{\textcolor{teal}{x_i} - \textcolor{maroon}{x_j}}$$
Ah, makes sense. It‘s easy to miss (for me, anyway), but the function \(f(x)\) isn’t the only polynomial here—the term within the \(\prod\) is itself also a polynomial.
At first, I thought it was just a clever trick, but the reason for factoring out the \(x\) without a subscript is basically that unlike everything else in the entire function, that \(x\) is not being iterated over by either the \(\prod\) (iterator \(j\)) or \(\sum\) (iterator \(i\)).
It’s the general indeterminate quantity \(\textcolor{orange}x\), and not \(\textcolor{teal}{x_i}\) or \(\textcolor{maroon}{x_j}\) (i.e., the x-coordinate of one of the \(n\) points that we provided to the function), which are actually part of the coefficients here. Incidentally, separating the static x from the dynamic xs was a stumbling block for me as I imagined how to tackle this.