gecode icon indicating copy to clipboard operation
gecode copied to clipboard

Fixing one off in the uniform_on_restart bug.

Open kieronqtran opened this issue 4 months ago • 2 comments

This pull request makes a small but important fix to the random value assignment logic in the gecode/flatzinc/flatzinc.cpp file. The change ensures that the generated random integer values can include the upper bound of the specified range, correcting an off-by-one error. This is happened becasue Rnd _random input domain is [lower_bound, upper_bound) and + 1 to correct set to [lower_bound, upper_bound], and it is effect to uniform_on_restart constraints.

  • Fixed the calculation of random values for uniform integer ranges to include the upper bound by changing the random range from (range.second - range.first) to (range.second - range.first + 1).

kieronqtran avatar Oct 17 '25 10:10 kieronqtran

This fix looks good to me. As you pointed out, I didn't see that the Rnd::operator() gives a value in the range [0,n) instead of [0,n] as I expected.

The same issue actually is also present for floating point, although in a different form:

const FloatVal rndVal = (static_cast<FloatVal>(_random(INT_MAX)) / INT_MAX)*(range.second - range.first) + range.first;

This will never reach the upper bound, as the division will never reach one because INT_MAX is excluded. To fix this, we might have to give up some of the granularity in the division and reduce the right-hand side of the division:

const FloatVal rndVal = (static_cast<FloatVal>(_random(INT_MAX)) / (INT_MAX-1))*(range.second - range.first) + range.first;

This seems fine, and I think any other fix would require an inclusive version of the random number generator, which would be more work.

Dekker1 avatar Oct 26 '25 23:10 Dekker1

Updated for uniform_on_researt for float. Thank @Dekker1

kieronqtran avatar Nov 10 '25 03:11 kieronqtran