Re: [Caml-list] Approximations when converting from string to float

[Jacques-Henri Jourdan <jacques-henri.jourdan@normalesup.org>]

[-- Attachment #1: Type: text/plain, Size: 3271 bytes --]

Hi all,

On 10/25/2016 01:20 PM, Soegtrop, Michael wrote:
>
> Dear Tung,
>
> converting strings to floats and keeping exact bounds is not that 
> complicated. The steps are:
>
> 1.)Convert the digits to an integer. You can stop when you have 1 or 2 
> digits more than the mantissa can hold. E.g. if you create a 32 or 64 
> bit float, a 32 bit or 64 bit integer is enough, because it is quite a 
> bit longer than the float mantissa. The lower and upper bounds are the 
> truncated value and the truncated value + 1. If the decimal number 
> fits into the mantissa, the bounds are the same. For the truncated 
> digits you just have to count them to correct the decimal exponent. 
> Also you need to take care of the decimal point to get the proper 
> decimal exponent.
>

The issue is that values of the remaining digits *do* matter for the 
right result to be computed, not just the number of them.

Imagine if the integer you get is 2^70 or 2^70-1. Then the lower bounds 
of the intervals have to be different (2^70 is exactly a double 
precision float, so 2^70-1 maps to the preceding float), but notice that 
these two integers differ only by their last digit.


> 2.)Convert the integer to a float. If the integer is smaller than the 
> mantissa length, this is trivial. If it is longer, you divide by 2 
> until it fits. The lower limit from step 1 is rounded down, the upper 
> limit is rounded up while dividing. The number of divide steps is 
> limited by the difference of the integer size you used and the floats 
> mantissa size (that is the exponent size of the float +1). To make it 
> faster, you can also do a binary intersection search of the right 
> power of 2, but it might not be worth it, because dividing integers by 
> 2 is cheap and the max loop count is small.
>
> 3.)In order to handle the decimal point and decimal exponents, you 
> need tables of 10^(2^n). Use the binary representation of the decimal 
> exponent to find out which powers to multiply. For each power you need 
> a lower and upper bound value (as a floating point number). You can 
> compute these tables with libraries supporting higher precision 
> numbers and store the numbers (best in hex float notation – which is 
> standard C). In an IEEE floating point implementation, you can choose 
> the rounding direction (up down middle). When you multiply the factors 
> of the lower and upper bounds, you set the rounding direction 
> accordingly. The C function for this is fesetround. The exponent 
> tables are fairly small, because 10^(2^n) is larger than the maximal 
> floating point number for rather modest n (for double precision, n=8 = 
> 10^256 should be the largest value you need).
>
> That’s it. Since you multiply several numbers (at most 10), each of 
> which is rounded up /down, your range might be a bit larger than 
> necessary. For getting the minimum bound you need multi precision 
> arithmetic, but the method above works with just target precision 
> arithmetic and gives reliable bounds.
>

That's the point : if you really want the tight interval, then you need 
arbitrary precision arithmetic.

Moreover, it is not possible to implement interval arithmetic with 
OCaml, since you cannot change the rounding mode without a bit of C...

-- 
JH

[-- Attachment #2: Type: text/html, Size: 9786 bytes --]