2013 paper on Right-sizing precision

[jim.bra...@ieee.org]

Am wondering about you current stance on the the use of an exact/inexact bit?

(slides 30 & 31)

[John Gustafson]

If you use a pair of posits where the last bit is the exact/inexact bit, you get what I call a "valid", capable of expressing closed, open, and half-open intervals, as well as the extended reals with ±∞, and the empty set. Overflow and underflow are handled very logically as the interval between the largest magnitude numbers and ±∞, or between zero and the smallest magnitude numbers. They can then do all the things described in The End of Error: Unum Computing, but the precision is fixed. Fixed precision makes them more hardware-friendly, but less able to economize by shrinking the representation to match the knowledge about the bound.

In the marketplace of ideas, perfect computation with real numbers always seems to lose to "good enough and fast" computation. There is a tiny group of us who feel otherwise, but I have to acknowledge the reality that computer users seldom want to pay the price of a guaranteed bound on the rounding error. That's why my next book will focus on making rounded arithmetic as good as it possibly can be, with only a chapter or two on valids.

I still see papers coming out on Type II unums and SORNs (Sets Of Real Numbers), which are even more powerful than intervals since they can represent disconnected sets of real numbers, yet still look like machine arithmetic for hardware.

IBM got a lesson back in the 1990s when they introduced their ACRITH environment that guaranteed floating-point answers correct to half a unit in the last place (0.5 ULP), which is like doing an entire computing task with exact arithmetic and then rounding. It ran about three times slower than normal float arithmetic. It didn't sell, and IBM dropped it as a product offering.

Since the IEEE 1788 Standard was finished for interval arithmetic (closed intervals only, and no exact dot product accumulator), there have been no takers. About ten years, and no commercial product offerings.

It seems to be tough to get correct arithmetic on real numbers to be a mainstream idea, and in demand!

John 

On Nov 5, 2023, at 7:52 PM, 'jim.bra...@ieee.org' via Unum Computing <unum-co...@googlegroups.com> wrote:

Am wondering about you current stance on the the use of an exact/inexact bit?

(slides 30 & 31)

--
You received this message because you are subscribed to the Google Groups "Unum Computing" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unum-computin...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/0b30a52d-2358-4b58-8b10-74a25a3a2da6n%40googlegroups.com.

[jim.bra...@ieee.org]

"It seems to be tough to get correct arithmetic on real numbers to be a mainstream idea, and in demand!"

It seems the entire commercial world is bent on least expensive product, with no room for style, grace or long term quality.

I think I am correct in saying that unbiased rounding of whatever variety uses alternating open on both ends /closed on both ends intervals?  This is visually appealing and makes the round-to-nearest rule a consequence.

The last open interval (in magnitude) then "encompasses infinity?  And the closed interval at the other end encompasses zero, ugh from both sides?

While pondering how to encompass exact and inexact numbers without a specific flag bit that takes a bit from the fraction/mantissa,

the thought occurred that exact numbers are relatively rare compared to in-exacts and might fit into the code space of 754 NaNs.

Such does not seem possible with Posits as there is no unused encoding space?

Currently struggling to make sense of all the different round-to-odd meanings.

 Today happened upon Sylvie Boldo's very recent paper:

https://hal.science/hal-04095151 

which looks forward to reexamining floating point implementations.

[John Gustafson]

Replies embedded.

On Nov 6, 2023, at 11:35 AM, 'jim.bra...@ieee.org' via Unum Computing <unum-co...@googlegroups.com> wrote:

"It seems to be tough to get correct arithmetic on real numbers to be a mainstream idea, and in demand!"

It seems the entire commercial world is bent on least expensive product, with no room for style, grace or long term quality.

I think I am correct in saying that unbiased rounding of whatever variety uses alternating open on both ends /closed on both ends intervals?  This is visually appealing and makes the round-to-nearest rule a consequence.

