Formula to compute the approximate decimal precision

[Alessandro Astone]

As posits have dynamic precision, I would like to be able to compute how many decimals of accuracy i can expect within a specific number range.

For example, how may I compute the minimum decimal precision of a Posit16 (defined as per the latest spec with 2 bits of exponent) in the range (a,b)? And how about generalized for size N?

[John Gustafson]

Alessandro,

I see no one is responding, so let me give you a quick response and I'll send a more elaborate and complete one later.

You want to convert a posit value to a decimal character string with the minimal number of decimals such that it always converts back to the original posit. As the Posit™ Standard (2022) states, 5 decimals suffice for 16-bit standard posits (eS = 2), 10 decimals for 32-bit posits, and 21 decimals for 64-bit posits.

However, as you've discovered, this is overkill outside the region of highest accuracy. Also, only those examples are given because they had to be worked out by hand and we were not able to find a general formula. If you can find the general formula, please let us know! I recall discovering non-obvious corner cases that didn't work.

The principle is this: Use the smallest number of decimals such that the ±0.5 ULP for those decimals is smaller than the ±0.5 ULP for the binary significand in the posit. Put another way, the interval [decimal – 0.5 ULP, decimal + 0.5 ULP] must contain only one posit value. That assures it will convert back correctly.

The number of significant bits in a posit is easily obtained by taking the floor of the log base uSeed of the absolute value of the number the posit represents. That's sloppy, but I think you get what I mean. Or just count leading zeros or leading ones to find the regime length. That tells you the number of bits available to represent the fraction and that gives you the binary ULP width, and that in turn tells you how many decimals you need.

More later.

John

On Jul 11, 2023, at 2:46 AM, Alessandro Astone <ales....@gmail.com> wrote:

As posits have dynamic precision, I would like to be able to compute how many decimals of accuracy i can expect within a specific number range.

For example, how may I compute the minimum decimal precision of a Posit16 (defined as per the latest spec with 2 bits of exponent) in the range (a,b)? And how about generalized for size N?

--
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/f5259246-d22d-4689-87ad-2dd0f94c9948n%40googlegroups.com.

[Job van der Zwan]

On Wednesday, 12 July 2023 at 03:45:50 UTC+2 johngustafson wrote:

You want to convert a posit value to a decimal character string with the minimal number of decimals such that it always converts back to the original posit.

Out of curiosity: I'm missing the leap from the question of decimals of accuracy to printing posits as decimal numbers. Isn't the former more of a question about how many significant numbers one should expect to have after doing N calculations with numbers in a particular range? Isn't that a related but different problem to doing a round-trip to a decimal representation of a single number? Perhaps I am reading an intent in Allessandro's question that is not there, though.

I recall discovering non-obvious corner cases that didn't work.

 

To stick with the problem of a to-decimal-representation-and-back, wouldn't these corner cases be a good test data set for anyone trying to come up with a formula?

Kind regards,

Job van der Zwan

[Alessandro Astone]

I was actually interested in the accuracy compared to real numbers. For example, a 32-bit float has a (almost) uniformly distributed ~7 digit accuracy.

Because posits are not uniformly distributed, to perform the same analysis I need to start with a target range. How many digits are accurately stored in a Posit of size N in the range (a,b)?

I believe this was explored for 8 bits size in the John L. Gustafson, Isaac Yonemoto paper, and presented as below:

From that for example I can deduce that for Posit8 in the range (-16,16) I should expect no less than 1.3 digits of accuracy

Then the question of how bad is the loss after N calculations within the range is also interesting, as Job was saying.

[John Gustafson]

Hi Alessandro,

I think what you need is a preview of Chapter 2 of my next book, Every Bit Counts: Posit Computing. Attached here. It is a better analysis than what was in the original paper I wrote with Yonemoto.

Decimal accuracy is not the same as the minimal number of decimals needed to assure conversion back to the original posit. The latter is larger. For example, a 32-bit posit has 28 bits of significance in its highest-accuracy region, which is about 28 * log10(2) + 0.5 log10(2) ≈ 8.6 decimals of minimum relative accuracy, but if you only use 9 decimals to express a posit and you convert those 9 decimals back into a posit, occasionally you will get a different posit from what you started with.

John

[Alessandro Astone]

Thanks, that is indeed helpful!

I see you computed the accuracy in the highest accuracy region by considering that it is obtained with 1 sign bit, 1 regime bit, 2 exponent bits, and thus 28 fraction bits.

