NVIDIA Interview Question
Software Engineer / DevelopersAm I missing something or is a simple bitwise xor sufficient if all you want to know is equal or not? (a ^ b = 0 iff a==b). And ofcourse the bitwise operator cannot be applied to a float directly but as far as I know sizeof(long)==sizeof(float) {cant guarantee this and xor wont work if this isnt true but mostly it is}
so all we need to do is cast the reference to a long pointer and do a bitwise xor on the dereferenced values
long * a'=(long *)&a;
long * b'=(long *)&b;
return *a' ^ *b';//here assuming 0 means equal like in some
//inbuilt comparisons comparisons...
//otherwise put an if statement to return necessary value
Anonymous
Yes you are missing something, the very essence of the problem. Given the following statements:
float a = 1.0/3.0 + 1.0/3.0 + 1.0/3.0;
float b = 1.0;
given the previous values, now consider the implications of the statement.
a==b
The fundamental problem is floating point numbers are not exact representations so that in a variety of contexts two floating point numbers that should be equal are not.
The problem with your solution is it assumes floating point numbers are always exact representations.
It might benefit you to read the rest of the posts, your response seems to indicate that you have not read the additional posts or you didn't understand them.
Is it really necessary to compare byte by byte? yes we know that the floats are not represented accurately in the computer, however, if the internal representation of the two numbers are equal, they are equal, if they are not equal, they are not. unless these two numbers are deveried from some other calculations which cause the discrepancy due to the inaccurate internal representation, in this case, we could test based on a give precision, e.g., 0.00000000001, then we could do something like
if(abs(x-y))<=0.00000000001) return 1;(equal)
else return 0; (unequal)
correct me if I am wrong.
1) Using "(x==y)" where x and y are floating point data type should be sufficient for regular C/C++ code.
2) Compiler will generate code to call floating point emulation library APIs or invoke FPU instructions which convert the values to internal format(e.g., single, double, extended precision) and perform the "compare" operation to return the results.
Note that the relational operators (< <=, <, <=) and equality operators (==, !=) can be used for "compare".
qc,
I think you, most of the other posters, have missed the key point of this problem.
That key point is recognizing the issues with floating-point accuracy as indicated in previous posts by Anonymous on August 25 and Mohit on August 27.
As a software engineer it is important to be aware of the fact that the direct comparisons of floating-point values are almost always the wrong thing to do, due to the accumulation of rounding and cancelation errors.
The common way to resolve this problem for floating-point comparisons is to use some type of tolerance comparison. There are a number of techniques for doing this using absolute or relative tolerances or some combination for floating point comparison tests. The following code is an example of these techniques.
//-------------------------------------------------------------
// Reference "Real Time Collision Detection" by Christer Ericson
// published by Morgan Kaufmann; Copyright 2005
// ISBN-13 978-1-55860-7323 pp. 427-443
//-------------------------------------------------------------
// #include "math.h" // required for fabs & sqrt
// #include "float.h" // required for FLT_EPSILON definition
//-------------------------------------------------------------
//
// Use absolute comparison only, relatively cheap and works well over a wide range
bool IsAlmostEqualAbsolute(float x, float y, float maxAbsoluteError=1.0e-5f)
{
return ( fabs(x-y) <= maxAbsoluteError );
}
// By using the square root of the machine epsilon the numbers are
// required to agree to rougly half the number of positions available
// in the given machine representation.
const float MAX_FP_ERROR=sqrt(FLT_EPSILON);
// Use absolute and relative comparison combined, more expensive and
// is usually not necessary.
bool IsAlmostEqual(float x, float y, float maxError = MAX_FP_ERROR)
{
return( fabs(x-y) <= maxError*std::max(fabs(x),std::max(fabs(y),1.0f)) );
}
Bruce Dawson has an interesting article that discusses these issues in detail, “Comparing floating point numbers” and also has sample code.
You can find it at the following URL
http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm
In this article he even discusses a technique for converting floats to integers for doing comparisons, but I haven’t had much luck with that technique and have found the absolute and combination tolerance tests to work well.
Why can't we convert the floats to string ans then do string compare
We can use sprintf to convert from float to string.
We wont have any accuracy related issued if we do string compare
Or am I missing some thing ?
- LLOLer August 25, 2009