## Horner’s Method

October 25, 2016

It’s not like evaluating polynomial is something that comes up that frequently in the average programmer’s day. In fact, almost never, but it brings up a number of interesting questions, such as, how do we evaluate it very efficiently and how much of a simplification in the computation is actually a simplification?

The generic polynomial has the form

$a_0+a_1x+a_2x^2+a_3x^3+\cdots+a_nx^n$.

If we evaluate this naïvely, we end up doing $O(n^2)$ multiply and $O(n)$ additions. Even using the fast exponentiation algorithm, we still use $O(n \lg n)$ multiplies. But we can, very easily, get down to $O(n)$.

## Fractional Bits (Part III)

October 18, 2016

A long time ago, we discussed the problem of using fractions of bits to encode, jointly, values without wasting much bits. But we considered then only special cases, but what if we need to shift precisely by, say, half a bit?

But what does shifting by half a bit even means?

## Count like an Egyptian (Part III)

October 11, 2016

In previous posts, I’ve looked into unit fractions, also known as “Egyptian fractions”, fractions where the numerator is $1$ and the denominator $n$, some integer. We have noticed that finding good representation for a fraction $a/b$ as a sum of unit fraction is not as trivial as it may first seem. Indeed, we noticed that the greedy algorithm, the one that always pick the largest unitary fraction that does not exceed the rest as the next term, may lead to long series of unit fractions, sometimes with large denominators, even for simple fraction. For example,

$\displaystyle \frac{412}{1000}=\frac{103}{250}=\frac{1}{3}+\frac{1}{13}+\frac{1}{574}+\frac{1}{699563}$.

In a previous post, I suggested decomposing $a/b$ in an “easy way”, which was often better than the greedy algorithm. Surely, we can do better, but how?

## Yet Another Square Root Algorithm (part III)

October 4, 2016

Finding good, fast, and stable numerical algorithms is usually hard, even for simple problems like the square root, subject we’ve visited a number of times. One method we haven’t explored yet, is using the Taylor series. The Taylor series for $\sqrt{n}$ around $a$ is given by:

$\displaystyle \sqrt{n}=\sqrt{a}+\frac{1}{2}\frac{n-a}{\sqrt{a}}-\frac{1}{8}\frac{(n-a)^2}{a^{3/2}}+\frac{1}{16}\frac{(n-a)^3}{a^{5/2}}+\cdots$

Can we exploit that to compute efficiently, and with some precision, square roots?

## Weird binomial coefficients

September 27, 2016

The binomial coefficients find great many uses in combinatorics, but also in calculus. The usual way we understand the binomial coefficients is

$\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}$,

where $n$ and $k$ are integers. But what do you do with $\displaystyle \binom{\frac{1}{2}}{k}$?! Is it even defined?

September 20, 2016

Sometimes, you need to compute a function that’s complex, cumbersome, or which your favorite language doesn’t quite provide for. We may be interested in an exact implementation, or in a sufficiently good approximation. For the later, I often turn to Abramovitz and Stegun’s Handbook of Mathematical Function, a treasure trove of tables and approximations to hard functions. But how do they get all these approximations? The rational function approximations seemed the most mysterious of them all. Indeed, how can one come up with

$e^x \approx 1-0.9664x+0.3536x^2$

for $e^x$, for $0\leqslant x\leqslant\ln 2$?

Well, turns out, it’s hard work, but there’s a twist to it. Let’s see how it’s done!