> On 12 Jun 2025, at 14:50, Tiago Freire <tmiguelf_at_[hidden]> wrote:
>
> Of unsigned integers, In order to detect the overflow all you have to do in your example:
> a1 ≥ b

I have implemented this, which incidentally I used in the debugging code. :-)

So it means your proposal is sufficient for this multiprecision division implementation.

> If you also can guarantee that the most significant bit of 'b' is set (and this condition is extremely important otherwise the following won't work),

Yes, I left-shift the top part needed in the two-word by one-word division.

> then you can just do this:
>
> if(a1 < b)
> { //no overflow
> auto result = div_wide(a1, a0, b);
> }
> else //overflow
> {
> auto result = div_wide(a1 - b , a0, b);
> //extra bit handling goes here
> }

I use, where the remainders are currently not used:
if (a1 < b0)
  std::tie(q0, r0) = div(a0, a1, b0);
else {
  r0 = b0 + a0; // Same as div(a0, Word(a1 - b0), b0)
  q0 = -1;
}

One example where the overflow occurs is with word type uint16_t, and in a = q b + r, set
a = ₓ7fff800100000000
b = ₓ800080020005
q = ₓfffd
r = ₓ80008001000f
In the computation, there is an iteration with values
a1 a0 = ₓ8000 8001
   b0 = ₓ8000
q1 q0 = ₓ1 0001
When setting q0 = β - 1 = ₓffff, one gets r1 r0 = ₓ1 0001.

I think that in a suggested division algorithm, one reduces q1 q0 with one and increases r0 with b0 to get r0 = ₓ8001, and then stops because r0 ≥ b0. Then after adding q1 q0 to q, the value a - q*b is negative, and has to reduce q one step more. As I work with unsigned numbers, I use a different approach:

I merely compare q*b > a in a for-loop, and if true, decrease q0 (or q1 q0 if using the overflow) with 1 at most two times. After that, compute a - q*b which becomes the new dividend which finally will produce the remainder.

Then there are optimizations using the remainders, which I may look into later.

Also, I use binary division, which is easy to implement, to check the results.