Sign in to follow this  
ascorbic

C++ Templates and Overflow/Underflow Issues

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Evil 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 | *special


The 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 == +2147483647

Which 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 > 0

the 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)) > -tol

EDIT: 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 (...) == 0

As 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]

Share this post


Link to post
Share on other sites
Quote:
Original post by dragongame
Hi,

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 );
}


Boo
isDifferent( 2147483647, -2147483648, 0 ) == false
isDifferent( -2147483648, 2147483647, 0 ) == false
Press any key to continue . . . _


[Edited by - MaulingMonkey on May 8, 2007 1:03:00 AM]

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Quote:
Original post by ascorbic
Thanks so much MaulingMonkey! I figured there were a couple branches in the logic. You're saying that a function as follows is needed:


Evil 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 ;-).

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
This 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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Bregma
Quote:
Original post by MaulingMonkey
This 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.


Hmm 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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this