error in comparing CORE Expr values

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

error in comparing CORE Expr values

Peter Palfrader
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
--
                            |  .''`.       ** Debian **
      Peter Palfrader       | : :' :      The  universal
 https://www.palfrader.org/ | `. `'      Operating System
                            |   `-    https://www.debian.org/

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



cgal0_1.cpp (14K) Download Attachment
cgal0_2.cpp (14K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: error in comparing CORE Expr values

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




--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss


Reply | Threaded
Open this post in threaded view
|

Re: error in comparing CORE Expr values

Stefan Schirra
Hi,

On 19.09.2019 11:27, Stefan Schirra wrote:

> 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.

In Stefan Funke's Diplomarbeit the recommendation is to return
[NaN, infty, ...] if xxx is not positive. There is no way to get rid of
the NaN anymore, so no derived interval will be OK later on.

However, you can get rid of the inf later on and this happens in the
sample code, causing the bug. Again in a division operation, the new
approximation is computed as
double val =  fpVal / x.fpVal;
with fpVal positive finite and x.fpVal = infinity, resulting in value 0
in accordance with IEEE 754. The resulting interval is considered OK,
because the value is finite, although it does not contain the actual value.

Probably one should use something like

return filteredFp( ::sqrt(-1.0), getDoubleInfty(), 1);

or some default NaN, if there is something like that in CORE already.

Best regards

        Stefan


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss