Yes? No? Maybe? (Part I)

March 20, 2018

Initializing arrays, or any variable for that matter, is always kind of a problem. Most of the times, you can get away with a default value, typically zero in C#C++, but not always. For floats, for example, NaN makes much more sense. Indeed, it’s initialized to not a number: it clearly states that it is initialized, consciously, to not a value. That’s neat. What about integers? Clearly, there’s no way to encode a NaI (not an integer), maybe std::numeric_limits::min(), which is still better than zero. What about bools?

Bool is trickier. In C++, bool is either false or true, and weak typing makes everything not zero true. However, if you assign 3 to a bool, it will be “normalized” to true, that is, exactly 1. Therefore, and not that surprisingly, you can’t have true, false, and maybe. Well, let’s fix that.

Read the rest of this entry »


Paeth’s Method (Square Roots, Part VII)

March 13, 2018

In Graphics Gems [1], Paeth proposes a fast (but quite approximate) method for the rapid computation of hypotenuse,

\displaystyle h=\sqrt{x^2+y^2}.

The goal here is to get rid of the big bad \sqrt{} because it is deemed “too expensive”—I wonder if that’s still actually true. First, he transforms the above equation:

\displaystyle h=\sqrt{x^2+y^2}

\displaystyle =\sqrt{x^2\left(1+\frac{y^2}{x^2}\right)}

\displaystyle =x\sqrt{1+\frac{y^2}{x^2}}.

This leaves us with the special case $\sqrt{1+u^2}, for which we can find the Taylor series

\displaystyle \sqrt{1+u^2}=1+\frac{1}{2}u^2-\frac{1}{8}u^4+\cdots

The numerators are given by A002596 and the denominators by A046161. So we can rewrite the whole thing as

\displaystyle x\sqrt{1+\frac{y^2}{x^2}}=x\left(1+\frac{1}{2}\left(\frac{y}{x}\right)^2-\frac{1}{8}\left(\frac{y}{x}\right)^4+\cdots\right).

*
* *

We’ll now try to get away with only a few terms of the series, and hope the precision isn’t too damaged. say we keep only the first two terms, how does it compare to other methods?

Let’s break down the graph:

  • Blue: Circle of radius 10, the real hypotenuse;
  • Green: True radius, 10;
  • Dotted purple: Archytas, 3 iterations;
  • Purple: Bakhshali’s method;
  • Red: Paeth’s method.

Since Paeth’s method works well if y<x, we may tweak it a bit. Letting

Q(x,y)=x\left(1+\frac{1}{2}\left(\frac{y}{x}\right)^2-\dots\right),

then letting

P(x,y)=\begin{cases}  Q(x,y)&\textrm{if~}y<x,\\  Q(y,x)&\textrm{otherwise}.  \end{cases}

The imprecision is maximal when x\approx{y}, or when the hypotenuse is at an angle of about 45 degrees.

*
* *

Originally, this hack was for considered for fast collisions/proximity testing. If you absolutely need a circular (or spherical) region, you need a square root, but that’s not the only option:

  • L_1 metric, which is just the sum of absolute values |x|+|y|;
  • L_2 metric, the usual euclidean distance;
  • L_\infty metric, which is \max(x,y).

The L_2 metric requires the square root, but the others are (if branches are cheap), rather inexpensive to compute—but they have counter-intuitive behavior. They might be useful for a first faster check, followed by Paeth’s method, followed by a full test.


[1] lan W. Paeth — VIII.5 A Fast Approximation to the Hypotenuse — in : Andrew Glassnet, ed., Graphics Gems, Morgan Kaufmann (1993), p. 427– 431


Square roots (Part VI)

February 20, 2018

I’ve discussed algorithms for computing square roots a couple of times already, and then some. While sorting notes, I’ve came across something interesting: Archytas’ method for computing square roots.

Archytas’ method is basically the old Babylonian method, where you first set

a=1,

b=n,

and iterate

\displaystyle a'=\frac{a+b}{2},

\displaystyle b'=\frac{n}{a'}=\frac{2n}{a+b},

until desired precision is achieved (or the scribe is exhausted).

Read the rest of this entry »


#include <the_usual>

January 9, 2018

Recently on Freenode channel ##cpp, I saw some code using an include-all-you-can header. The idea was to help beginners to the language, help them start programming without having to remember which header was which, and which headers are needed.

Is that really a good idea?

Read the rest of this entry »


Taylor Series

December 19, 2017

A Taylor series for a function f(x) around x_0 that is n times differentiable is given by

\displaystyle f(x) \approx f(x_0)+f'(x_0)(x-x_0)+\frac{f''(x_0)}{2}(x-x_0)^2+\frac{f'''(x_0)}{6}(x-x_0)^3+\cdots

or

\displaystyle f(x) \approx \sum_{i=0}^{n} \frac{f^{(i)}(x_0)}{i!}(x-x_0)^i,

where f^{(i)}(x) is the ith derivative of f at x.

Have you ever wondered where the coefficients in a Taylor series come from? Well, let’s see!

Read the rest of this entry »


Building a large text corpus (Part I)

December 12, 2017

Getting good text data for language-model training isn’t as easy as it sounds. First, you have to find a large corpus. Second, you must clean it up!

Read the rest of this entry »


Reinventing the Wheel (or not)

December 5, 2017

About a week ago, some dude drops on IRC that he’s beat memcpy “by a lot”. That’d be interesting, except that we couldn’t get neither code nor test methodology out of him. But, how hard can making a better memcpy be? Turns out, harder than you think!

If you think this is a typical case of “reinventing the wheel”, I mostly agree with you. But while reinventing will be hard, can improvements be made?

Read the rest of this entry »