So should I extend this to my problem, that is finding the accuracy in any region defined by an interval of reals (a,b)?

I would apply the formula: (N_bits - max{regime_bits(a), regime_bits(b)} - 3) * log10(2) + 0.5 log10(2)

Does that make sense?

[Alessandro Astone]

The issue i see with that is that i was disregarding ranges below 1.

Indeed ranges that include the zero should always have the lowest minimum relative accuracy

[John Gustafson]

First of all, there are two regime bits (01 or 10), not one. The termination (opposite) bit is part of the regime. That leaves 27 bits for the fraction, which is 28 bits of significand including the hidden value left of the radix point.

Yes, your formula should then work, but remember that you have wobbling relative accuracy (wobble of ±½ log10(2) ≈ ±0.15 decimals) for both posits and floats within any given binade. You should probably be pessimistic and use the lower bound on the sawtooth shape if you are trying to prove something about the accuracy of a computation.

John

--
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/474db44a-3195-4969-bacc-b380ab271704n%40googlegroups.com.

[Alessandro Astone]

Thanks.

Do you have an idea on how to get any significance on the result if the range includes zero? Since the regime bits tend to N_bits and the relative accuracy goes to zero...

[John Gustafson]

Remember that we usually measure real number errors as the difference of the logarithms of the computed value and the correct value. So any interval that spans zero is just as inaccurate as an interval that includes infinity or minus infinity.

You don't get exact zero with posits unless you multiply by zero or add x to –x. Unlike floats, posits do not make the infinitely large error of flushing small results to zero. Hence, I expect your interval does not actually include zero. It may look more like

[–a, –minPos] ∪ [minPos, a]

in which case the relative error could be quite low. Just as it's important to be able to bound the magnitude of calculations on the high end (to avoid overflow to ∞ for floats, or major loss or relative accuracy for posits), the same is true for bounding the magnitudes on the low end.

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/05b5c39c-a78e-438d-badd-f540a45083c2n%40googlegroups.com.

[Alessandro Astone]

Makes sense!

However, you state that in which case the relative error could be quite low, but following the method of counting how many fraction bits are left in the representation I would get none for minPos.

And indeed, for an example with Posit16, the decimal accuracy between  minPos≈1.4e-17 and  next(minPos)≈2.2e-16 evaluates to roughly 0.44 digits.

[John Gustafson]

I mis-typed… I meant to write the the relative accuracy could be quite low. Just the opposite. The relative accuracy could be quite high. Sorry!

John

To view this discussion on the web visit https://groups.google.com/d/msgid/unum-computing/6c47bbdd-af79-4adc-acfa-423404ccd649n%40googlegroups.com.

[John Gustafson]

Alessandro,

I now understand that you wanted a general approach to finding decimal digits of accuracy for an arbitrary specific number range, and I think that has now been answered.

But I said I would provide details about a closely-related problem, which is converting to decimal form and back. This is a much trickier subject than you would imagine. Consider 8-bit standard posits, which according to the Posit™ Standard (2022) can be converted to 2 decimals of accuracy and that 2-decimal number will convert back to the original posit. But consider this diagram for part of the range:

If you convert 1/8 = 0.125 to a 2-digit decimal, you have a tie between 0.12 and 0.13. By the "ties go to even" (banker's rounding) rule, you would choose 0.12; however, when you convert 0.12 back to a posit, you should get 15/128 = 0.1171875 as the closest posit representation, which is marked "oops" in the diagram. In this case, converting 1/8 to 0.13 will give correct behavior, but I'm still uncertain what the algorithm is for handling all such cases. It's not just posits, by the way; a similar problem can happen with floats.

This brings up an interesting advantage of posits over floats: compact formatting. The more extreme the magnitude, the greater the need to express an exponent instead of using the location of the decimal point, but the lower the number of decimals needed to express the value such that it converts back to the correct posit. I believe all 8-bit posits can be expressed using only six characters, in human-readable decimal. For example, starting with minPos = 1 / 16777216:

00000001 +6e–8

00000010 +1e–6

00000011 +4e–6

00000100 +2e–5

00000101 +3e–5

00000110 +6e–5

00000111 +1e–4

00001000 +2e–4

00001001 +4e–4

00001010 +5e–4

00001011 +7e–4

00001100 +.001

The point at which to switch from e notation to movable decimal point is a matter of taste, but all of those fit in just five characters. The next one requires the maximum of six characters:

00001101 +.0015  That's the first one that requires two decimal digits.

00001110 +.002

00001111 +.003

.

.

.

Then when you get to the range 1/16 to 16 where the accuracy is highest, you have space for two decimals where needed:

.

.

.

00100000 +.06

00100001 +.07

00100010 +.08

00100011 +.086

00100100 +.09

.

.

.

and once you get to large magnitudes, you can go back to e notation:

.

.

.

01110100 +1e3

01110101 +1.5e3 That's the last one that requires two decimal digits.

01110110 +2e3

01110111 +3e3

.

.

.

01111111 +2e7

I haven't worked out what the minimum number of characters is for standard 16-bit and 32-bit posits yet, but I'm pretty sure it is more compact than for IEEE floats of the same precision. as the result of tapered accuracy making room for the e notation.

John

On Jul 11, 2023, at 2:46 AM, Alessandro Astone <ales....@gmail.com> wrote:

As posits have dynamic precision, I would like to be able to compute how many decimals of accuracy i can expect within a specific number range.

For example, how may I compute the minimum decimal precision of a Posit16 (defined as per the latest spec with 2 bits of exponent) in the range (a,b)? And how about generalized for size N?

--
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/f5259246-d22d-4689-87ad-2dd0f94c9948n%40googlegroups.com.

[MitchAlsup]

On Wednesday, July 12, 2023 at 10:12:35 AM UTC-5 johngustafson wrote:

I think what you need is a preview of Chapter 2 of my next book, Every Bit Counts: Posit Computing. Attached here. It is a better analysis than what was in the original paper I wrote with Yonemoto.<snip>

John

I like Chapter 2 where you switch from error to accuracy. Indeed if you change your |ln()| into |ln2()| you get bits of precision directly. 

And if you plot this, you can reason about a polynomial accuracy visually.

This is the way I present "math" to circuit designers. "you have to get this bit correct in order for the "math" to work at the architectural level. And to get that bit correct this multiplier tree has to be this big and coefficient[i] input has to be this big."

[Job van der Zwan]

On Thu, 13 Jul 2023 at 22:22, John Gustafson <jlgu...@asu.edu> wrote:

But I said I would provide details about a closely-related problem, which is converting to decimal form and back. This is a much trickier subject than you would imagine. Consider 8-bit standard posits, which according to the Posit™ Standard (2022) can be converted to 2 decimals of accuracy and that 2-decimal number will convert back to the original posit. But consider this diagram for part of the range:

If you convert 1/8 = 0.125 to a 2-digit decimal, you have a tie between 0.12 and 0.13. By the "ties go to even" (banker's rounding) rule, you would choose 0.12; however, when you convert 0.12 back to a posit, you should get 15/128 = 0.1171875 as the closest posit representation, which is marked "oops" in the diagram. In this case, converting 1/8 to 0.13 will give correct behavior, but I'm still uncertain what the algorithm is for handling all such cases. It's not just posits, by the way; a similar problem can happen with floats.

This sounds like one of those problems where you can surprise non-mathematicians with the fact that it's so difficult to solve. I certainly am! May I indulge in some naive questions out of curiosity?

This is describing the problem of converting to decimal and back, but there also is the question of converting from decimal to posit and back. Is that also an unsolved problem? If so, is it the same problem or a different one somehow?

The reason I'm wondering is because this image indirectly reminded me of the novel correct rounding tricks that RLibm¹ uses for determining its polynomial approximations. If I understand correctly, one of its key insights is: if we have a function f(x) for real-valued input that produces correctly rounded n+2 bit floating point (or posit) representations, using a round-to-odd mode, then that function can be used to produce correctly rounded results for all n-bit representations with all other rounding modes.

Since you are a collaborator on that project I'm sure you have already tried to translate all insights from them to this context, but I'm still wondering: if the question is "converting from d-digit decimals to correctly rounded n-bit posits and back", could one resort to the RLibm approach? Is it even necessary? If it is and works, could that be a starting point of figuring out the other roundtrip of binary-to-decimal-and-back?

Kind regards,

Job van der Zwan

¹ https://people.cs.rutgers.edu/~sn349/rlibm/

[John Gustafson]

Job,

Yes, this has all the earmarks of one of those mathematical questions that is so simple to pose and so tantalizingly difficult to solve. Like, "In a grid of unit squares, how many will be completely inside a circle of radius r?" If you want it exactly, not just approximately, you're going to have a head-scratcher for a while.

Let me start by offering you a tool, with apologies that it's written in Mathematica but I hope it's readable: