Prev: UTF-8 messages in exceptions ?
Next: Is there any standard/guarantees for exception safety in STL operations?
From: Michael Kilburn on 17 Jul 2010 12:25
Hi,

This is somewhat tricky question:
- we have two doubles d1 and d2
- and d1 < d2
Is it guaranteed (and where exactly in C++/IEEE 754 standards?) that
this relationship will stay if I move d1 and/or d2 around in memory?

I'll try to illustrate this in example:

double foo() { ... } // this is a "generator"

deque<double> v_sorted(1, 0.0); // populated with one value of 0.0
for(size_t i = 0; i < 1000; ++i)
{
double d = foo();

if (v_sorted.back() < d) v_sorted.push_back(d);
}

As you see I am trying to extract ordered sequence (without
duplicates, values > 0) from stream of values produced by foo().

Now -- is it guaranteed that I'll end up with what I seek (ordered, no
duplicates)? I feel answer is "yes", but then more important question
arises -- where are those guarantees?

Thank you.
Michael.


P.S. Why answer can be "no" -- because on x87 FPU register is 80bits
(+ hidden bit) and in-memory double is 64 bits. I.e. if compiler does
not round double produced by foo() before comparison we might end up
with d1 < d2. But later we unload value into memory in push_back()
call which will force rounding and d2 might become equal to d1.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Bo Persson on 18 Jul 2010 05:28
Michael Kilburn wrote:
> Hi,
>
> This is somewhat tricky question:
> - we have two doubles d1 and d2
> - and d1 < d2
> Is it guaranteed (and where exactly in C++/IEEE 754 standards?)
> that this relationship will stay if I move d1 and/or d2 around in
> memory?
>
> I'll try to illustrate this in example:
>
> double foo() { ... } // this is a "generator"
>
> deque<double> v_sorted(1, 0.0); // populated with one value of 0.0
> for(size_t i = 0; i < 1000; ++i)
> {
> double d = foo();
>
> if (v_sorted.back() < d) v_sorted.push_back(d);
> }
>
> As you see I am trying to extract ordered sequence (without
> duplicates, values > 0) from stream of values produced by foo().
>
> Now -- is it guaranteed that I'll end up with what I seek (ordered,
> no duplicates)? I feel answer is "yes", but then more important
> question arises -- where are those guarantees?
>
> Thank you.
> Michael.
>
>
> P.S. Why answer can be "no" -- because on x87 FPU register is 80bits
> (+ hidden bit) and in-memory double is 64 bits. I.e. if compiler
> does not round double produced by foo() before comparison we might
> end up with d1 < d2. But later we unload value into memory in
> push_back() call which will force rounding and d2 might become
> equal to d1.

The answer will be Yes if you use proper settings for you compiler, so
that it either doesn't use the 80 bit registers or forces the
appropriate rounding before comparisons. Some compilers have a default
setting that favors faster code, even if it means being slightly
non-conforming.

http://msdn.microsoft.com/en-us/library/e7s85ffb.aspx



Bo Persson



--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Zeljko Vrba on 18 Jul 2010 05:30
On 2010-07-18, Michael Kilburn <crusader.mike(a)gmail.com> wrote:
> Hi,
>
> This is somewhat tricky question:
> - we have two doubles d1 and d2
> - and d1 < d2
> Is it guaranteed (and where exactly in C++/IEEE 754 standards?) that
> this relationship will stay if I move d1 and/or d2 around in memory?
>
The answer could be "no" only if the same bit pattern were interpreted
differently depending on where in memory it is stored. No CPU with such
a botched FP implementation would survive long on the market.

> I'll try to illustrate this in example:
>
> double foo() { ... } // this is a "generator"
>
> deque<double> v_sorted(1, 0.0); // populated with one value of 0.0
> for(size_t i = 0; i < 1000; ++i)
> {
> double d = foo();
>
> if (v_sorted.back() < d) v_sorted.push_back(d);
> }
>

>
> P.S. Why answer can be "no" -- because on x87 FPU register is 80bits
> (+ hidden bit) and in-memory double is 64 bits. I.e. if compiler does
> not round double produced by foo() before comparison we might end up
> with d1 < d2. But later we unload value into memory in push_back()
> call which will force rounding and d2 might become equal to d1.
>
This is different than comparing two doubles that are already stored in
memory (your original question). Here, the answer can be "no" because
you don't know whether you're comparing 1) two doubles in memory, or 2)
one long double in register and one double in memory, or 3) two long
doubles in two registers (an advanced compiler might cache also the
last element of the vector in a register).

Try finnding in your compiler documentation how to turn on strict IEEE FP
and what are effects of that switch.

To get around this problem, you can set the x87 precision to 64 bits.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Louis Lavery on 18 Jul 2010 05:30
On 18/07/2010 04:25, Michael Kilburn wrote:
> Hi,
>
> This is somewhat tricky question:

Nice question.

> - we have two doubles d1 and d2
> - and d1< d2
> Is it guaranteed (and where exactly in C++/IEEE 754 standards?) that
> this relationship will stay if I move d1 and/or d2 around in memory?

I think the only platform independent C++/IEEE 754 rule is that there
aren't any (bar this one!). An awful state really, it's no wonder
floating point software is still so flaky.

> I'll try to illustrate this in example:
>

You could do something like this...

> double foo() { ... } // this is a "generator"
>
> deque<double> v_sorted(1, 0.0); // populated with one value of 0.0
> for(size_t i = 0; i< 1000; ++i)
> {
deque<double> const d(1, foo());
>
> if (v_sorted.back()< d) v_sorted.push_back(d);
> }

.....but I can't say as it's guaranteed to work.

Louis.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Daniel Krügler on 18 Jul 2010 05:30
On 18 Jul., 05:25, Michael Kilburn <crusader.m...(a)gmail.com> wrote:
> Hi,
>
> This is somewhat tricky question:
> - we have two doubles d1 and d2
> - and d1 < d2
> Is it guaranteed (and where exactly in C++/IEEE 754 standards?) that
> this relationship will stay if I move d1 and/or d2 around in memory?
>
> I'll try to illustrate this in example:
>
> double foo() { ... } // this is a "generator"
>
> deque<double> v_sorted(1, 0.0); // populated with one value of 0.0
> for(size_t i = 0; i < 1000; ++i)
> {
> double d = foo();
> if (v_sorted.back() < d) v_sorted.push_back(d);
> }
>
> As you see I am trying to extract ordered sequence (without
> duplicates, values > 0) from stream of values produced by foo().
>
> Now -- is it guaranteed that I'll end up with what I seek (ordered, no
> duplicates)? I feel answer is "yes", but then more important question
> arises -- where are those guarantees?

I think this is already guaranteed by the basic requirements
of a C++ program in 1.9/5:

"A conforming implementation executing a well-formed program
shall produce the same observable behavior as one of the
possible execution sequences of the corresponding instance of
the abstract machine with the same program and the same input."

and p. 10:

"10 An instance of each object with automatic storage duration
(3.7.2) is associated with each entry into its block. Such an
object exists and retains its last-stored value during the
execution of the block and while the block is suspended (by
a call of a function or receipt of a signal)."

All this is only relevant, if any difference would be
observable and it does also not apply to volatile
objects (which might change their value at any point
in time).

Via the C standard latitude is given to implementations
that the intermediate format of floating-point
operations is greater than required by the type, but I
don't see how this result in an observable difference
in your particular example.

HTH & Greetings from Bremen,

Daniel Kr�gler







--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: UTF-8 messages in exceptions ?
Next: Is there any standard/guarantees for exception safety in STL operations?