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


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

Random Points on a Sphere (Generating Random Sequences III, Revisited)

February 27, 2018

While searching for old notes—that I haven’t found anyway—I returned to an old blog entry and I thought I was kind of unsatisfactory, with be best part being swept under the carpet with a bit a faery dust, and very handwavingly.

So let’s work-out how to uniformly distribute points on a sphere in a more satisfactory fashion.

Read the rest of this entry »

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



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 »

Unary numbers.

February 13, 2018

A positional number system needs a base that is either greater than one, or smaller than minus one—yes, we can have a negative base for a number system. The system, however, seems to break down if the base we chose is base 1.

If the base is 1, then there are no permissible digits since the digits d, in a base b system, must be 0\leqslant{d}<b. But we can still represent numbers using just 1s. That's the unary numeral system, and numbers are just represented as repeated 1s. 15? Fifteen ones: 111111111111111. Operations? Not very complicated, just… laborious.

Read the rest of this entry »

Elementary Automata (Generating Random Sequences XI)

February 6, 2018

So 3-cells context elementary automata seem too “self-correcting” to be useful pseudo-random generators. What if we fixed that boundary problem and have the automaton run on a cylinder (with both end joined)? What if we augment the context from 3 to 5 cells?

Read the rest of this entry »

Elementary Automata (Generating Random Sequences X)

January 30, 2018

I was rather discontented with last week’s post results. Most automata seemed to produce self-correcting patterns, even when seeded randomly—one could argue that rand() isn’t the strongest random generator, but that wasn’t the problem. No, indeed, most automata exhibit self-correcting behavior, forming the same self-similar pattern, or worse, the same periodic pattern.

So I made a few more experiments with random seeds and larger images. The code isn’t very complicated and isn’t of interest in itself, but it reveals a couple of interesting things.

Read the rest of this entry »

Elementary Automata (Generating Random Sequences IX)

January 23, 2018

A while ago, Wolfram (re)introduced elementary cellular automata, a special case of cellular automata that lives in one dimension. One cutesy aspect of these automata is that the rules are easy to describe and number. As any automata, it is given a context, a region of interest, and gives an output depending on the context. For example, we can have the rules:

Context output
000 1
001 0
010 1
011 0
100 1
101 0
110 1
111 1

The output column can be viewed as a number, in this case 11010101, 0xd5, or 213. This is rule 213.

It may be tempting to use those to generate chaos, noise, and random numbers. But is it that a good idea?

Read the rest of this entry »