interval::operator/ returns the whole line for [-1,0] / [0,1] (strict is_neg(xu) in div_positive / div_negative)

Open Beginner friendly
#78 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Assessment

Difficulty
2/5
Estimated time
1-3 hours
Newbie friendliness
85/100
Issue type
Bug
Clarity
Clearly specified
Activity status
Active
Tech stack
cpp
Domain
data

Research direction

The bug is in include/boost/numeric/interval/detail/division.hpp, in div_positive (around line 78) and div_negative (around line 113), where the is_neg(xu) test misroutes a numerator whose upper bound is exactly zero. Start by compiling the reproducer in the issue and checking that [-1,0] / [0,1] returns the whole line. Done means that case returns (-inf, 0], the sign-symmetric case returns [0, +inf), and a regression case is added to test/mul.cpp.

Written by the indexing model from the issue text.

Description

Version: Boost 1.83.0 (headers only, g++ 13.3.0, -frounding-math). The relevant code in include/boost/numeric/interval/detail/division.hpp is unchanged on develop (a701c9dd22) and master.

What happens. The documentation of / says: "If the denominator contains zero (but not only zero), the result will be the smallest interval containing the set of division results; so one of its bound will be infinite, but it may not be the whole interval." For a numerator whose upper bound is exactly zero and a denominator with one zero endpoint, operator/ (and division_part1) return [-inf, +inf]:

[-1,0] / [0,1]  = [-inf, inf]   expected (-inf, 0]
[-1,0] / [-1,0] = [-inf, inf]   expected [0, +inf)
[0,1]  / [0,1]  = [0, inf]      (correct)
[0,1]  / [-1,0] = [-inf, 0]     (correct)

The result still encloses all quotients, so this is a loss of tightness relative to the documentation rather than an unsound result, and it breaks the sign symmetry between the third and first lines.

Reproducer (Boost headers only; g++ -std=c++17 -frounding-math repro.cpp && ./a.out):

#include <boost/numeric/interval.hpp>
#include <cstdio>
using I = boost::numeric::interval<double>;
static void show(const char* name, I x, I y) {
  I r = x / y;
  std::printf("%-16s = [%g, %g]\n", name, r.lower(), r.upper());
}
int main() {
  show("[-1,0] / [0,1]",  I(-1, 0), I(0, 1));   // expected (-inf, 0]
  show("[-1,0] / [-1,0]", I(-1, 0), I(-1, 0));  // expected [0, +inf)
  show("[0,1] / [0,1]",   I(0, 1),  I(0, 1));   // [0, +inf), correct
  show("[0,1] / [-1,0]",  I(0, 1),  I(-1, 0));  // (-inf, 0], correct
}

Cause. div_positive(const interval&, const T& yu) (line 78) and div_negative(const interval&, const T& yl) (line 113) branch on is_neg(xu), i.e. xu < 0. When xu == 0 and xl < 0 this falls through to the is_neg(xl) branch, which is meant for a numerator containing zero in its interior, and returns the whole line. (The other two is_neg(xu) tests in the file, in div_non_zero and div_zero_part1, give correct results for xu == 0.)

Suggested fix. Replace is_neg(xu) with !is_pos(xu) in those two functions; x == [0,0] is already handled earlier by is_zero. I tested the patched header on 35,654 generated cases (boundary grid plus random, including signed zeros, subnormals, max and infinities) against an exact rational oracle: the 311 mismatching cases become correct, the other 35,343 are unchanged, and all 341 div vectors of the IEEE 1788 test suite (ITF1788) pass. To my reading the division tests in test/mul.cpp do not cover a numerator with an upper endpoint of 0. I'm happy to open a PR with the change and a regression test if that helps.

Dominant language
C++
Stars
30
Forks
49
Avg merge
2d 15h
Merged PRs (30d)
7

Getting set up

This project ships no dev container, Dockerfile or contributing guide, so setting up is up to you: start from its README, and see our first-contribution guide for the general steps.

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/interval

All issues in boostorg/interval

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.