We talked last time about the problem of summing the first $n$ consecutive integers. Here is another approach which demonstrates some different, but equally clever tricks. $\require{cancel}$

In high school, we learn that the difference of two squares can be computed by the formula $m^2 - n^2 = (m+n)(m-n)$. If this is unfamiliar, try expanding the right hand side and then simplifying.

Let's suppose for a moment that $m$ is the next number after $n$. We compute that:

$$ \begin{align} m^2 - n^2 &= (m+n)(m-n) \\ &= (2n + 1)(1) \\ &= 2n + 1 \end{align} $$

This formula holds for all $n$ whenever $m$ is the next number up. This means we can instantiate the formula with different values for $n$ like this:

$$ \begin{align} 6^2 - 5^2 = 2 \cdot 5 + 1 \\ 5^2 - 4^2 = 2 \cdot 4 + 1 \\ 4^2 - 3^2 = 2 \cdot 3 + 1 \\ 3^2 - 2^2 = 2 \cdot 2 + 1 \\ 2^2 - 1^2 = 2 \cdot 1 + 1 \\ 1^2 - 0^2 = 2 \cdot 0 + 1 \end{align} $$

This is where we get clever. We add vertically. Something interesting happens on either side of the equals sign.

read more...

There is a story that every math student should learn. It's about a mathematician named Gauss. One day, his school teacher wanted to keep the class busy for a long time so he could relax. So he gave the class an impossibly difficult task:

Add up all the numbers from 1 to 100.

The class got busy calculating. But not Gauss. After a few minutes, while most students were just beginning to struggle with the teens, Gauss was just finishing with writing down his final answer.

When he brought it to submit it, his teacher was furious with him for not taking the assignment seriously (and for interrupting his nap behind the desk).

We'll look to see how Gauss got his answer so quickly.

read more...

Regression analysis is a common technique for finding a best fit line through a set of data points. We'll illustrate how it works by showing a simple case involving one input feature.

read more...

Everyone has, at some point during their childhood, found themselves in a contest to name the largest number. It starts off with perhaps a hundred, or a thousand, then a million, a billion, a trillion. Perhaps the savvy youngsters will know about quadrilions or quintillions.

But at some point, we run out of words for numbers. The argument continues with one-upsmanship. Your friend names a number. You tack "plus one" onto the end. They come back with "plus two". Maybe some multiplication gets thrown in there ("a trillion trillion!").

The game gets boring pretty quickly, though. You decide it's time to pull out your trump card: infinity!

Surely, you've won. No one can top infinity. It's bigger than the biggest number, after all. Your friend will have to forfeit.

Or so you think. But they come right back at you: "Infinity plus one!"

read more...

Infinite lists

OCaml and Haskell are both statically typed functional programming languages. Their type systems are very similar. They both have function types, algebraic data types, higher-order types (list of things, maybe/option types, tuple types). They both support type variants of the Hindley-Milner type inference algorithm.

But in Haskell, one often heralded featured is that data types can be "infinite". Haskellers love to showcase this clever one-linear which produces the fibonacci numbers:

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

read more...

The Specs for Halt

We suppose the existence of a function called Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then Halt(f) returns true if the call to f() ever returns a value, and Halt(f) returns false if f() loops infinitely.

An important part of this assumption is that Halt(f) must always return true or false regardless of your choice of f. It must not itself loop.

read more...