Fix incorrect verdict for prodbin-ll_unwindbound50.yml and prodbin-ll_unwindbound100.yml
The two benchmarks nla-digbench-scaling/prodbin-ll_unwindbound50.yml and nla-digbench-scaling/prodbin-ll_unwindbound100.yml have an incorrect verdict. They should be labeled as correct. There is why:
- The first assertion
z + x * y == (long long) a * bis a loop invariant, so it can never be violated. - Therefore a possible counterexample has to violate the assertion
__VERIFIER_assert(z == (long long) a * b);after the loop. - To violate this assertion we cannot execute the
break, since the loop invariant together with the if-condition implies the assertion.- Therefore we need to execute the loop completely, i.e.
Ntimes (given in the filename). - Therefore
ymust always be greater than zero.
- Therefore we need to execute the loop completely, i.e.
- Since
yis divided by two in every iteration (the subtraction is irrelevant), it has the value\lfloor b / 2^i \rfloorin the i-th iteration. - This means that
\lfloor b / 2^{N-1} \rfloor \gt 0(yis allowed to be 0 only in the very last iteration) and thereforeb \geq 2^{N-1}. - On the other hand
bis anint(32bit), thereforeb \leq 2^{31}-1. - This concludes that there only exists a counterexample for
N \leq 31, i.e. the program is correct forN \gt 31.