Ian,
According to the draft, interval literal [l,u] is invalid, when l > u,
and its value in level2 is NaI.
Suppose two strings
s1 = "[ 1.0...02 , 1.0...01 ]";
s2 = "[ 1.0...02 , 1.0...03 ]";
Here "..." stands for N zeros when N is sufficiently large.
s1 - is invalid, s2 - is valid.
the value of b64-text2interval(s1) is NaI ;
the value of b64-text2interval(s2) is [ 1 , b64-nextUp(1) ].
So tightest implementation must store all digits of l in memory.
However, there is a relaxed rule in 11.11.8 of the Draft 7.3 :
"text2interval(s) ...
succeeds in the following cases ...
- s is of inf-sup form [l, u] but the implementation cannot determine that l ≤ u. The result shall
be an interval containing l and u".
So accurate implementation may say that it cannot determine and
return b64-text2interval(s1) = [1, b64-nextUp(1) ]. It doesn't need to store all digits of l in memory.
This problem occur only with tightest implementation.
Accurate implementation can handle all forms of interval literals (including p/q form) in bounded memory.
-Dima
----- Исходное сообщение -----
От: ianm@xxxxxxxxxx
Кому: stds-1788@xxxxxxxxxxxxxxxxx
Отправленные: Пятница, 12 Июль 2013 г 6:31:47 GMT +04:00 Абу-Даби, Маскат
Тема: Re: Motion 46: finalise interval literals, amendments
On 2013-07-10 19:27:43 -0700, Dmitry Nadezhin wrote:
> > Am I right that this p/q feature is the ONLY place in the standard
> > that specifies data structures of unbounded size?
>
> No, this feature is not the only place.
>
> Suppose input stream with interval literal [l,h] where l and u are
> decimal string. We need to store l in memory to distinguish between
> l <= u and l > u.
In the discussion about nums2interval, I wanted to drop this
distinction because of such kind of problems, which may occur
with some numeric types. Of course, problems are the same with
interval literals.
So, if rationals are supported, I agree that we should not require
correct rounding for all possible inputs. In particular, this would
mean that the above distinction needs to be dropped.
--
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)
According to the draft, interval literal [l,u] is invalid, when l > u,
and its value in level2 is NaI.
Suppose two strings
s1 = "[ 1.0...02 , 1.0...01 ]";
s2 = "[ 1.0...02 , 1.0...03 ]";
Here "..." stands for N zeros when N is sufficiently large.
s1 - is invalid, s2 - is valid.
the value of b64-text2interval(s1) is NaI ;
the value of b64-text2interval(s2) is [ 1 , b64-nextUp(1) ].
So tightest implementation must store all digits of l in memory.
However, there is a relaxed rule in 11.11.8 of the Draft 7.3 :
"text2interval(s) ...
succeeds in the following cases ...
- s is of inf-sup form [l, u] but the implementation cannot determine that l ≤ u. The result shall
be an interval containing l and u".
So accurate implementation may say that it cannot determine and
return b64-text2interval(s1) = [1, b64-nextUp(1) ]. It doesn't need to store all digits of l in memory.
This problem occur only with tightest implementation.
Accurate implementation can handle all forms of interval literals (including p/q form) in bounded memory.
-Dima
----- Исходное сообщение -----
От: ianm@xxxxxxxxxx
Кому: stds-1788@xxxxxxxxxxxxxxxxx
Отправленные: Пятница, 12 Июль 2013 г 6:31:47 GMT +04:00 Абу-Даби, Маскат
Тема: Re: Motion 46: finalise interval literals, amendments
Sorry, I don't understand why needing to store 1 when processing [1, h] to distinguish between 1 <= u and 1 > u needs unbounded memory. Can't you just store 1 as a floating point value of bounded size (eg, 8 bytes for double precision)?
Does the problem only occur when using arbitrary precision and with an arbitrarily long numerator?
- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development
Vincent Lefevre ---07/11/2013 09:17:37 AM---On 2013-07-10 19:27:43 -0700, Dmitry Nadezhin wrote: > > Am I right that this p/q feature is the ONL
| Vincent Lefevre <vincent@xxxxxxxxxx> |
| Ian McIntosh/Toronto/IBM@IBMCA |
| 07/11/2013 09:17 AM |
| Re: Motion 46: finalise interval literals, amendments |
On 2013-07-10 19:27:43 -0700, Dmitry Nadezhin wrote:
> > Am I right that this p/q feature is the ONLY place in the standard
> > that specifies data structures of unbounded size?
>
> No, this feature is not the only place.
>
> Suppose input stream with interval literal [l,h] where l and u are
> decimal string. We need to store l in memory to distinguish between
> l <= u and l > u.
In the discussion about nums2interval, I wanted to drop this
distinction because of such kind of problems, which may occur
with some numeric types. Of course, problems are the same with
interval literals.
So, if rationals are supported, I agree that we should not require
correct rounding for all possible inputs. In particular, this would
mean that the above distinction needs to be dropped.
--
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)
