ascorbic 307 Report post Posted May 8, 2007 I recently had this question asked of me in an interview and didn't really know how to answer it. The question had to do with a templated function that determined if two numbers were within a certain tolerance and thus could be considered the same number or not. a and b are basically numbers, tol is the allowable difference between the numbers. I simplified the function just to magnify the question. Most of the time this function works properly. template <class T> bool isDifferent(T a, T b, T tol) { return (a-b)>tol; // plus "or" something I don't remember... unimportant to question... } If a=4, b=3, tol=5, then 4-3>5 is 1>5 is false... which is expected. However, if we use unsigned chars for T, then the following could be true. If a=0, b=2, tol=5, then 0-2>5 is 254>5, which is true, which is NOT expected. The question was then asked of how to fix the function to account for this. I really had no idea. I figured to account for this, you could do a check like: if((a-b) > a) { return (b-a)>tol; // b is bigger than a - underflow with (a-b) } else { return (a-b)>tol; // a is bigger than b - no problem } This doesn't seem right... but maybe it is. This fixes the problem with unsigned numbers. But now what about signed numbers? Sorry for the long winded and confused question. So bottom line, how do you correctly account for overflow/underflow to make this function robust for all data types? Thanks! 0 Share this post Link to post Share on other sites
dragongame 538 Report post Posted May 8, 2007 Hi,why not do it like the following?template <class T>bool isDifferent(T a, T b, T tol){return a>b?((a-b)>tol):((b-a)>tol);} 0 Share this post Link to post Share on other sites
MaulingMonkey 1730 Report post Posted May 8, 2007 My first instinct is this: Unit testing.A few numbers to plug into a, b, and tol for these checks:0, std::numeric_limits<T>::max/min(), +/-1, +/- _other_magic_numbers_here_Given that every single +/- of any of a, b, and tol, must be assumed to be able to overflow, unless explicitly checked by a corresponding comparison first. I think I'd even start with a truth table like so:Presumptions:tol >= 0 (negative tolerance makes no sense -- equasion should be short circuited or abs()ed (or throwing?) previously) a | b | sane equasion | notes + + | (max(a,b)-min(a,b)) < tol | max(a,b)-min(a,b) must be positive, and no larger than known positive min(a,b) -- so there is no chance of over/underflow + - | a < tol+b | a-b < tol with +b to both sides tol+b can be no larger than tol, and no smaller than b -- so no chance of over/underflow - + | b < tol+a | b-a < tol with +a to both sides same rationale as above - - | (max(a,b)-min(a,b)) < tol | *specialThe last problem seems non-trivial on account of negative numbers not necessairly having the same range as positive ones, making sign inversion problematic, as well as the possibility of two negative numbers having a greater distance between them than the largest positive one. Fortunately, the extreme practical case on most modern systems would be:-1, -2147483648 == +2147483647Which exactly fits into the maximum range of a positive int on most systems. But of important note: "0, -2147483648" would not work, so the truth table must include 0 as "positive" (or special case it, which would be a bit silly).EDIT:A fix for the problem -- the original equasion should be used if std::numeric_limits<T>::max() > -std::numeric_limits<T>::min(), or is close enough. If -std::numeric_limits<T>::min() is sufficiently larger than std::numeric_limits<T>::max, this would be an alternative:(min(a,b)-max(a,b))+tol > 0the min/max bit is just a sign reversed version of the original, resulting in a negative representation of the difference -- so we could say mathematically:(min(a,b)-max(a,b)) > -tolEDIT: Forgot a sign flip there too.As our condition -- and we just add +tol to both sides to get a version which may actually work everywhere. For some reason I was recalling that I had a corner case for which this wouldn't work for <T>::max() > -<T>::min(), but I can't recall it now. EDIT: ahh right -- (...) - tol could underflow if max() > -min(), if tol == max() and (...) == 0As for figuring out wheither T has larger max() than -min():bool T_max_higher_magnitude_than_min = std::numeric_limits<T>::max()/std::numeric_limits<T>::min() <= -1;round-to-zero assures us that if -min() > max(), the result will be 0 <= -1. And it "just works" ™ for floating point numbers -- barring rounding errors (hah, yeah right) at least :D[Edited by - MaulingMonkey on May 8, 2007 1:56:22 AM] 0 Share this post Link to post Share on other sites
MaulingMonkey 1730 Report post Posted May 8, 2007 Quote:Original post by dragongameHi,why not do it like the following?*** Source Snippet Removed ***This is why:#include <iostream>#include <limits>template <class T>bool isDifferent(T a, T b, T tol){ std::cout << "isDifferent( " << a << ", " << b << ", " << tol << " ) == "; bool different = a>b?((a-b)>tol):((b-a)>tol); std::cout << (different?"true":"false") << std::endl; return different;}int main() { isDifferent( std::numeric_limits<int>::max() , std::numeric_limits<int>::min() , 0 ); isDifferent( std::numeric_limits<int>::min() , std::numeric_limits<int>::max() , 0 );} isDifferent( 2147483647, -2147483648, 0 ) == falseisDifferent( -2147483648, 2147483647, 0 ) == falsePress any key to continue . . . _[Edited by - MaulingMonkey on May 8, 2007 1:03:00 AM] 0 Share this post Link to post Share on other sites
ascorbic 307 Report post Posted May 8, 2007 Thanks so much MaulingMonkey! I figured there were a couple branches in the logic. You're saying that a function as follows is needed:template <class T>bool isTheSameNumber(T a, T b, T tol){ if(a >= 0) { if(b >= 0) { return (max(a,b) - min(a,b)) < tol; } else { return (a < tol + b); } } else { if(b >= 0) { return (b < tol + a); } else { return (max(a,b) - min(a,b)) < tol; } }}Probably why I didn't get the job! Thanks for the help!EDIT: Not exactly right... per your edit above... but good enough to shed light on my problems... thanks for everything! 0 Share this post Link to post Share on other sites
MaulingMonkey 1730 Report post Posted May 8, 2007 Quote:Original post by ascorbicThanks so much MaulingMonkey! I figured there were a couple branches in the logic. You're saying that a function as follows is needed: Here's my revised version:#include <algorithm>template < typename T >bool is_equivilant( T a, T b, T tolerance ) { using std::max; using std::min; if ( a >= 0 ) { if ( b >= 0 ) { return (max(a,b)-min(a,b)) < tol; /* max(a,b)-min(a,b) must be positive, * and no larger than known positive * min(a,b) -- so there is no chance * of over/underflow */ } else /* b < 0 */ { return a < tol+b; /* a-b < tol with +b to both sides * tol+b can be no larger than tol, and * no smaller than b -- so no chance of * over/underflow */ } } else /* a < 0 */ { if ( b >= 0 ) { return b < tol+a; /* b-a < tol with +a to both sides * tol+a can be no larger than tol, and * no smaller than a -- so no chance of * over/underflow */ } else /* b < 0 */ { static const bool T_max_magnitude_gt_min = std::numeric_limits<T>::max()/std::numeric_limits<T>::min() <= -1; if ( T_max_magnitude_gt_min ) { return (max(a,b)-min(a,b)) < tol; /* mostly the same rationale as a>=0, b>=0 * special considerations: maximum difference * between negative numbers is less than max */ } else { return (min(a,b)-max(a,b)) > -tol; /* same equasion as above, only sign flipped to * keep intermediate calculations negative, since * the difference might not be expressible as a positive * number due to an overflow */ } } }}This is of course the anal-retentive insanity inducing version.EDIT: forgot to flip the inequality in the sign flip as well.And people wonder why programs have so many bugs ;-). 0 Share this post Link to post Share on other sites
Bregma 9221 Report post Posted May 8, 2007 Quote:Original post by MaulingMonkeyThis is of course the anal-retentive insanity inducing version.But it's a template function. You could dispatch to specialized versions to eliminate half the code for unsigned integral types, not to mention your T_max_magnitude_gt_min value. What kind of nutty insanity do you really hope to induce without function template specialization? Don't forget about std::numeric_limits<T>::is_signed. 0 Share this post Link to post Share on other sites
MaulingMonkey 1730 Report post Posted May 8, 2007 Quote:Original post by BregmaQuote:Original post by MaulingMonkeyThis is of course the anal-retentive insanity inducing version.But it's a template function. You could dispatch to specialized versions to eliminate half the code for unsigned integral types, not to mention your T_max_magnitude_gt_min value. What kind of nutty insanity do you really hope to induce without function template specialization? Don't forget about std::numeric_limits<T>::is_signed. If I dispatch of half my code per function, but increase my specializations by 4-fold, what have I gained? More code X_x.!is_signed would just be a way of verifying always-true for "a>=0" or "b>=0", which the compiler should be smart enough to optimize on it's own, and optimizations that I can't apply to the general case (nor magically disappear for all the specialized cases). What, pray tell, could be eliminated from the function if this were the specialization for <int> ? Or <short> ? I suspect the compiler is smart enough to optimize T_max_magnitude_gt_min into a constant as well.[Edited by - MaulingMonkey on May 8, 2007 6:23:17 PM] 0 Share this post Link to post Share on other sites