Quadratic Equation

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.

Ad Saturation

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).

2. Certain websites. In particular I’m thinking of Wikipedia and Google two of the most used website today. Wikipedia has absolutely no ads and Google has intelligent ads. By intelligent ads I mean that when searching for “Earth’s diameter” on Google you don’t see any ads (versus searching for “exercise equipment” which brings up lots of ads). But on Yahoo they always have ads for any search. Also the Google home page is simple and devoid of ads versus the Yahoo page which is overly complicated and not ad free.

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.