The quadratic equation of the form $x^2 + ax + b = 0$ is one of the simplest nonlinear problems in one variable. The method I use for solving it can also be applied to the cubic and quartic equations but of course not the quintic.

Let $e_1 \textrm{ and } e_2$ be two (not necessarily different) solutions to $x^2 + ax + b = 0$. By the fundamental theorem of algebra $(x - e_1)(x - e_2) = x^2 + ax + b$. Multiplying out $x^2 -(e_1 + e_2) x + e_1e_2=x^2 + ax + b$. So $e_1 + e_2 = -a \textrm{ and } e_1e_2 = b.$ This is a non-linear system of equations in two variables.

Note that ${(e_1 - e_2)}^2 = e_1^2 + e_2^2 -2e_1e_2$ which is equal to ${(e_1 + e_2)}^2 - 4e_1e_2 .$ Thus $e_1 - e_2 = {(a^2 - 4b)}^{1/2}$ Which easily yields the solution $e_1 = -a/2 +- {(a^2 - 4b)}^{1/2}.$

It’s a fun exercise. The trick is writing the square of $e_1 - e_2$ and also assuming you already have two solutions.

Have we reached a local temporal maximum for ads? As you well know, ours is an ad driven world. Everywhere you look there are ads. This phenomenon has gradually come to pass in the last century. Especially now in the online world there are ads everywhere.

But I’ve noticed that in the last couple years there are a couple places where the prevalence of ads has decreased.

1. TV, the number of ads on TV hasn’t decreased but we now have DVR’s which accomplish the same purpose. I almost never watch live TV because you have to wait through the ads. It will be interesting if the number of ad free channels increases in the future because everyone has DVR’s (so TV ads would be pointless because everyone would fast forward through them).

So there is my evidence that all is not hopeless, there have been at least a couple bright spots in keeping the world from being overrun with ads 🙂

Listing All Subsets

A common problem in discrete math is listing all subsets for a given set say $S.$ There’s a trivial recursive algorithm for listing all subsets but I want to give an algorithm for listing subsets when $S$ is small.

Lets try out the algorithm for the set $S=\{a,b\}.$

The subsets are $\{\}, \{b\}, \{a\}, \{a,b\}.$

Now look at the numbers 0, 1, 2, 3 in binary: $00, 01, 10, 11.$

We can say that 00 represents the set $\{\}$, 01 the set $\{a\}$, 10 the set $\{b\}$ and 11 the set $\{a,b\}$. Remember to read the binary numbers from right to left. Given a binary number the set it represents corresponds to the one’s in the binary number, so if the binary number has a one in the 10th bit (where the 10th bit is the 10 character from the right end of the number) than the 10th element in the set $S$ is included in the subset.

This does mean we need an ordering for the set $S.$ But the ordering is only used when listing out the subsets so it’s doesn’t violate the condition that sets aren’t ordered (if we wanted to list the subsets of an infinite set this could be a problem).

Now it’s obvious how to list the subsets of a set $S.$

1. Create an array, A, of all the numbers from 0 to $2^{|S|} - 1.$

2. Iterate over the array A and for each element, n, of A list out the corresponding subset of $S.$ If n = 1 then the corresponding subset is $\{a\},$ where $S = \{a,b\}.$

Use bitwise arithmetic to retrieve the individual bits from a number. For getting the nth bit from a number, x, in java, c, etc. do “x & pow(2,n)”. If x has a 1 in the nth then “x & pow(2,n) == 2n” otherwise it’s == 0.

Thats it. Happy coding.