search

yongyanghz / LAPJV-algorithm-c

Jonker-Volgenant / LAPJV algorithm for the linear assignment problem, in C language
32 stars 11 forks source link

type issues that can lead to possible overflows #7

Closed Dharmesh946 closed 3 months ago

Dharmesh946 commented 3 months ago

During algorithm execution, according to cost nature and range of values in assigncost, some variables can overflow, noticeably d, v.

For instance, if cost is std::uintxx_t I observed that some negative values can occurred when reducing cost. On the tests I did, it happened to work anyway due to modulo arithmetic with integers but I'm not sure that larger overflows can not occur, leading failure in the algorithm.

Even if cost is double or the largest possible integer, some computations may overflow (typically the final total cost).

Besides BIG is not large enough. Why not set it to std::numeric_limits<cost>::max()?

I don't understand the algorithm (neither from the code, nor the original paper) and I'm enable yet to determine if it has properties that limits the range of possible internal values according to input costs range.

Could it be possible to do this analysis and improve the computation safety (wrt overflows)?

Btw, free could be holding booleans? Am I right? And it should be rename as it collisions with a langage keyword.

yongyanghz commented 3 months ago

Hi Dharmesh, Thanks for your valuable feedback and suggestions. For the following issues:

  1. double data type Overflow issue: Yes, it does exist when accumulate the path cost, double lost its precision: check this stackoverflow link
  2. Besides BIG is not large enough. Why not set it to std::numeric_limits::max()? Yes, set it to std::numeric_limits::max() is rational.
  3. free is not a good name for variable, should be renamed.

I will modify and test the code according to the above suggestions, and update the code.

Best regards, Yong Yang

Dharmesh946 commented 3 months ago

Thanks for your comment.

I overlooked the loss of precision but it may also be a concern (but I think that it might be negligible). My issue was more about overflow (dual variables exceeding their type range, if we want to use integral types).

Regards

yongyanghz commented 3 months ago

Updated code.

yongyanghz commented 3 months ago

Integer type for cost in not suggested due to the overflow issue, always use double for cost.