Yes, you can think of unbiased (banker's) rounding that way. Alternating [  ](  )[  ](  )… where the square brackets enclose an encoding ending in a 0 bit and the odd ones enclose an encoding ending in a 1 bit. The applies to both posits and the default rounding mode of IEEE 754 floats.

The last open interval (in magnitude) then "encompasses infinity?  And the closed interval at the other end encompasses zero, ugh from both sides?

No, and this is important. Something like –log(0) is ∞, but if you do something like square the largest real number you can represent (maxReal), it is incorrect to call that ∞. It is in the open interval (maxReal, ∞), which says "the number is finite but too large to represent." That tends to be sticky; for example, if you subtract maxReal from that interval, you get (0, ∞) and the result still conveys to the user that an overflow happened.

Absent rigorous intervals, the philosophy of posit computing environments is to avoid overflow and underflow by debugging the code, not expect the hardware to be constantly assigned the task of looking for such problems,.

While pondering how to encompass exact and inexact numbers without a specific flag bit that takes a bit from the fraction/mantissa,

the thought occurred that exact numbers are relatively rare compared to in-exacts and might fit into the code space of 754 NaNs.

The unum system is to have half the numbers exact and the other half the open interval between exacts, and then use a pair of them (a "ubound", in the parlance of The End of Error) to delimit the interval. I tried to make unum arithmetic an upward-compatible extension of IEEE 754 in that book, and later realized that we're way overdue for a fresh approach to the representation of real numbers… IEEE 754 is outdated, not well-followed by vendors, and much of the language of the standard is a non-mathematical mess. (For example, negative and positive zero should return "true" if compared for equality, and compares should return "true" if the test is (negative zero) < (positive zero) but "false" if the test is (positive zero) < (negative zero). That's the kind of thing that makes me facepalm.

Such does not seem possible with Posits as there is no unused encoding space?

It's all worked out and described in the section on Valids in this document, Section 3.6:

Currently struggling to make sense of all the different round-to-odd meanings.

 Today happened upon Sylvie Boldo's very recent paper:

https://hal.science/hal-04095151 

which looks forward to reexamining floating point implementations.

That's an excellent paper, and Sylvie Boldo has made some major contributions to the field of floating-point representation. I believe she deserves most of the credit for figuring out how to use round-to-nearest-odd to eliminate double rounding errors. We use that technique to create math libraries for posits that work for all precision from 2 bits to 32 bits in SoftPosit.

Best,

John

 

On Monday, November 6, 2023 at 10:40:17 AM UTC-6 johngustafson wrote:

If you use a pair of posits where the last bit is the exact/inexact bit, you get what I call a "valid", capable of expressing closed, open, and half-open intervals, as well as the extended reals with ±∞, and the empty set. Overflow and underflow are handled very logically as the interval between the largest magnitude numbers and ±∞, or between zero and the smallest magnitude numbers. They can then do all the things described in The End of Error: Unum Computing, but the precision is fixed. Fixed precision makes them more hardware-friendly, but less able to economize by shrinking the representation to match the knowledge about the bound.

In the marketplace of ideas, perfect computation with real numbers always seems to lose to "good enough and fast" computation. There is a tiny group of us who feel otherwise, but I have to acknowledge the reality that computer users seldom want to pay the price of a guaranteed bound on the rounding error. That's why my next book will focus on making rounded arithmetic as good as it possibly can be, with only a chapter or two on valids.

I still see papers coming out on Type II unums and SORNs (Sets Of Real Numbers), which are even more powerful than intervals since they can represent disconnected sets of real numbers, yet still look like machine arithmetic for hardware.

IBM got a lesson back in the 1990s when they introduced their ACRITH environment that guaranteed floating-point answers correct to half a unit in the last place (0.5 ULP), which is like doing an entire computing task with exact arithmetic and then rounding. It ran about three times slower than normal float arithmetic. It didn't sell, and IBM dropped it as a product offering.

Since the IEEE 1788 Standard was finished for interval arithmetic (closed intervals only, and no exact dot product accumulator), there have been no takers. About ten years, and no commercial product offerings.

It seems to be tough to get correct arithmetic on real numbers to be a mainstream idea, and in demand!

John 

On Nov 5, 2023, at 7:52 PM, 'jim.bra...@ieee.org' via Unum Computing <unum-co...@googlegroups.com> wrote:

Am wondering about you current stance on the the use of an exact/inexact bit?

(slides 30 & 31)

--
You received this message because you are subscribed to the Google Groups "Unum Computing" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unum-computin...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/0b30a52d-2358-4b58-8b10-74a25a3a2da6n%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Unum Computing" group.
To unsubscribe from this group and stop receiving emails from it, send an email to unum-computin...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/01ae04e6-aaee-428d-b0e3-b7342d5de3c5n%40googlegroups.com.

[Angelo Bulfone]

I've seen arguments that every IEEE float really always represents the range of values around it rather than the exact value. This would make "∞", "-∞", "0", and "-0" really be the intervals between ∞ and the highest magnitude "finite" floats and between 0 and the lowest magnitude "non-zero" floats. This makes overflow and underflow feel much more reasonable, but also that all 4 values are horribly misnamed, or at least that the two "zeros" should be called "infinitesimals." A minor problem with this system though is that with s = smallest positive subnormal, "0" being the interval from 0 to s and "-0" being the interval from -s to 0, which interval does the actual additive identity belong to? They're both equally close, equally imprecise, and equally even. The only reason to choose "0" is really a positivity bias.

With this, "infinity" and "0" start looking more like max_pos and min_pos, especially if the right-most bit is treated as a ubit, while the posit value 0 simply doesn't have a unique corresponding float value. With how min_pos * 2 = min_pos, min_pos + x = x for any non-zero x, min_pos * x = min_pos for any x less than 1, and max_pos / 2 = max_pos, they really do start to look like overflow and underflow, but without explicitly specifying them as exceptional cases.

Since min_pos and max_pos kind of emulate underflow and overflow in many ways, the other floating point flags that proponents of IEEE seem to want but are also locked away in a special CPU register are the illegal operation flag, divide-by-zero flag, and inexact flag. Illegal operation is redundant since you can always just compare a posit with NaR, which is sticky and doesn't go away from most operations. Divide-by-zero they way it happens in IEEE doesn't happen since posits don't try to claim the result of "underflow" is "0", and the actual 0 gives NaR when used as a divisor. The last flag is the inexact flag, set when an operation needed to round which... hey that's just the ubit! An N-1 bit posit with a ubit effectively encodes all the information normally hidden away in flags. This is why I'm interested in seeing posits with a ubit used outside the context of valids, but they would require different rounding behavior than both standard N-bit posits and valids with 2 N-1 bit posits with ubits.

I'm also quite curious how to implement valids or these modified posits efficiently. While intervals require twice the space to store, you might be able to get away with replacing a 32-bit float with a valid composed of 2 15+1-bit posits to keep the total storage space the same at the cost of precision and dynamic range (and also a unique value to pretend that it is). This is on top of posits just being much harder to decode and encode than floats inherently due to effectively being a compressed representation of a modified (generally more sane) float format. Encoding and decoding require implementing this compression and decompression logic in hardware.

[John Gustafson]

Just a reminder that when you bring in interval representation, you also need the skill set to prevent intervals from expanding exponentially so that you don't wind up with [–∞,∞] for your answers. People who try intervals as a drop-in substitute for floats usually get burned by this and don't try them again. 

So few people who do technical computing actually have a decent understanding of numerical analysis… and an even smaller subset of those have any idea how to deal with The Wrapping Problem and The Dependency Problem, the two main causes of exponential growth of interval bounds. The Karlsruhe people pretty much conquered both problems in the 1980s but much of their work seems to have been forgotten and it's pretty sophisticated stuff. They find the conditions under which a basic block can be converted to a lower-triangular system of equations and then build a contractive map, an operator with eigenvalues all less than 1 so that repeated application is guaranteed to shrink an interval bound down to ±0.5 ULP.

The End of Error: Unum Computing contributed the idea that both The Wrapping Problem and The Dependency Problem grow linearly instead of exponentially if you always use single unums (not ranges larger than an ULP) as inputs. It's an approach that does not require mathematical sophistication but instead exploits the brute force of massive parallelism that wasn't available to the Karlsruhe people.

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/a921f724-4580-439c-b44b-6379b27c135en%40googlegroups.com.

[jim.bra...@ieee.org]

|>

|>A minor problem with this system though is that with s = smallest positive subnormal, "0" being the interval from 0 to s |>and "-0" being the interval from -s to 0, which interval does the actual additive identity belong to? They're both equally |>close, equally imprecise, and equally even. 

The solution? is to merge the two intervals that then surrounds exact zero and use the other code for NaR ?

[John Gustafson]

I'm completely confused by this. There are no subnormal numbers in posits, and certainly no negative zero. The additive identity is the exact number zero, as it should be, whether using posits or valids. 

In valids, the interval (0, minReal) is used to express underflow of positive numbers, and (–minReal, 0) to express underflow of negative numbers. Neither serves as an additive identity because (0, minReal) + (0, minReal) would be (0, x) where x is the smallest posit greater than minReal.

In valids, indeterminate answers are expressed as the empty set… I think the convention for ∅ is that the valid pair is the valid for (0, minReal) for the beginning and exact 0 for the end, like an impossible step backwards. If you do something like zero divided by zero, it actually is expressible as ℝ⁺, where the convention is to use the valid pair where the first element is the one that serves as NaR for posits (1 followed by all 0 bits; think of it as exact –∞) and the second element is the one for

(maxReal, ∞), which is all 1 bits. That maps to the smallest 2's complement integer and the largest 2's complement integer.

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/9311af09-a9dc-4db2-a32f-d4d34863f403n%40googlegroups.com.

[jim.bra...@ieee.org]

My mistake, thinking my version of subnormals in 754 applies to Posits

[Angelo Bulfone]

Maybe my message was unclear. Posits and Valids do have true 0s. It's that IEEE floats do not. IEEE "+0.0" from what I can tell behaves more like the posit min_pos and valid [0, min_pos) than it does like the posit 0 or valid [0, 0]. On the other end, IEEE +Inf seems to behave more like the posit max_pos and valid (max_pos, NaR] (or maybe (max_pos, NaR)) than like the posit NaR.

Huh. I'm a little surprised by the suggested valid for ∅. I would expect it to be [NaR, NaR], since typically an upper bound less than the lower bound implies wrapping around infinity. This technically should imply many different representations for ℝ⁺, though [NaR, NaR) (or int_min .. int_max) feels the most appropriate. The valid for ℝ (not extended) seems like it should only have one representation though as (NaR, NaR) (or int_min+1 ..  int_max). This probably has something to do with treating int_min as NaR even as a valid bound rather than infinity?

[John Gustafson]

I like your idea of [NaR, NaR} for ∅. That's more logical than what I suggested. Though it does mean we can only express (–∞,∞) and not [–∞,∞]. Hmm…

If you go through the IEEE Std 754 looking at every statement that pertains to signed zero, you find no mathematical consistency. Sometimes both are exact zero. But the reciprocal of –0 is –∞ and the reciprocal of +0 is +∞. What should –0 minus +0 be?

This is all the result of the choice John Palmer made in the late 1970s in designing the i8087 coprocessor. It was common back then to just carve up the bit fields and assign each a meaning, rather than consider something more like Dedekind cuts as you read each bit from MSB to LSB the way posits do. When Kahan was hired by Intel, he was tasked with justifying the i8087 design choices, and I'm sure he struggled with defending negative and positive zero. Kahan finally came up with an application to functions with branch cuts in the complex plane along the negative x-axis, like log and square root. But that application means treating +0 as (0, minReal) and –0 as (–minReal,0) which are completely different mathematical entities from zero.

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/d35f6cb3-a153-40e9-a1a5-0eec85d734a5n%40googlegroups.com.

[Angelo Bulfone]

Infinity isn't a ℝeal number, and IEEE infinity is more like the set of all ℝeal numbers larger than the largest representable finite float, so not having a representation for [-∞, ∞] doesn't seem like that big of an issue if you ask me.

-0 - -0 would be like -min_pos - min_pos, which rounds to min_pos, and for IEEE, to -0. The better question is what +0 + -0 would be. The simple answer is the posit 0, which... isn't an IEEE float. This is what I meant by IEEE lacking a true additive identity. Officially, I think -0 + +0 is supposed to evaluate to -0. Also while treating -0 and +0 as separate intervals or as infinitesimals makes more sense mathematically (at least to me) than actually "negative zero", it does make the gap or overlap between them and the fact that they're supposed to evaluate as equal to each other more jarring.

[John Gustafson]

If a finite number is divided by an interval that contains 0, the result will be [–∞,∞], It happens all the time in interval arithmetic. So we need a way to represent it if valids are used the way interval arithmetic is used presently.

There will also be situations where we need to express (–∞,∞), [–∞,∞), and (–∞,∞]. They are particularly useful in expressing the domains of functions and then being able to prove properties. For example, suppose

f(x) = 1 / (1 + x²).

Does this have any roots for real x? You can plug in x = (–∞,∞). Square that to get [0,∞). (Which shows why you sometimes need half-open intervals.) Add 1 to get [1,∞). Take the reciprocal and you get (0,1], proving there are no zeros for real x. But if you allow extended reals and set x = [–∞,∞], you wind up with f(x) = [0,1] so there are roots… at ±∞.

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/d1c869d7-7aa1-4289-9754-20ac0b8a5cbfn%40googlegroups.com.

[MitchAlsup]

On Wednesday, November 8, 2023 at 4:23:24 PM UTC-6 johngustafson wrote:

I like your idea of [NaR, NaR} for ∅. That's more logical than what I suggested. Though it does mean we can only express (–∞,∞) and not [–∞,∞]. Hmm…

If you go through the IEEE Std 754 looking at every statement that pertains to signed zero, you find no mathematical consistency. Sometimes both are exact zero. But the reciprocal of –0 is –∞ and the reciprocal of +0 is +∞. What should –0 minus +0 be?

{pedantic mode==ON} you forgot the raising of overflow {pedantic mode==OFF}

It is my considered opinion that IEEE 754 should have had 3 zeros  {-0, 0, and +0} where -0 represents underflow of a negative calculation, +0 represents underflow of a positive calculation, an that 0 represents a real zero. I would reserve the following encodings of 80...01 as -0 and 00...01 as +0 decreasing the denorm space by 2 (essentially useless values carrying no precision)  that would be easy to test for in HW.

But that ship sailed oh so long ago.....

I might note that MAX( -0, +0 ) is defined to be +0 ('2019) and that MIN( -0, +0 ) is defined to be -0 to sanitize the total order intrinsic.

-0 - +0 should end up being -0; since when you subtract a positive number (+0) from another number the result is "smaller" (in some hand waving sense wrt signed 0s) and -0 (from the total order intrinsic) is smaller than +0 (even though they compare as the same value--except when "x == -x" .)

This is all the result of the choice John Palmer made in the late 1970s in designing the i8087 coprocessor. It was common back then to just carve up the bit fields and assign each a meaning, rather than consider something more like Dedekind cuts as you read each bit from MSB to LSB the way posits do. When Kahan was hired by Intel, he was tasked with justifying the i8087 design choices, and I'm sure he struggled with defending negative and positive zero.

He also had trouble grappling with projective versus affine infinities--luckily only 1 remains.....

Mitch

 

Kahan finally came up with an application to functions with branch cuts in the complex plane along the negative x-axis, like log and square root. But that application means treating +0 as (0, minReal) and –0 as (–minReal,0) which are completely different mathematical entities from zero.

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/d35f6cb3-a153-40e9-a1a5-0eec85d734a5n%40googlegroups.com.