# Boost :

Subject: [boost] [multiprecision review] Possible use of uninitialised value
From: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2012-06-13 17:21:48

Dear All,

I decided to try to evaluate the proposed Boost.Multiprecision on the
code that I wrote recently when looking at the proposed Delaunay
Triangulation / Voronoi Diagram code. Specifically, this function:

inline bool delaunay_test(int32_t ax, int32_t ay, int32_t bx, int32_t by,
int32_t cx, int32_t cy, int32_t dx, int32_t dy)
{
// Test whether the quadrilateral ABCD's diagonal AC should be
flipped to BD.
// This is the Cline & Renka method.
// Flip if the sum of the angles ABC and CDA is greater than 180 degrees.
// Equivalently, flip if sin(ABC + CDA) < 0.
// Trig identity: cos(ABC) * sin(CDA) + sin(ABC) * cos(CDA) < 0
// We can use scalar and vector products to find sin and cos, and simplify
// to the following code.
// Numerical robustness is important. This code addresses it by performing
// exact calculations with large integer types.

i64 ax64 = ax, ay64 = ay, bx64 = bx, by64 = by,
cx64 = cx, cy64 = cy, dx64 = dx, dy64 = dy;

i64 cos_abc = (ax64-bx64)*(cx64-bx64) + (ay64-by64)*(cy64-by64);
i64 cos_cda = (cx64-dx64)*(ax64-dx64) + (cy64-dy64)*(ay64-dy64);
if (cos_abc >= 0 && cos_cda >= 0) return false;
if (cos_abc < 0 && cos_cda < 0) return true;

i64 sin_abc = (ax64-bx64)*(cy64-by64) - (cx64-bx64)*(ay64-by64);
i64 sin_cda = (cx64-dx64)*(ay64-dy64) - (ax64-dx64)*(cy64-dy64);

i128 sin_sum = static_cast<i128>(sin_abc)*cos_cda
+ static_cast<i128>(cos_abc)*sin_cda;

return sin_sum < 0;
}

Here i64 and i128 are typedefs for appropriate 64- and 128-bit signed
integer types.

when I try to use boost::multiprecision::cpp_int, I get answers that
are only mostly correct. Specifically, sometimes the very first call
gives the wrong answer. It is dependent on the number of iterations of
my benchmark loop and other factors.

valgrind reports the following:

==15713== Conditional jump or move depends on uninitialised value(s)
==15713== at 0x8053B0C:
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >,
true>::mp_number<boost::multiprecision::detail::plus,
boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>, void, void>,
boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>, void, void>, void,
void>(boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::plus,
boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>, void, void>,
boost::multiprecision::detail::mp_exp<boost::multiprecision::detail::multiply_immediates,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>,
boost::multiprecision::mp_number<boost::multiprecision::backends::cpp_int_backend<0u,
true, std::allocator<unsigned int> >, true>, void, void>, void, void>
const&) (in /home/phil/boost_mp_review/benchmark)

As expected, the error is impenetrable.

Can anyone guess what is going on?

(I seem to get the right answers and no valgrind errors with the
fixed-size and no-expression-templates types.)

Regards, Phil.