Re: Difficulties in implementation of textToInterval(s)
Am 24. Mai 2016 19:37:54 MESZ, schrieb "Nedialkov, Ned" <nedialk@xxxxxxxxxxx>:
>
>
>Dmitry,
>
>
>On May 24, 2016, at 00:11, Dmitry Nadezhin <dmitry.nadezhin@xxxxxxxxxx>
>wrote:
>
>
>Perhaps, it were wiser if P1788 required the same radix in l and u ends
>of interval number literals.
>However, I am not sure if it is possible to fix it now.
>
>I remind why I insist on rational number literals.
>I want interchange between different interval types different
>implementations.
>Implementation A1 if interval type T1 should be to able convert its
>interval x
>to an interval literal s of the same value as x by
>s=intervalToExact(x).
>And then implementation A2 of iterval type T2 should be able to read
>this to interval y that contains x
>by y=textToInterval(s).
>
>If T1 is infsup_F where F is a binary floating-point format then
>intervalToExact(x) can return interval literal where ends are
>hexadecimal number literals.
>If T1 is infsup_F where F is a decimal floating-point format then
>intervalToExact(x) can return interval literal where ends are decimal
>number literals.
>If T1 is infsup_F where F is a format whose members are rational
>numbers then
>intervalToExact(x) can return interval literal where ends are rational
>number literals.
>
>So I request that y=textToInterval(s) of P1788.1 implementation is able
>to read any of such string
>into infsup_b64 interval y which contains x.
>It can be achieve by adding a sentence to 6.6.1
>"- A rational literal p / q. This comprises an integer literal p, the /
>character, and a positive-natural literal
>q. Its value is the value of p divided by the value of q."
>As rational literal has radix 10, the difficult case of mixing
>hexadecimal and rational ends
>will be excluded by the new words in 6.6.2 “of the same radix (10 or
>16)”.
>
>
>I feel quite uneasy advocating for rationals into the simplified
>standard. I do not see them massively
>
>used to justify the added complexity.
>
>
>
>If we have l and u in [ l, u ] of the same radix (as suggested in my
>previous e-mail),
>we can leave it as implementation dependent how they are (outward)
>rounded when
>converted to binary64.
>
>
>Does it mean that you want to replace
>"If s is a valid interval literal with Level 1 value x,
>the result shall be the hull of x (the constructor succeeds)."
>in 6.7.5 by something like this
>"If s is a valid interval literal with Level 1 value x,
>the result shall contain x (the constructor succeeds).”
>
>?
>
>
>I thought about it. I am not an expert on conversions. My question is,
>for more knowledgeable
>
>people, how difficult is to compute the hull in binary from two decimal
>strings for which we
>
>know l <= u?
>
>(BTW, I found this an interesting read
>http://www.exploringbinary.com/incorrect-directed-conversions-in-david-gays-strtod/)
>
>
>Here are two more questions. In both 1788 and 1788.1, we have “Accuracy
>requirements.” In an implementation, they have to be documented. Has
>anybody tried to document the tightness of interval
>
>operations for a particular package? Moreover, is there an
>implementation that (provably) satisfies these
>
>requirements?
>
>
>Regards,
>
>Ned
If you don't have a correctly-rounded string-to-binary64 operation, you can achieve the conversion with some string operations, which should be available almost everywhere---at least in software.
First, you need a data type for decimal numbers with arbitrary precision. That is, a sign bit, an exponent, and a mantissa. The latter can be stored as a string or as an array of digits. For now, you don't need any arithmetic operations on that data type. It is only necessary to have simple comparison operations (less than, greater than or equal, ...).
To compute the hull of [l, u] one has to convert decimal number literal l (and u respectively) into binary64 with directed rounding.
1. Convert l into the decimal data type mentioned above.
2. Check if the absolute value of l lies between realmin (2^-1074) and realmax. If not, this can be handled as a special case.
3. Use the standard string-to-binary64 operation to produce an approximate value of l. The value should have been rounded to nearest (ties to even) and might already be the correct result.
4. Convert the binary64 value back into the decimal data type. This operation is lossless.
5. Check, if the binary64 value is greater than l. If so, use the nextBefore operation to get the correct result. Otherwise the binary64 number is correct.
The upper boundary u can be converted analogously.
To support rational numbers, we have to extend the decimal data type with (exact) add, subtract, and division operations. The add and subtract operations should be straightforward to implement. Note, that they might lead to a result with very long mantissa, but that does not happen in the following scenario. The exact division operation shall compute (up to) n significant digits of the result and return it together with a remainder. A very primitive implementation can be carried out like this: for i = 1 to n do, while remainder > divisor do, mantissa [i] ++, remainder -= divisor, end while, divisor /= 10, end for.
Now, if l is a rational number literal, we insert step 0 before step 1 above.
0. Split l at the slash character. Do a division with 18 significant decimal digits. If there is a remainder, set mantissa [19] to an arbitrary value different from zero, e.g., mantissa [19] = 1.
Regarding the accuracy requirements. Please check the wiki (at Github) of libieeep1788. IIRC, it lists all operations with accuracy. Since MPFR with correctly-rounded operations is used internally, it should be easy to verify that the requirements are fulfilled (given that you trust or have proven MPFR to be correct).
Oliver
P.S. please excuse my brevity, I am on the beach with no Internet access to provide links.