Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > C/C++ pitfalls related to 64-bits (unsigned long & double)

Reply
Thread Tools

C/C++ pitfalls related to 64-bits (unsigned long & double)

 
 
Miles Bader
Guest
Posts: n/a
 
      02-14-2012
BGB <(E-Mail Removed)> writes:
>> Integer arithmetic with doubles _is_ exact though, if the integers can
>> be exactly-represented as doubles (which appears to be the case here).

>
> yes.
>
> the issue may be partly a matter of HW though, as I am seeing it on my
> HW (using an AMD chip), but apparently someone else is not seeing it
> (with an Intel chip), but there does seem to be a pattern in the values
> (apparently: 0x4, 0x40, 0x400, 0x4000, ..., so for whatever reason
> integer results which should land on one of these values is off by a
> tiny amount...).


Any conventional PC-type system these days is going to use IEEE FP,
and if the system claims to support IEEE FP, it has to be exact. If
it isn't, it's a bug.

I did run your program on my AMD system (phenom I), and it showed no
output. It would be interesting to see somebody with an identical CPU
to yours try it...

> it could be a minor issue of the "arithmetic with doubles may not be
> exact even if the doubles represent integers" variety, which is odd, but
> whatever (it can be compensated for by fudging the value).


I'm not sure you could call it a minor issue. A lot of software
assumes that FP arithmetic is exact for integer values within a
certain range, and isn't going to do any fudging (because it shouldn't
be necessary, and would have a severe performance impact), so such a
system where fudging is necessary would have ... problems.

-miles

--
Clarionet, n. An instrument of torture operated by a person with cotton in his
ears. There are two instruments that are worse than a clarionet -- two
clarionets.
 
Reply With Quote
 
 
 
 
Miles Bader
Guest
Posts: n/a
 
      02-14-2012
Eric Sosman <(E-Mail Removed)> writes:
>> Integer arithmetic with doubles _is_ exact though, if the integers can
>> be exactly-represented as doubles (which appears to be the case here).

>
> C doesn't actually guarantee this. It guarantees exact
> conversion to an F-P type for all values the type can represent
> exactly (for example, 42 must convert to exactly 42.0, not to
> 42.0000000000000010173 or some such), but it does not guarantee
> that 42.0 (exact) plus 1.0 (exact) equals 43.0 (exact).


Not C, but C-on-a-system-using-IEEE-FP, which is basically everything
mainstream. [In practice it's a pretty good bet that even wackier FP
hardware actually maintains the same constraint.]

Although C-the-language hedges its bets for extreme portability (and
to some degree, history: things were a lot more wild-n-wooly when C
was created), people writing the actual applications tend to be a bit
more practical, and _do_ assume things that aren't guaranteed by the
language, if the likelihood of that assumption being violated is
infinitesimal. I think this is a reasonable stance where the cost of
not making such assumptions is non-trivial.

-miles

--
XML is like violence. If it doesn't solve your problem, you're not
using enough of it.
 
Reply With Quote
 
 
 
 
Miles Bader
Guest
Posts: n/a
 
      02-14-2012
James Kuyper <(E-Mail Removed)> writes:
>>> so, this may not be a conversion bug, but more of an "integer
>>> arithmetic with doubles isn't exact" issue (leads to values ever
>>> slightly smaller than what they would need to be).

>>
>> Integer arithmetic with doubles _is_ exact though, if the integers can
>> be exactly-represented as doubles ...

>
> For IEEE double precision, 2^100 and 1 are both exactly representable,
> so is the result of multiplying or dividing them, but their sum and
> difference are not exactly representable.


Well "the integers" should include the answer of course!

-miles

--
Accordion, n. An instrument in harmony with the sentiments of an assassin.
 
Reply With Quote
 
BGB
Guest
Posts: n/a
 
      02-14-2012
On 2/13/2012 9:25 PM, Miles Bader wrote:
> BGB<(E-Mail Removed)> writes:
>>> Integer arithmetic with doubles _is_ exact though, if the integers can
>>> be exactly-represented as doubles (which appears to be the case here).

>>
>> yes.
>>
>> the issue may be partly a matter of HW though, as I am seeing it on my
>> HW (using an AMD chip), but apparently someone else is not seeing it
>> (with an Intel chip), but there does seem to be a pattern in the values
>> (apparently: 0x4, 0x40, 0x400, 0x4000, ..., so for whatever reason
>> integer results which should land on one of these values is off by a
>> tiny amount...).

