Tuesday, November 02, 2004

How to represent INFINITY in ur programs

No doubt every one might have come across this in their programming experience, on how to represent the theoritical infinity in the programs.
Example: -----------
Most candid use of INFINITY is to use them in graphs to represent two nodes which are not connected ie if we dont have any edge between two nodes N1 and N2 then we represent the cost of the edge as INFINITY. in the implementation of the dijkstra's algorithm on a graph we generally, come across a condition 'CURRENT_COST > CURRENT_COST + WEIGHT_OF_EDGE' then update the path. Theoritically INFINITY+1 = INFINITY. So if some one just does a #define INFINITY __SOME_LARGE_NUMBER, then INFINITY+1 will not be INFINITY. And the conditions just as the ones illustrated above will become buggy. The following representation of infinity is more shrewd than the ordinary #def's
/*
* The following coordinate, INFINITY, is used to represent a
* tile location outside of the tile plane.
*
* It must be possible to represent INFINITY+1 as well as
* INFINITY.
*
* Also, because locations involving INFINITY may be transformed,
* it is desirable that additions and subtractions of small integers
* from either INFINITY or MINFINITY not cause overflow.
*
* Consequently, we define INFINITY to be the largest integer
* representable in wordsize - 5 bits.
*/

#undef INFINITY
#define	INFINITY	((1 << (8*sizeof (int) - 6)) - 4)
#define	MINFINITY	(-INFINITY)

No comments: