CGAL users discussion list

[Stefan Schirra <>]

Hi,

On 18.09.2019 15:33, Peter Palfrader wrote:
> Hi!
>
> I have encountered what seems like a strange issue:
>
> Consider this code snippet:
> ]   std::cout << "v1: " << v1 << std::endl;
> ]   std::cout << "v2: " << v2 << std::endl;
> ]   std::cout << "v1 < v2: " << (v1 < v2 ? "yes" : "no") << std::endl;
> which prints this:
> ]   v1: 0.49770
> ]   v2: 0.01047
> ]   v1 < v2: yes
>
> I'm not sure what is going on, but I don't think that 0.49770 is
> less than 0.01047. :)
>
> This is with libcgal13 (as shipped in Debian 10[1] and Ubuntu 18.04).  The
> attached piece of code constructs v1 and v2.  Compiling with clang++ (or g++)
> produces this effect:
>
> | weasel@waschbaer:~$ clang++ cgal0_1.cpp -o cgal -lgmpxx -lgmp 
> -lboost_thread -lCGAL_Core -lCGAL
> | weasel@waschbaer:~$ ./cgal
> | v1: 0.49770
> | v2: 0.01047
> | v1 < v2: yes
>
>
> If you multiply all the constants (not unity) by 100, nothing changes:
> | v1: 49.7703
> | v2: 1.04670
> | v1 < v2: yes
>
> Once you multiply them by 10000: (cf. cgal0_2.cpp).
> | v1: 4977.03
> | v2: 104.670
> | v1 < v2: no
>
> Something's fishy here.
>
> Cheers,
> Peter
>
> 1.  Versions of packages libcgal13:amd64 depends on:
>    libboost-thread1.67.0  1.67.0-13
>    libc6                  2.28-10
>    libgcc1                1:8.3.0-6
>    libgmp10               2:6.1.2+dfsg-4
>    libstdc++6             8.3.0-6
>    zlib1g                 1:1.2.11.dfsg-1


WARNING: This is a partial answer, not a solution.

Apparently, the problem is with the floating-point filter (FPF). CORE 
"checks" whether the interval of the FPF allows for deciding the sign 
and if so reports the sign of the approximation. The FPF maintains three 
values, an approximation fpVal, and maxAbs and ind, such that maxAbs * 
ind * 2^{-53} is an error bound for the approximation. Unfortunately the 
interval for v1-v2 is incorrect (because the interval for v1 is 
incorrect). The actual bigFloat approximation for v1-v2 is correct and 
has the correct sign, but its sign is not used in the <  operation.

An excerpt from the code:

inline int ExprRep::getSign() {
  if (ffVal.isOK())
    return ffVal.sign();
  else
    return getExactSign();
}

If you add

std::cout << "ex.sign of v1-v2: " << (v1-v2).Rep()->getExactSign() << 
std::endl;

you'll get the correct sign!

The intervals for v1, v2, and v1-v2 are

v1:      Filter=[fpVal=0,maxAbs=2.22507e-308,ind=13]
v2:      Filter=[fpVal=0.010467,maxAbs=6.57198e+10,ind=23]
v1-v2:   Filter=[fpVal=-0.010467,maxAbs=6.57198e+10,ind=24]

and you see, the interval for v1 is wrong since it does not contain the 
actual value.


Tracing this back a bit we see after


NT e_f4c1f8 = e_ed6940 / e_ed68a0; // -4.00000  // tree-height:  13

e_ed6940: -6.56405e-17
e_ed6940: Filter=[fpVal=-1.12323e-16,maxAbs=1.02754e+08,ind=18]
e_ed68a0: 1.64101e-17
e_ed68a0: Filter=[fpVal=2.80266e-17,maxAbs=139.598,ind=6]
e_f4c1f8: -4.00000
e_f4c1f8: Filter=[fpVal=inf,maxAbs=0,ind=0]

So we have approximation infinity, but error 0 (IMHO this is strange!) 
for e_....

If we set the error to infińity in operator/ for FPF in CORE/Filter.h

 filteredFp operator/ (const filteredFp& x) const {
    if (x.fpVal == 0.0)
      core_error("possible zero divisor!", __FILE__, __LINE__, false);
    double xxx = core_abs(x.fpVal) / x.maxAbs - (x.ind+1)*CORE_EPS + 
DBL_MIN;
    if (xxx > 0) {
      double val =  fpVal / x.fpVal;
      double maxVal = ( core_abs(val) + maxAbs / x.maxAbs) / xxx + DBL_MIN;
      return filteredFp(val, maxVal, 1 + core_max(ind, x.ind + 1));
    } else
      // return filteredFp(getDoubleInfty(), 0.0, 0);
      return filteredFp(getDoubleInfty(), getDoubleInfty(), 1);  // NEW
  }

it works.

May be this information helps to find the real bug and to design a bug fix.


Best regards


    Stefan