>
> Any conventional PC-type system these days is going to use IEEE FP,
> and if the system claims to support IEEE FP, it has to be exact. If
> it isn't, it's a bug.
>
> I did run your program on my AMD system (phenom I), and it showed no
> output. It would be interesting to see somebody with an identical CPU
> to yours try it...
>


I don't know.

in the past, the issue seemed specific to Linux x86-64 (and SSE), but I
am also currently getting the same results from a 32-bit Windows program
(using the x87 FPU, compiled with GCC).

testing with MSVC, the results slightly are different (only 4 different
values show up), but the basic issue is still present.


>> it could be a minor issue of the "arithmetic with doubles may not be
>> exact even if the doubles represent integers" variety, which is odd, but
>> whatever (it can be compensated for by fudging the value).

>
> I'm not sure you could call it a minor issue. A lot of software
> assumes that FP arithmetic is exact for integer values within a
> certain range, and isn't going to do any fudging (because it shouldn't
> be necessary, and would have a severe performance impact), so such a
> system where fudging is necessary would have ... problems.
>


potentially, yes.

however, other than this, the computer seems to work fine (nothing is
obviously acting buggy or crashing...).
 
Reply With Quote
 
BGB
Guest
Posts: n/a
 
      02-14-2012
On 2/13/2012 11:24 PM, Robert Wessel wrote:
> On Mon, 13 Feb 2012 18:31:48 -0700, BGB<(E-Mail Removed)> wrote:
>
>> On 2/13/2012 5:46 PM, Ben Bacarisse wrote:
>>> BGB<(E-Mail Removed)> writes:
>>>
>>>> On 2/13/2012 3:00 PM, Ben Bacarisse wrote:
>>>>> BGB<(E-Mail Removed)> writes:
>>>>> <snip>
>>>>>> also, even though double has more bits than, say, an integer, does not
>>>>>> mean it will reliably encode an integer's value (it can do so in
>>>>>> theory, and will most often do so, but whether or not it will actually
>>>>>> always do so is more "up for grabs").
>>>>>
>>>>> It's not up for grabs in C (and C++ is essentially the same in this
>>>>> regard). If the integer can be represented exactly in the floating
>>>>> point type, it must be.
>>>>>
>>>>
>>>> theoretically, yes.
>>>>
>>>> given a double has 52 bits, and int is 32 bits, and it is possible to
>>>> convert exactly, it should always be reliable.
>>>>
>>>> but, I have seen it not work exactly right, albeit in rare cases (IME,
>>>> usually on 64-bit Linux systems, generally fairly rare and when using
>>>> AMD chips IME).
>>>>
>>>> I haven't seen the issue on Win64 though that I can remember, nor with
>>>> 32-bit code, so I don't know.
>>>>
>>>> it "might" have something to do with SSE for all I know (since 32-bit
>>>> code typically uses x87, and 64-bit typically uses SSE), or maybe
>>>> something to do with GCC, or similar.
>>>>
>>>> might require researching, like trying to figure how exactly AMD chips
>>>> implement the "cvtsi2sd" and "cvtsd2si" instructions or similar... (I
>>>> am not even particularly sure which side of the conversion would have
>>>> been introducing a loss of accuracy, or if the cause could be
>>>> something else "in the middle" somewhere).
>>>
>>> Since this behaviour is required for C implementations to be conforming,
>>> deviation from it is important. Was there perhaps a bug report filed?
>>>

>>
>> not at the time, I merely thought of it as an interesting occurrence and
>> worked around it.
>>
>>
>>> <snip>
>>>>>> one can counteract this by fudging the value with a small epsilon
>>>>>> prior to converting back into an integer.
>>>>>>
>>>>>> say, for example (untested, from memory):
>>>>>> (v>=0)?((int)(v+0.0001))(int)(v-0.0001));
>>>>>
>>>>> I can't see how this helps. If v is representable exactly as a double,
>>>>> the round trip has no effect so this code is not needed. Can you give me
>>>>> a use-case?
>>>>>
>>>>
>>>> generally, I had seen it in my 3D engine, where in some cases integers
>>>> ended up getting converted to doubles and back, and sometimes they
>>>> would get "bumped" in this way. adding a small adjustment seemed to
>>>> fix the problem.
>>>
>>> Can you add a test to the code to print v when
>>>
>>> (int)(double)v != v&&
>>> (v>= 0 ? (int)(v+0.0001) : (int)(v-0.0001)) == v
>>>
>>> ? That way we might get an example of the problem you are reporting.
>>>

