C++ Logo

std-proposals

Advanced search

Re: [std-proposals] Integer overflow arithmetic with exceptions

From: Hans Åberg <haberg_1_at_[hidden]>
Date: Thu, 12 Jun 2025 11:16:10 +0200
I made a class basic_natural<Word> for multiprecision unsigned integers that includes multiprecision division:

It would be good to have overflow reported in the function that divides two words with one, as that may happen in multiprecision division with more than one word. When dividing with just one word, as in the example of your proposal, it is not needed.

A method to divide with more than one word is to shift left so that the top word of the divisor has the high bit set, and one can then show that the division of the two top words of the (also shifted left) dividend overshoots the correct value with at most 2. But it means that overflow can and will occur.

The optimization I mentioned earlier, to have the lowest word always present, I have implemented via a class nonempty_vector that can be used instead of std::vector:
template <class A>
class nonempty_vector {
  A a0_ = A();
  std::vector<A> as_;
  …
};
It may be of independent interest, though I do not know any other use case.

Currently, one can switch between using this class and std::vector, but I will probably remove the latter at some point.

Possibly one can optimize further if there is access to CPU traps.

Received on 2025-06-12 09:16:26