Correction. The length of prefix is about 1024 - 308 < 750 digits, not 308 .
Sorry.
-Dima
----- Original Message -----
From: dmitry.nadezhin@xxxxxxxxxx
To: stds-1788@xxxxxxxxxxxxxxxxx
Sent: Tuesday, May 24, 2016 10:15:30 PM GMT +03:00 Iraq
Subject: Fwd: Difficulties in implementation of textToInterval(s)
Ned,
> how difficult is to compute the hull in binary from two decimal strings for which we
> know l <= u?
We need to perform two independent conversions:
- convert l rounding to negative infinity;
- convert u rounding to positive infinity.
Knowledge l <= u doesn't give an advantage here.
Consider one of conversions, u to positive infinity.
u may have arbitrary many decimal digits.
The good thing is that we are more interested in some prefix of u.
We don't need to make computations on remaining tail digits,
it is only necessary to scan tail digits and determine if they are all zeros
or there is a non-zero digit. The length of interesting prefix is about 308 decimal digits
for b64 format. So time is A + B*n where n is a number digits. B is rather small (time to compare with zero).
Time A can be estimated in such a way for 64-bit CPU.
Group digits into 19 digits chunks.
Each chunk is converted into a machine word (10^19 < 2^64).
This may require 308 multiplications, thouth there are tricks to do it in fewwer multiplications.
There are no more than 308/19 = 17 chunks.
To convert them from decimal to multiprecision binary it is necessary 17*17/2 = 145 64-bit multiplications.
So 308 + 145 approximately 500 64-bit integer multiplications and approximately the same number of additions.
Above estimation was worst-case.
Usually number of digits doesn't exceed much number required to represent mantissa precisely.
For b64 it is 17 because 2^53 < 10^17 . It is assumed threshold of 17+3 = 20 digits.
When number of decimal digits is less that some threshold it is possible to make some precomputations and
then use faster algorithm developed by Michel Hack:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.85.8351&rep=rep1&type=pdf#page=114
> Has anybody tried to document the tightness of interval
operations for a particular package?
I know about a few packages with tightest accuracy:
libieee1788
JInterval
mpfi
-Dima