Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

16-bit math look-up tables – the unexpected power of scaled-integer math

wilsonminesco.com

Post reply on HN
Print view View original

11–20 of 54 posts

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#11

Post by weinzierl »

quakeguy wrote: post #9
weinzierl wrote: post #8

Back in the day of 80286's and 80386's there was a popular Fractal generating software that did all calculations in fixed point arithmetic because PCs usually had no FPU back then. Fractint[1], the site has a certificate error, but otherwise works fine, even the software still gets updated from time to time. [1] https://fractint.org/

Used it to generate uniform random plasma fields for game textures. Great program!

With the right color map they made a nice sky with clouds. Color cycling them through a smooth full color map was also nice.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#12

Post by Mindless2112 »

shpx wrote: post #7

Related to 16 bit lookup tables, unum is a format for representing numbers as sets of number ranges as an alternative to floats. http://www.johngustafson.net/presentations/Unums2.0.pptx http://www.johngustafson.net/presentations/Unums2.0.pdf https://arxiv.org/pdf/1701.00722.pdf https://en.wikipedia.org/wiki/Interval_arithmetic

Unums are unlikely to gain much usage. Posits[1][2], also by Gustafson, are a more reasonable alternative to IEEE-754 floating point (but will still have a difficult time displacing IEEE-754, if they can at all).

[1] http://web.stanford.edu/class/ee380/Abstracts/170201-slides.... [2] https://www.youtube.com/watch?v=aP0Y1uAA-2Y

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#13

Post by jacobolus »

Animats wrote: post #2

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 ta…

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.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#14

Post by doubleunplussed »

jacobolus wrote: post #13
Animats wrote: post #2

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 ta…

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…

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.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#15

Post by jacobolus »

Animats wrote: post #4
kstenerud wrote: post #3

Earlier quoted context omitted.

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.

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.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#16

Post by jacobolus »

doubleunplussed wrote: post #14
jacobolus wrote: post #13

Earlier quoted context omitted.

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…

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.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#17

Post by MegaDeKay »

weinzierl wrote: post #10
Animats wrote: post #2

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 ta…

> 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 sp…

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.

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#18

Post by adrianratnapala »

jacobolus wrote: post #15
Animats wrote: post #4

Earlier quoted context omitted.

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.

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)?

Re: 16-bit math look-up tables – the unexpected power of scaled-integer math

#20

Post by adrianratnapala »

Mindless2112 wrote: post #12
shpx wrote: post #7

Related to 16 bit lookup tables, unum is a format for representing numbers as sets of number ranges as an alternative to floats. http://www.johngustafson.net/presentations/Unums2.0.pptx http://www.johngustafson.net/presentations/Unums2.0.pdf https://arxiv.org/pdf/1701.00722.pdf https://en.wikipedia.org/wiki/Interval_arithmetic

Unums are unlikely to gain much usage. Posits[1][2], also by Gustafson, are a more reasonable alternative to IEEE-754 floating point (but will still have a difficult time displacing IEEE-754, if they can at all). [1] http://web.stanford.edu/class/ee380/Abstracts/170201-slides.... [2] https://www.youtube.com/watch?v=aP0Y1uAA-2Y

Posits seem impressive. My only concern is the lack of NaNs seems like a bug rather than a feature.

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.

Post reply on HN