Live data from Hacker News

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

wilsonminesco.com

31–40 of 54 posts

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

#31

Earlier quoted context omitted.

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…

I think I would probably choose to have one NaN rather than +/-Infinity. Infinity itself is not a number -- it's just a special NaN.

Infinity is certainly a “number”; https://en.wikipedia.org/wiki/Projectively_extended_real_lin... https://en.wikipedia.org/wiki/Riemann_sphere

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

#32

Earlier quoted context omitted.

I think I would probably choose to have one NaN rather than +/-Infinity. Infinity itself is not a number -- it's just a special NaN.

Infinity is certainly a “number”; https://en.wikipedia.org/wiki/Projectively_extended_real_lin... https://en.wikipedia.org/wiki/Riemann_sphere

It's not a number if you are like me and say "a number is an element of a ring." (We're not talking about ordinals or cardinals, the subject being rationals, otherwise I might have a different definition.)

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.

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

#33

Earlier quoted context omitted.

>is the lack of NaNs seems like a bug rather than a feature. 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.

What if we want both NaN and infinity?

if you really want both, then either 1) use IEEE floats or 2) write your own data type, or 3) used a boxed data type, which is really the best solution for the dominant "missing data" abuse case anyways.

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

#34
For those who are interested, CORDIC (for COordinate Rotation DIgital Computer) is another technique from that era. It "is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions, typically converging with one digit (or bit) per iteration." See https://en.wikibooks.org/wiki/Digital_Circuits/CORDIC

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...

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

#35

Earlier quoted context omitted.

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…

Isaac Yonemoto has suggested the use of ±∞ as a NaN, and it seems to work exactly like NaN does other than x/±∞ = 0 whereas you want x/NaN = NaN. I hate hardware exceptions. If you have a code that occasionally hits a NaN, that means the code is still under development. You would never release such a code into the wild, because it clearly is not safe to use and has not done the basic blocking and tackling of guarding against input arguments that will prevent any indeterminate forms, square roots of negative values, etc.

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.

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

#36

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.

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.

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

#39
post #29

Earlier quoted context omitted.

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

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!

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

#40

Earlier quoted context omitted.

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…

Actually, posits handle NaNs already, by interrupting the calculation and doing whatever you have set up to handle the exception. What they do NOT do is represent Not-a-Number with a number. If a programmer is about to compute, say, x/y and in running the code it sometimes hits the case y = 0, then any competent programmer can write a conditional test to guard against that happening. It is not reasonable to ask computer hardware to magically continue to work somehow when it hits a bug in a program.

Think of it this way: posits have a signaling NaN but do not have a quiet NaN.

Post reply on HN