Hacker News Reader

Comment by Animats | Hacker News Reader

Cute. However, unless you're using a CPU from the 6502 era, it's probably not worth the trouble for multiplication and division. Today's low-end CPUs have good multiply hardware, and for a few dollars more, you get a decent FPU. Trig functions, though, may be worth precomputing. The standard libraries for trig functions often grind their way out to far more precision than you need for graphics or control, and that takes time. Interpolating from a modest sized table can be faster.

View on HN

> However, unless you're using a CPU from the 6502 era, it's probably not worth the trouble for multiplication and division.

When we talk PC, fixed point math was popular a few generations longer than the 6502 era. The 6502 had no multiply and division instructions at all, and up to the 80386 there was only integer multiply and division and that was slow as molasses. Before the 80486 fixed point wasn't a matter of speed, it was a matter of survival (at least for graphics and such).

I remember my old 8086 PC turbo'd to 8 MHz would crawl along as it rendered the wireframe space shuttle demo image that came with Autocad. I somehow got my hands on an 8087 math coprocessor, plugged that bad boy in, and the difference was phenomenal. Good times.

indeed, I was using fixed point maths on PlayStation 1 games in the mid to late 90s. It was often responsible for the gaps you'd see between polygons on many PS1 games.

I was using it for z-80, game boy color homebrew. Getting down in the bits like this is.... bracing!

I remember doing a Gameboy Color game after working on a PS1 title. And even though I came from an 8 bit 6502 background (BBC Micro), going back to it was hell. 'Bracing' is an understatement! I couldn't imagine much worse these days.

Gaps were mostly a sign of sloppy developers and rushed schedules. Compare Tomb Raider 1 on both PC/PSX with Destruction Derby (reflections) and Gran Turismo 1/2 (polyphony).

Yes, there were ways to avoid it (shared vertex calculations), but the effect seen was mostly where there are two separate vertices that are supposed to be at the same position, aren't, because each vertex was positioned with different transformation matrices.

It’s usually possible to re-frame problems to not require trig functions at all.

For instance, you can represent rotations as unit magnitude complex numbers, compose them using complex multiplication, and trivially get whatever trig functions you want out. If you need to compress them for I/O, take the stereographic projection (requires 1 division per point for both forward and inverse transform) and then optionally reduce the precision of the result.

Construction of a unit complex number though, given an angle, requires trigonometry. Precomputing this and re-using it is identical to precomputing the sine and cosine of that angle and reusing them instead - the complex number itself doesn't simplify anything here other than storing both the sine and cosine in one variable.

The only time you need to start with an angle is if a human or other external system is feeding it to you, and the only time you need to convert to an angle is when you need to present the data to a human or other external system.

The point here is that you can usually get rid of evaluating transcendental functions in the middle of the number crunching part of your code, which is where you would care most about saving operations.

I don't think that's right. A rotation implies an angle. If it's not coming from a human, then you are either hard-coding an angle to rotate by, in which case you need to take sine and cosine of that angle to generate a complex number, or you're getting the rotation that is implied from some coordinates, hard-coded or otherwise. In which case, you need to normalise a complex number - still requiring a square root.

I don't think there's a way to do rotations without transcendental functions (or square roots) that isn't equivalent to merely precomputing the transcendental functions or square roots.

Maybe square roots are faster, in which case you have a point that avoiding transcendental functions is the way to go.

I think they're referring to quaternions. May require some trig to generate the initial quaternion, but then in your number crunching code you can multiply with other quaternions (representing rotation composition) and then even convert the result to a 3x3 rotation matrix, both with no trig. This is how game engines handle storing 3D rotation.

An example, a solar sailing toy: http://wry.me/t/gravity/gravity.html

Yes, there's a sqrt. (And another for gravity.) No trig needed or wanted.

We’re talking about possible representations of a rotation in the plane. The usual representation is “angle measure”, e.g. radians, degrees, or “binary radians”. This representation makes it easy to compose rotations (just add the angle measures), and the binary version is an efficient use of bits, but if you want to do anything else, e.g. rotate some arbitrary vector, then you need to do a bunch of transcendental function evaluations, which is computationally expensive.

I am recommending using the Cartesian (x, y) coordinate representation instead. This is often called a “complex number” x + iy on the “complex unit circle”, or you can think of it as (cosine, sine) if you prefer. Composition of rotations in this representation is still straight-forward: (a + ib)(c + id) = (ac – bd) + i(ad + bc).

If you need to compress this down to one number for transmission or storage, you can take the stereographic projection (“half-angle tangent”), (x, y) ↦ y / (x + 1), and optionally also reduce the precision. This saves you at least half the bits vs. storing the pair of coordinates, and is relatively inexpensive to compute (takes one division per point).

You are right that to normalize an arbitrary vector requires taking a square root. Fortunately, this doesn’t need to be done too often.

As an added bonus, this method generalizes much more easily than angle measure to representing higher-dimensional rotations and points on higher-dimensional spheres. For instance, I recommend using cartesian coordinates (or the stereographic projection for compression) instead of latitude and longitude for storing points on the 2-sphere such as geographical places. Many pieces of mapping software are constantly converting back and forth (implicitly or explicitly) between latitude/longitude vs. cartesian coordinates for computing distances, directions, and areas, finding intermediate points, applying 3-dimensional rotations, clipping shapes, and so on. This is slow and complicated vs. just using Cartesian coordinates as the internal representation.

It is usually unnecessary to compute the angle measure corresponding to a rotation unless communicating with a human. Angle measure is just one of several possible representations, and it’s only the most common because it gets taught to every child.

I don't quite agree. Complex analysis is more than powerful enough to recover the unit complex number corresponding to a specific angle without referencing any kind of trigonometry. Of course you'll have reconstructed the sine and cosine functions that way, but you don't need to use a single trigonometric function or theorem to get there.

In terms of implementation, what are you not quite agreeing with?

Except for the cache hit.

If you're interpolating and only need 16 bits of precision, you need only a small table. 32 or 64 entries should be enough for sine and cosine.

An example of the linear-interpolated lookup table approach using fixed-point math is the sine generation[0] in my music synthesizer. It generates a table of 1024 entries, then lerps between those. This gives you precision beyond the least perceptible audio error, and is pretty fast.

When I first wrote that code, I was targeting 32 bit ARM, with possibly very weak floating point units. These days, on the types of chips you'd see in phones (or computers in the $9-$40 range like rpi 3), the floating point calculation is _so_ fast (especially with simd) that the cost of the memory lookup starts dominating. So, the NEON implementation computes 4 sin values in a gulp, using a floating point polynomial approximation about the same precision as above[1].

[0] https://github.com/google/music-synthesizer-for-android/blob...

[1] https://github.com/google/music-synthesizer-for-android/blob...

It’s probably a generally better idea to use a polynomial approximation if you have a floating point unit; a degree 8 polynomial for sin(x) on the range [0, π/2] gets you to just about the limits of single precision floating point. If you only need about 4 digits of precision, you can use a degree 5 polynomial.

Couldn't you do better by only using the range [0, π/4] and noting that sin(x) = cos(x - π/2)?

Sure, then you can get away with an even smaller degree polynomial.

FWIW, Applesoft for the 6502 uses a 5th order poly.

Reply on news.ycombinator.com