>>
>> I would have to find an example of it again...
>>
>> I remember seeing the problem a few years ago in some code of mine, but
>> don't have any recent memory of bugs resulting from it (but, then again,
>> this could also be due to code paranoia...).
>>
>> just went and tried to recreate it, with mixed results:
>> a raw conversion does not show any issues (seems to always be reliable);
>> if I add a value to the double, and subtract the same value, then it
>> starts acting up.
>>
>> testing the code below in Fedora 13 x86-64 within VMware (yes, not the
>> raw HW, but I would otherwise have to reboot).
>>
>> #include<stdio.h>
>>
>> int main()
>> {
>> double d;
>> int i, j, k;
>>
>> for(i=0; i<100000000; i++)
>> {
>> j=rand()*rand()*i;
>> d=j;
>> d=d+1.0; //(1)
>> d=d-1.0; //(1)
>> k=d; //(2)
>> k=(d>=0?(int)(d+0.0001)int)(d-0.0001)); //(2)
>> if(j!=k)
>> printf("%d %d\n", j, k);
>> }
>> }
>>
>> 1: if these lines are commented out, then the printf is never called,
>> but if uncommented (along with using different constant values), then I
>> start seeing messages (with it off-by-one, rounded towards 0).
>>
>> 2: if I switch to the second form, which makes the fudging, then the
>> messages disappear (they still appear with the first form).
>>
>> so, it would seem to be mostly an issue in this case of whether or not
>> one does any arithmetic on the values (not sure whether or not this
>> still counts). CPU is an "AMD Athlon II X4 630".
>>
>> or, at least, this is what I am seeing here...
>>
>>
>> here is the inner part of the loop (in ASM):
>> .L4:
>> movl $0, %eax
>> call rand
>> movl %eax, %ebx
>> movl $0, %eax
>> call rand
>> imull %ebx, %eax
>> imull -20(%rbp), %eax
>> movl %eax, -24(%rbp)
>> cvtsi2sd -24(%rbp), %xmm0
>> movsd %xmm0, -32(%rbp)

>
>> movsd -32(%rbp), %xmm1
>> movsd .LC0(%rip), %xmm0
>> addsd %xmm1, %xmm0
>> movsd %xmm0, -32(%rbp)
>> movsd -32(%rbp), %xmm0
>> movsd .LC0(%rip), %xmm1
>> subsd %xmm1, %xmm0
>> movsd %xmm0, -32(%rbp)
>> movsd -32(%rbp), %xmm0
>> cvttsd2si %xmm0, %eax
>> movl %eax, -36(%rbp)
>> movl -24(%rbp), %eax
>> cmpl -36(%rbp), %eax
>> je .L3
>> movl $.LC1, %eax
>> movl -36(%rbp), %edx
>> movl -24(%rbp), %ecx
>> movl %ecx, %esi
>> movq %rax, %rdi
>> movl $0, %eax
>> call printf
>> .L3:
>>
>> ...
>>
>> .LC0:
>> .long 0
>> .long 1072693248

>
>
> The explanation for this, at least, seems simple. You're overflowing
> the dynamic range of a double. 32767*32767*100000000 needs a bit more
> than 56 bits to represent exactly. That doesn't fit in a double
> (assuming an IEEE double, of course). Nor do the results of that
> number plus or minus 1.0. If the ints on your system are 32 bit,
> there should be no problem, as the number will be reduced to 32 bits
> first, if they're 64 bits, you'll have round off error.
>


this is on x86 and x86-64, and in both cases "int" is 32 bits.
storing the expression into an int essentially truncates it to 32-bits.

if it were a "long long", it would be a different matter.


> I've not looks through all the combinations, but the compilers could
> be setting rounding differently, and even for x87 and SSE2
> instructions rounding can be set differently at the same time.
> Rounding can be different between the x87 store-as-int (FIST rounds
> according to the selected x87 rounding mode), SSE2 convert-to-int
> (CVTTSD2S always truncates towards zero) and software convert-to-int
> (which can do whatever the implementers fancied). Those different
> rounding modes could to a lesser or greater degree be masking the
> problem. Another variable is that on some implementations, the x87 FP
> calculations are done in 80-bit format, at least some of the time, so
> you might see no round off errors at all in those cases.


yeah.

dunno the what exactly is the issue, but it is probably fairly minor
given the lack of any obvious problems...

as noted, when I had seen it before, I had simply assumed that it was
some basic property of floating-point behavior and fudged it. if other
people have been seeing similar behavior, it is possible maybe such
fudging is fairly common?...

 
Reply With Quote
 
MikeWhy
Guest
Posts: n/a
 
      02-14-2012
