RFR: 8282365: Consolidate and improve division by constant idealizations [v44]

[Quan Anh Mai]

On Tue, 23 Jan 2024 13:30:46 GMT, Raffaello Giulietti <rgiulietti at openjdk.org> wrote:

>> The convoluted test to break out of the while loop can be simplified if we are willing to consider two cases.
>> 
>> Equality in `c / m <= (1 / d) * ((v + 1) / v)` is equivalent to `c / m = b / v`, where `b = (v + 1) / d` is an integer. Note that the fraction `b / v` is irreducible: a common divisor of `b` an `v` has to divide any linear combination as well, in particular it has to divide `d * b - 1 * v = 1`. Thus, `c >= b` and `m >= v`. Since `m = 2^s`, `v` must be a power of 2.
>> 
>> This means that, when `m` is a power of 2, the only way to have equality is `v_neg > v_pos` _and_ `v_neg` is a power of 2 (say `v_neg = 2^e`), which should be a rare case. This can be detected cheaply early, before the loop. In such a  case, the smallest `c` is `b` and the smallest `s` is `e`, and a result meeting `s >= min_s` doesn't need any iterative algorithm.
>> 
>> Otherwise equality does not hold. Now, `c / m < (1 / d) * ((v + 1) / v)` is equivalent to `m > v * rc`. In turn, `m > v * rc` <=> `m / v > rc` <=> `ceil(m / v) > rc`.
>> 
>> Thus, rather than maintaining invariants for `qv = floor(m / v)` and `rv = m - qv * v` as currently defined, we can redefine them as `qv = ceil(m / v)` and `rv = qv * v - m` (`0 <= rv < v`) and maintain _these_ invariants instead.
>> 
>>   T qv = 1;
>>   T rv = v - 1;
>>     ...
>>     if (rv >= v - rv) { // 2 * rv >= v
>>       qv_ovf = qv > min_signed;
>>       qv = qv * 2 - 1;
>>       rv = rv * 2 - v;
>>     } else {            // 2 * rv < v
>>       qv_ovf = qv >= min_signed;
>>       qv = qv * 2;
>>       rv = rv * 2;
>>     }
>> 
>> The test to exit the loop then reduces to `qv > rc || qv_ovf`.
>
>> such a case, the smallest c is b and the smallest s is e, and a result meeting s >= min_s doesn't need any iterative algorithm.
> 
> I must correct this claim, my bad.
> A result meeting `s >= min_s` might still need an iterative algorithm if `e < min_s` and if `c` must be minimal.

That is an excellent analysis. To add to the analysis, we do not really need the minimal value of `c`, since 2 values of `c` that both satisfy the inequations must give the same upper bits for all input values. As a result, for the purpose of the algorithm, they are equivalent.

My concern is that it will complicate the analysis, which is complicated enough, for a minor improvement in the exit conditions.

-------------

PR Review Comment: https://git.openjdk.org/jdk/pull/9947#discussion_r1463403251