Re: Motion 46: finalise interval literals, amendments
> Multiple precision, yes. But arbitrary precision is not necessary,
> as the needed precision is bounded, AFAIK.
More precisiely, if both needed precision and needed exponent range are bounded.
If precision is bounded but exponent range is unbounded, arbitrary precision is necessary.
Now about p/q conversion .
If binary format F is fixed then correct rounding of p/q to F
can be computed in O(1) memory and in O(n) time, where n - number of characters in
string p/q .
How to do it ? We need comparison of p/q with some threshold.
Threshold is either a number from F or midpoint between neibour numbers of F.
Threshold is a rational number a/b . For fixed format F, a and b are bounded by some N,
though N is about pow(2, F-exponent-range).
So we need to compare p*b and q*a .
If we compare them in decimal arithmetic without conversion to binary,
we can do it in fixed 2*N*N memory
and in time something proportional to length of a in b.
-Dima
----- Исходное сообщение -----
От: vincent@xxxxxxxxxx
Кому: stds-1788@xxxxxxxxxxxxxxxxx
Отправленные: Вторник, 9 Июль 2013 г 19:21:38 GMT +04:00 Абу-Даби, Маскат
Тема: Re: Motion 46: finalise interval literals, amendments
On 2013-07-09 05:20:04 -0700, Dmitry Nadezhin wrote:
> > Otherwise an arbitrary precision library may be needed to
> > evaluate (simplify) rational numbers.
>
> Arbitrary precision library is not a trouble.
> Conversion of decimal string to binary floating-point
> with correct rounding already requires
> arbitrary precision library.
Multiple precision, yes. But arbitrary precision is not necessary,
as the needed precision is bounded, AFAIK.
--
Vincent Lefèvre <vincent@xxxxxxxxxx> - Web: <http://www.vinc17.net/>
100% accessible validated (X)HTML - Blog: <http://www.vinc17.net/blog/>
Work: CR INRIA - computer arithmetic / AriC project (LIP, ENS-Lyon)