BGB wrote:
> On 2/13/2012 9:25 PM, Miles Bader wrote:
>> BGB<(E-Mail Removed)> writes:
>>>> Integer arithmetic with doubles _is_ exact though, if the integers
>>>> can be exactly-represented as doubles (which appears to be the
>>>> case here).
>>>
>>> yes.
>>>
>>> the issue may be partly a matter of HW though, as I am seeing it on
>>> my HW (using an AMD chip), but apparently someone else is not
>>> seeing it (with an Intel chip), but there does seem to be a pattern
>>> in the values (apparently: 0x4, 0x40, 0x400, 0x4000, ..., so for
>>> whatever reason integer results which should land on one of these
>>> values is off by a tiny amount...).

>>
>> Any conventional PC-type system these days is going to use IEEE FP,
>> and if the system claims to support IEEE FP, it has to be exact. If
>> it isn't, it's a bug.
>>
>> I did run your program on my AMD system (phenom I), and it showed no
>> output. It would be interesting to see somebody with an identical
>> CPU to yours try it...
>>

>
> I don't know.
>
> in the past, the issue seemed specific to Linux x86-64 (and SSE), but
> I am also currently getting the same results from a 32-bit Windows
> program (using the x87 FPU, compiled with GCC).
>
> testing with MSVC, the results slightly are different (only 4
> different values show up), but the basic issue is still present.


The MSVC warnings are rather explicit:
"... possible loss of data".
'initializing' : truncation from 'const uint_64' to 'const double'
'initializing' : conversion from 'const double' to 'const uint_64', possible
loss of data

Z:\Foo>fooFP.exe
sizeof(uint_64) ==> 8
std::numeric_limits<double>::digits = 53
std::numeric_limits<uint_64>::digits = 64
(18446744073709551615 == 922337203685477580 ==> false
(18446744073709551615 == 922337203685477580 ==> false

On gcc:

mikey@boatVPM-Linux:~/Foo$ g++ --version
g++ (Ubuntu/Linaro 4.6.1-9ubuntu3) 4.6.1
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

mikey@boatVPM-Linux:~/Foo$ g++ -std=c++0x -Wall -pedantic fooFP.cpp
fooFP.cpp: In function âint main()â:
fooFP.cpp:21:30: warning: overflow in implicit constant conversion
[-Woverflow]
mikey@boatVPM-Linux:~/Foo$ ./a.out
sizeof(uint_64) ==> 8
std::numeric_limits<double>::digits = 53
std::numeric_limits<uint_64>::digits = 64
(18446744073709551615 == 0) ==> false
(18446744073709551615 == 18446744073709551615) ==> true
mikey@boatVPM-Linux:~/Foo$

The first case was similar to what you had written it. The second case used
'const uint_64' and const double as hints to the compiler. gcc actually
managed to get the second case right. I don't know what MSVC was thinking.
The integer value evaluated to (2^64 - 1) as expected. Converting back to
ULL from double produced 2^63. It apparently stored 1/2 * 2^64 as the FP
value, which is a surprising conversion (but still within the definition of
undefined behavior).

> however, other than this, the computer seems to work fine (nothing is
> obviously acting buggy or crashing...).


??!! It's a coding error. The compiler recognized the error and printed
diagnostics, warning about truncation or overflow in the conversion.
Comparing std::numeric_limits<double>::digits against
std::numeric_limits<unsigned long long>::digits makes clear the nature of
the problem.


 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      02-14-2012
Ben Bacarisse <(E-Mail Removed)> writes:
> BGB <(E-Mail Removed)> writes:

[...]
>> as I understand it, the entire range of 32 bit integers can be exactly
>> represented by a double.

>
> In the architecture in question, yes.

[...]

In any conforming C implementation; the requirements on double are such
that it can represent any 32-bit integer value exactly.

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
James Kuyper
Guest
Posts: n/a
 
      02-14-2012
On 02/14/2012 01:24 AM, Robert Wessel wrote:
> On Mon, 13 Feb 2012 18:31:48 -0700, BGB <(E-Mail Removed)> wrote:

....
>> #include <stdio.h>
>>
>> int main()
>> {
>> double d;
>> int i, j, k;
>>
>> for(i=0; i<100000000; i++)
>> {
>> j=rand()*rand()*i;
>> d=j;
>> d=d+1.0; //(1)
>> d=d-1.0; //(1)
>> k=d; //(2)
>> k=(d>=0?(int)(d+0.0001)int)(d-0.0001)); //(2)
>> if(j!=k)
>> printf("%d %d\n", j, k);
>> }
>> }
>>
>> 1: if these lines are commented out, then the printf is never called,
>> but if uncommented (along with using different constant values), then I
>> start seeing messages (with it off-by-one, rounded towards 0).


That's to be expected. As i gets larger, for some of the values that can
be returned by rand(),
>>
>> 2: if I switch to the second form, which makes the fudging, then the
>> messages disappear (they still appear with the first form).
>>
>> so, it would seem to be mostly an issue in this case of whether or not
>> one does any arithmetic on the values (not sure whether or not this
>> still counts). CPU is an "AMD Athlon II X4 630".
>>
>> or, at least, this is what I am seeing here...

....
> The explanation for this, at least, seems simple. You're overflowing
> the dynamic range of a double. 32767*32767*100000000 needs a bit more
> than 56 bits to represent exactly.


That number is 32767*32767*5^8 * 2^8. Representing the first part
exactly only requires 48 bits, and the 2^8 just shifts the exponent.
However, the actual maximum value that d can have is
32767*32767*99999999, and that does require 56 bits to represent exactly.

> ... That doesn't fit in a double
> (assuming an IEEE double, of course). Nor do the results of that
> number plus or minus 1.0. ...


That part is true, even when 'i' has a large power of 2 among it's factors.

There's no mystery about these results anymore - he's looking at integer
values that are too large for N and N+1 to both be exactly representable.
--
James Kuyper
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      02-14-2012
James Kuyper <(E-Mail Removed)> writes:

> On 02/14/2012 01:24 AM, Robert Wessel wrote:
>> On Mon, 13 Feb 2012 18:31:48 -0700, BGB <(E-Mail Removed)> wrote:

> ...
>>> #include <stdio.h>
>>>
>>> int main()
>>> {
>>> double d;
>>> int i, j, k;
>>>
>>> for(i=0; i<100000000; i++)
>>> {
>>> j=rand()*rand()*i;
>>> d=j;
>>> d=d+1.0; //(1)
>>> d=d-1.0; //(1)
>>> k=d; //(2)
>>> k=(d>=0?(int)(d+0.0001)int)(d-0.0001)); //(2)

[The reported error come when the above line is commented out]
>>> if(j!=k)
>>> printf("%d %d\n", j, k);
>>> }
>>> }

