Алгоритм 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() beeing NegInf
• std::numeric_limits<int>::max() - 1 is Inf
• std::numeric_limits<int>::max() is 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 с одним интервалом.