16-bit math look-up tables – the unexpected power of scaled-integer math(wilsonminesco.com) |
16-bit math look-up tables – the unexpected power of scaled-integer math(wilsonminesco.com) |
For instructional purposes, here is a simple Python implementation that uses only adds and shifts in the inner loop, followed by a single scaled-multiply to finish it up: https://code.activestate.com/recipes/576792-polar-to-rectang...
I think the point of diminishing returns is 14-16 bits, but it's been a long time and I'd be happy to be proven wrong.
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).
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.
Fractint[1], the site has a certificate error, but otherwise works fine, even the software still gets updated from time to time.
http://www.johngustafson.net/presentations/Unums2.0.pptx
http://www.johngustafson.net/presentations/Unums2.0.pdf
[1] http://web.stanford.edu/class/ee380/Abstracts/170201-slides.... [2] https://www.youtube.com/watch?v=aP0Y1uAA-2Y
It's true that some programmers do the silliest things when faced with NaNs. But the fact is they are useful. You often want to do calculations over big matrices, where some elements simply don't have a mathematically defined answer (usually because of div0s but also because input data might have holes).
It would be a royal pain if the whole calculation stopped every time you had to add two infinities.
Babylonian multiplication and reciprocal tables are about 2500 years older.
For that matter, Hipparchus and Ptolemy’s chord tables are also centuries older, https://en.wikipedia.org/wiki/Ptolemy's_table_of_chords
well, actually ;) Adlib/Sound Blaster Yamaha OPL2 and OPL3 both used external Floating Point DACs (YM3014B,YAC512)
Ah shit, can't believe I missed this, all these years. Jack Crenshaw ie Let's Build a Compiler. Love that guy.
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...
I haven't written them up yet, but _valids_ are what you want if you are want software that can gracefully and mathematically handle the results that make floats generate a NaN. Think of the valid computing environment as the numerical debugging environment for posits. It's slower and ultra-careful and rigorous, but once you get your algorithm to the point where it never tries to color outside the lines, then switch to posits and go FAST.
Leaving a NaN in a number system designed for lean speed is a mixing of computing esthetics. Which do you want? Rigorous and careful and mathematical, or good enough, fast, and cheap? You have to make up your mind, because if you _mix_ the two esthetics in one number system, guess what: You get neither. It won't be fast, because it has to check for exceptions all the time, and it won't be mathematical because it keeps replacing correct answers with answers within its vocabulary (that is, it rounds). IEEE floats are a mixture of the two esthetics, and that is their fatal flaw.
I think this is a reasonable concern. I'll propose to John that we make there be an optional "mode" where the infinity token is treated as "NaN". In reality, this mode just amounts to "ignore NaN traps", because the way that it's done in my hardware models, it requires almost no extra hardware.
Think of it this way: posits have a signaling NaN but do not have a quiet NaN.
The projectively extended real line doesn't support adding infinity to itself, which is what the grandparent to your comment was talking about. The problem is that the projectively extended real line does not have both a positive and negative infinity.
> The extended complex numbers consist of the complex numbers C together with ∞.
It may be an "extended number", but it is not a number.
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 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 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.
Yes, there's a sqrt. (And another for gravity.) No trig needed or wanted.
In general, the boundary of the category of ideas (if you like, elements of some formal model) that can be called “numbers” is a very fuzzy and arbitrary one.
Some people might reject as “numbers” anything other than the counting numbers 1, 2, 3, 4. Others might allow “negative numbers” or ratios. Still others are happy to include quaternions or infinite strings of digits output by some computer program. Meh.
[1] https://en.wikipedia.org/wiki/Hyperreal_number [2] https://en.wikipedia.org/wiki/Dual_number
But, anyway, if you can claim infinity is a number because someone thought of the real projective line, I can say polynomials are numbers. Square matrices, too --- I think of square matrices as being big numbers; rank measures how invertible a big number is.
A stranger consequence of my definition is that a continuous real-valued function on a space X is a "number." If X is a single point, then such a function is the same as a real number. If X is a discrete set of n points, then the set of functions is R^n. If X is compact (I think that's sufficient?) then the maximal ideals in the set of continuous functions is in correspondence with X itself. This suggests that for any ring, one may imagine there to be a space that it is the functions of, whose points are the maximal ideals of that ring. For the ring of complex one-variable polynomials, the points correspond to C itself (the maximal ideals are generated by (x-c) for varying constants c). So, yeah, polynomials are numbers now.