<snip>
>> ... That doesn't fit in a double
>> (assuming an IEEE double, of course). Nor do the results of that
>> number plus or minus 1.0. ...

>
> That part is true, even when 'i' has a large power of 2 among it's factors.
>
> There's no mystery about these results anymore - he's looking at integer
> values that are too large for N and N+1 to both be exactly
> representable.


That's not what's happening. On the system in question, int has only
32 bits. The large and possibly overflowing value is assigned to an
int first. This conversion is implementation defined, but it can't make
j too large to represented exactly in d. In fact, one of his reported
error cases was caused when j == 4. This *must* set d to 4.0 (and it
did). The subsequent +1.0 and -1.0 and conversion back to int produces
a value not == 4.

I agree there is no mystery, but it's not using integers too large for
double -- it's floating-point arithmetic is not exact.

[Aside: since the integer arithmetic can overflow, technically the
program has undefined behaviour. So while d may be assigned 4.0, say,
it is quite permissible (from C's point of view) for it to become 5.0 or
109.2 or any other value at any time. I'm assuming a sane
implementation.]

--
Ben.
 
Reply With Quote
 
glen herrmannsfeldt
Guest
Posts: n/a
 
      02-14-2012
In comp.lang.c++ Robert Wessel <(E-Mail Removed)> wrote:

(snip, someone wrote)
>>Not C, but C-on-a-system-using-IEEE-FP, which is basically everything
>>mainstream. [In practice it's a pretty good bet that even wackier FP
>>hardware actually maintains the same constraint.]


> Apparently you never tried to multiply or divide on any early Crays.
>


> Multiplication could be off by a full ULP. So products that exactly
> filled all 48 bits with significant bits often produced slightly odd
> results.


Is that also the one with the non-commutative multiplication?

-- glen
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C/C++ pitfalls related to 64-bits (unsigned long & double) Alex Vinokur C++ 60 02-15-2012 08:00 AM
Having compilation error: no match for call to ‘(const __gnu_cxx::hash<long long int>) (const long long int&)’ veryhotsausage C++ 1 07-04-2008 05:41 PM
long long and long Mathieu Dutour C Programming 4 07-24-2007 11:15 AM
unsigned long long int to long double Daniel Rudy C Programming 5 09-20-2005 02:37 AM
Assigning unsigned long to unsigned long long George Marsaglia C Programming 1 07-08-2003 05:16 PM



Advertisments