C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Efficient double comparison          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message Dave Guest Posted: Wed Mar 03, 2004 8:35 pm    Post subject: Efficient double comparison Hello all, I would like to solicit suggestions on how to most efficiently accomplish something. I have profiled the project I'm working on and have found that calls to fabs() are taking a very substantial amount of time. fabs() is being used in the following manner: double a, b; a = get_a_value(); b = get_another_value(); if (fabs(a - b) > 1E-9) // Do "not equal" stuff else // Do "equal" stuff So, we're simply comparing two doubles for equality and making allowances for inexact numeric representation. Of course, we could save time by reducing the number of comparisons. But, unfortunately, we do need all of the comparisons we're making - none are redundant or unused. So... Can anybody out there suggest a more efficient way of accomplishing these comparisons? Thanks, Dave Back to top Claudio Puviani Guest Posted: Wed Mar 03, 2004 11:37 pm    Post subject: Re: Efficient double comparison "Dave" <better_cs_now (AT) yahoo (DOT) com> wrote Quote: Hello all, I would like to solicit suggestions on how to most efficiently accomplish something. I have profiled the project I'm working on and have found that calls to fabs() are taking a very substantial amount of time. fabs() is being used in the following manner: double a, b; a = get_a_value(); b = get_another_value(); if (fabs(a - b) > 1E-9) // Do "not equal" stuff else // Do "equal" stuff So, we're simply comparing two doubles for equality and making allowances for inexact numeric representation. Of course, we could save time by reducing the number of comparisons. But, unfortunately, we do need all of the comparisons we're making - none are redundant or unused. So... Can anybody out there suggest a more efficient way of accomplishing these comparisons? You can always do something like this: inline bool simpleFuzzyEq(const double & v1, const double & v2, const double & epsilon) { const double diff = v1 - v2; return diff < epsilon && diff > -epsilon; } The extra comparison is far less expensive than a call to fabs() and most compilers will inline this to something extremely tight. As a side note, a fuzzy equality test with an absolute epsilon has an extremely limited scope and doesn't behave intuitively if the magnitudes of a comparand is very large. Claudio Puviani Back to top Marcin Kalicinski Guest Posted: Fri Mar 05, 2004 9:38 am    Post subject: Re: Efficient double comparison Hi, inline bool simpleFuzzyEq(const double & v1, const double & v2, const double & epsilon) { const double diff = v1 - v2; return diff < epsilon && diff > -epsilon; } Quote: The extra comparison is far less expensive than a call to fabs() and most compilers will inline this to something extremely tight. This is something I absolutely cannot agree about, at least for Intel 80x86 architecture. FABS operation done in 80x86 FPU takes exactly 1 cycle, and also pairs with the next operation (if they're not dependent). Practically - it is free. Comparison between 2 floating point numbers is a complex thing on the other hand. It can take as much as 4 cycles, plus extra instructions to copy the result from FPU registers to CPU registers (to actually do the conditional jump based on comparison result). Not to say that in the code above there is an extra unary negation op, which has usually the same complexity as FABS alone. And an extra '&&' operation... I don't know other CPU architectures, but I think it's the same way round. On 80x86, if precision up to 15th digit is not very important, I'd suggest switching to float data and using _control87() to force FPU to work in 24-bit precision mode. _control87() is non-standard, but present in most 80x86 compilers libraries: _control87(_PC_24, MCW_PC); // reduce precision // here put plenty of intensive floating point operations. They'll work much faster _control87(_PC_53, MCW_PC); // restore precision Best regards, Marcin U¿ytkownik "Claudio Puviani" <puviani (AT) hotmail (DOT) com> napisa³ w wiadomoœci news:E_t1c.46040$5M6.12628959 (AT) news4 (DOT) srv.hcvlny.cv.net... "Dave" <better_cs_now (AT) yahoo (DOT) com> wrote Quote: Hello all, I would like to solicit suggestions on how to most efficiently accomplish something. I have profiled the project I'm working on and have found that calls to fabs() are taking a very substantial amount of time. fabs() is being used in the following manner: double a, b; a = get_a_value(); b = get_another_value(); if (fabs(a - b) > 1E-9) // Do "not equal" stuff else // Do "equal" stuff So, we're simply comparing two doubles for equality and making allowances for inexact numeric representation. Of course, we could save time by reducing the number of comparisons. But, unfortunately, we do need all of the comparisons we're making - none are redundant or unused. So... Can anybody out there suggest a more efficient way of accomplishing these comparisons? You can always do something like this: inline bool simpleFuzzyEq(const double & v1, const double & v2, const double & epsilon) { const double diff = v1 - v2; return diff < epsilon && diff > -epsilon; } The extra comparison is far less expensive than a call to fabs() and most compilers will inline this to something extremely tight. As a side note, a fuzzy equality test with an absolute epsilon has an extremely limited scope and doesn't behave intuitively if the magnitudes of a comparand is very large. Claudio Puviani Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.