C++ algorithm for division between 2 signed integer intervals

Question

Consider intervals A = [x1, y1] and B = [x2, y2], two intervals representing signed integers.

Interval arithmetic page on Wikipedia gives a formula to address the case where B does not contain 0, whose C++ implementation may be as follows:

void print(const char* const what, int x, int y)
{
  std::cout << what << " = [" << x << ", " << y << "]\n";
}

void div(const char* const what, int x1, int y1, int x2, int y2)
{
  int v1 = x1/x2;
  int v2 = x1/y2;
  int v3 = y1/x2;
  int v4 = y1/y2;

  int x = std::min(std::min(v1, v2), std::min(v3, v4));
  int y = std::max(std::max(v1, v2), std::max(v3, v4));

  print(what, x, y);
}

int main()
{
  int x1 = -10000, y1 = 150000;
  int x2 = -10, y2 = 10;

  print("A", x1, y1);
  print("B", x2, y2);

  div("A/B", x1, y1, x2, y2);
}

Output:

A = [-10000, 150000]
B = [-10, 10]
A/B = [-15000, 15000]

As expected, the result is incorrect given that B contains 0. For example, since 1 is part of B, 150000 should be within A/B but it is not.

What is a viable algorithm when 0 is excluded from B? Should the solution use multiple intervals around -1 and 1 (i.e. exclude 0) and join them somehow?

Edit: the solution may be expressed in terms of a union (vector) of intervals of long long type.

Answer 1

You are not writing C++, you are writing C wrapped in some little C++ then and there. So here's what I would do:

First I would start with a class for an interval, i.e.:

struct Interval
{
    int left;
    int right;
};

Then I would start with addition, subtraction and multiplication. E.g.

auto operator+(Interval lhs, Interval rhs) -> Interval;

Which are quite simple.

When we get to division, as seen on your wiki link, things get more complicated.

1. The result is no longer an interval, but a multi-interval i.e. a conjunction of intervals.
2. These intervals have ∞ and -∞ heads.

The first problem is solved with a new class:

class MultiInterval
{
    std::vector<Interval> intervals_;
    //...
};

For the second problem ... well we can no longer use int as data. So you need a new class for integer that can contain the values ∞, -∞, NaN. NaN is required as a byproduct, e.g. -∞ + ∞ = NaN.

class ExtendedInt
{
    // black magic
};

for which you would have to define 3 constants that are the new 3 values. You would then need to define all of the basic arithmetic operations on them.

Finally we get to redo everything to something like this:

class ExtendedInt;
auto operator+(ExtendedInt lhs, ExtendedInt rhs) -> ExtendedInt;
auto operator-(ExtendedInt lhs, ExtendedInt rhs) -> ExtendedInt;
auto operator*(ExtendedInt lhs, ExtendedInt rhs) -> ExtendedInt;
auto operator/(ExtendedInt lhs, ExtendedInt rhs) -> ExtendedInt;
// etc...

struct Interval
{
    ExtendedInt left;
    ExtendedInt right;    
};

class MultiInterval
{
   std::vector<Interval> intervals_;
   //...
};

auto operator+(Interval lhs, Interval rhs) -> Interval;
auto operator-(Interval lhs, Interval rhs) -> Interval;
auto operator*(Interval lhs, Interval rhs) -> Interval;

auto operator/(Interval lhs, Interval rhs) -> MultiInterval;

As you can see things get complicated pretty fast.

---

As for how you would implement ExtendedInt one solution is to have two data members, one int and one enum

enum class ExtendedIntValues { Normal, Inf, NegInf, NaN };

class ExtendedInt
{
     int value_;
     ExtendedIntValues ext_value_;
};

if ext_value_ == Normal then the value of the instance is value_, else it is ext_value_.

Another solution is to realize that functionally that is an union. So you could use std::variant<int, ExtendedIntValues> instead.

Yet another solution is to use std::optional:

enum class ExtendedIntValues { Inf, NegInf, NaN }; // notice no Normal enum

class ExtendedInt
{
     std::optional<int> value_;
     ExtendedIntValues ext_value_;
};

All these solution sacrifice space with std::variant sacrificing usability.

Another solution that just sacrifices 3 normal int values is to have just one int and have some values represent the special cases:

class ExtendedInt
{
     int value_;
};
constexpr ExtededInt NegInf = ...;
constexpr ExtededInt Inf = ...;
constexpr ExtededInt NaN = ... ;

Internally:

• std::numeric_limits<int>::min() beeing NegInf
• std::numeric_limits<int>::max() - 1 is Inf
• std::numeric_limits<int>::max() is NaN

Or something like that, but that would have to be made completely transparent. Extra special care would have to be made to arithmetic operations.

Another solution is to realize there is already a type (or two) that natively support these values and go with float or double. This would sacrifice precision.

---

Once you have ExtendedInt figured out then just follow the wiki algorithm:

auto operator/(Interval lhs, Interval rhs) -> MultiInterval
{
    MultiInterval f1{lhs};
    MultiInterval f2{};

    if (!contains(rhs, 0))
        f2 = MultiInterval{{1 / rhs.right, 1 / rhs.left}};

    else if (rhs.right == 0)
        f2 = MultiInterval{{NegInf, 1 / rhs.left}};

    else if (rhs.left == 0)
        f2 = MultiInterval{{1 / rhs.right, Inf}};

    else
        f2 = MultiInterval{{NegInf, 1 / rhs.left}, {1 / rhs.right, Inf}};

    return f1 * f2;
}

Minimum interface for the above to work:

struct ExtendedInt
{
    ExtendedInt();
    ExtendedInt(int);
};
ExtendedInt NegInf;
ExtendedInt Inf;
ExtendedInt NaN;

auto operator+(ExtendedInt, ExtendedInt) -> ExtendedInt;
auto operator-(ExtendedInt, ExtendedInt) -> ExtendedInt;
auto operator*(ExtendedInt, ExtendedInt) -> ExtendedInt;
auto operator/(ExtendedInt, ExtendedInt) -> ExtendedInt;

auto operator==(ExtendedInt, ExtendedInt) -> bool;
auto operator!=(ExtendedInt, ExtendedInt) -> bool;

struct Interval
{
    ExtendedInt left, right;
};

auto contains(Interval, ExtendedInt) -> bool;

class MultiInterval
{
public:
    MultiInterval(std::initializer_list<Interval>);
};

auto operator*(MultiInterval lhs, MultiInterval rhs) -> MultiInterval;

---

Finally please note this from wikipedia:

Because several such divisions may occur in an interval arithmetic calculation, it is sometimes useful to do the calculation with so-called multi-intervals of the form

So you would ultimately have to work only with MultiInterval where an interval is a MultiInterval with just one interval.