Evaluating polynomials faster

I was just trying to find the roots of \(f(x) = 4 + 10x + 6x^2 + x^3\) by trying some values of x, when I came up with a better way of evaluating polynomials. Up till then I had been evaluating polynomials by summing the values of monomials. The better way is to rewrite the polynomial above as \(4 + x(10 + x(6 + x(1)))\), evaluate the innermost parenthesis first and work one's way out.

Let the degree of the polynomial be n. The complexity of finding the value of an mth degree monomial is \(\log(m+1)\). By summing the complexities from m = 0 to n we get \(\log 1+\log 2+\log 3+...+\log n+\log (n + 1)\), which is about the same as \(\log(n^n) = n\log n\). The new method on the other hand is linear in n because we only need to multiply and add once more every time n increases by one.

To compute f(-2), we start with the last coefficient, 1, and alternatingly multiply by x and add the coefficient to the left. Our partial results are: 1, -2, 4, -8, 2, -4, 0. Indeed, x = -2 is a root of the polynomial.

Inverting a pair of numbers

Suppose you have two numbers \(a \pm b\) both not equal to zero. Then
\[
(a \pm b)(a \mp b) = a^2 - b^2\\
\frac{1}{a \pm b} = \frac{a \mp b}{a^2 - b^2} = \frac{a}{a^2 - b^2} \pm \frac{-b}{a^2 - b^2}
\]

How to install South Park: The Stick of Truth

It's been almost a week since this game was released, so I bet you've heard all about it already. In this guide I'll show you what I did to install it in Steam on Ubuntu using Wine.

1. Install a new version of Wine. Open up a terminal and run the following:
• sudo add-apt-repository ppa:ubuntu-wine/ppa
• sudo apt-get update
• sudo apt-get install wine1.7
2. Install Steam.
• Download the installer.
• Run it by right-clicking the file and choosing "Wine Windows Program Loader"
• Follow the wizard.
3. Install the game.
• Purchase it through Steam.
• Let Steam download it.

Fixing some problems

• I got a (non-fatal) error saying something about the gnome-keyring. I fixed it by following the accepted answer at askubuntu.
• The textures wouldn't load. For example, the main menu background didn't show South Park: The Stick of Truth, but rather a couple of pink squares floating around. Also, my character was red. I fixed this by installing newer graphics drivers for my Intel graphics card.

• Follow the instructions at the Steam Support site
• Update your system (sudo apt-get update && sudo apt-get dist-upgrade)
• Reboot your computer.