Re: Motion 46: finalise interval literals, amendments
Vincent,
> the literals may be read from an unseekable stream
Yes. I should be more exact:
If binary format F is fixed and input string p/q is in read-only seekable memory
then correct rounding of p/q to F
can be computed using read/write memory of bounded size.
If input is in a stream, then this algoritm requires O(n) memory to store input.
> I don't think that's possible in practice.
In practice p and q are of reasonable size.
I imagine only how a hacker sipplies long digit sequences as DoS attack.
An implementation may fail if it can't store input stream in memory
reporting OutOfMemory error.
I don't think that standard should specifiy this.
-Dima
----- Исходное сообщение -----
От: vincent@xxxxxxxxxx
Кому: stds-1788@xxxxxxxxxxxxxxxxx
Отправленные: Среда, 10 Июль 2013 г 3:45:44 GMT +04:00 Абу-Даби, Маскат
Тема: Re: Motion 46: finalise interval literals, amendments
On 2013-07-09 09:54:35 -0700, Dmitry Nadezhin wrote:
> > 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.
By "needed precision" I meant the precision needed to determine the
float (not the precision of the format). Then I agree with you.
> 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.
I don't think that's possible in practice. Note that with some
interfaces, the literals may be read from an unseekable stream
(e.g. a pipe), so that you need to guess b before p has entirely
been read and a before q has entirely been read, or consider all
the possible cases. Even with that, I don't see how you can start
the comparison before starting reading q... And if you don't, you
won't get O(1) memory. Indeed if this can be done in O(1) memory,
then there exist two different values of p that will give the same
memory status, say p and p' with p < p'; this means that you can't
differentiate p/q and p'/q, even in the case p/q < a/b < p'/q.
--
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)