Алгоритм C++ для разделения двух целочисленных интервалов со знаком

Question

Рассмотрим интервалы A = [x1, y1] и B = [x2, y2], два интервала, представляющие целые числа со знаком.

Интервальная арифметическая страница в Википедии дает формулу для решения случая, когда B не содержит 0, реализация C++ может быть следующей:

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);
}

Выход:

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

Как и ожидалось, результат неверен, учитывая, что B содержит 0. Например, поскольку 1 является частью B, 150000 должно быть в пределах A/B, но это не так.

Что такое жизнеспособный алгоритм, когда 0 исключен из B? Должно ли решение использовать несколько интервалов около -1 и 1 (т.е. исключать 0) и как-то их объединить?

Изменить: решение может быть выражено через объединение (вектор) интервалов типа long long.

Answer 1

Вы не пишете C++, вы пишете C, завернутый в какой-то маленький C++. Вот что я хотел бы сделать:

Сначала я бы начал с класса для интервала, то есть:

struct Interval
{
    int left;
    int right;
};

Тогда я бы начал с сложения, вычитания и умножения. Например

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

Которые довольно просты.

Когда мы добираемся до деления, как видно из вашей вики-ссылки, все становится сложнее.

1. Результатом является уже не интервал, а мультиинтервал, то есть соединение интервалов.
2. Эти интервалы имеют ∞ а также -∞ головы.

Первая проблема решается с новым классом:

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

Для второй проблемы... ну мы больше не можем использовать int как данные. Поэтому вам нужен новый класс для целых чисел, который может содержать значения ∞, -∞, NaN, NaN требуется как побочный продукт, например -∞ + ∞ = NaN,

class ExtendedInt
{
    // black magic
};

для которого вы должны будете определить 3 константы, которые являются новыми 3 значениями. Затем вам нужно будет определить все основные арифметические операции над ними.

Наконец, мы можем переделать все в нечто вроде этого:

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;

Как видите, все довольно быстро усложняется.

---

Что касается реализации ExtendedInt, одно решение состоит в том, чтобы иметь два элемента данных, один int и одно перечисление

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

class ExtendedInt
{
     int value_;
     ExtendedIntValues ext_value_;
};

если ext_value_ == Normal тогда значение экземпляра value_иначе это ext_value_,

Другое решение состоит в том, чтобы понять, что функционально это союз. Так что вы могли бы использовать std::variant<int, ExtendedIntValues> вместо.

Еще одно решение заключается в использовании std::optional:

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

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

Все эти решения жертвуют пространством с std::variant жертвуя юзабилити.

Другое решение, которое просто жертвует 3 нормальными int значения должны иметь только один int и имеют некоторые значения, представляющие особые случаи:

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

Внутренне:

• std::numeric_limits<int>::min() неоспоримым NegInf
• std::numeric_limits<int>::max() - 1 является Inf
• std::numeric_limits<int>::max() является NaN

Или что-то в этом роде, но это должно быть сделано совершенно прозрачным. Особое внимание должно быть уделено арифметическим операциям.

Другое решение состоит в том, чтобы понять, что уже есть тип (или два), которые изначально поддерживают эти значения и идут с float или же double, Это принесет в жертву точность.

---

Когда у вас есть ExtendedInt разобрался потом просто следуй вики алгоритму:

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;
}

Минимальный интерфейс для работы выше:

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;

---

Наконец, обратите внимание на это из Википедии:

Поскольку в арифметическом вычислении интервалов может происходить несколько таких делений, иногда полезно выполнять вычисления с так называемыми множественными интервалами вида

Таким образом, вам в конечном итоге придется работать только с MultiInterval где интервал является MultiInterval только с одним интервалом.