0

Backstory:

Learning exercise for large number arithmetic in C++, as I try to create a signalapp library in Qt.

Problem:

I am getting an erroneous result when I try to do division through multiplication.

/* This attempts division through multiplication */
const int dividend(500);
const int divisor (10 );
const int modulo  (17 );

/* Calculate the inverse */
mpq_class rational( 1, divisor );
mpf_class inverse( divisor == 0 ? 0 : rational );

/* Divide through multiplication */
inverse *= dividend;

/* Convert to integer */
mpz_class fromFloat( inverse );

/* Complete the equation with the modulus */
mpz_class result;
mpz_mod( result.get_mpz_t(), fromFloat.get_mpz_t(), mpz_class(modulo).get_mpz_t() );

/* Check Result */
qDebug() << "Expected Result: " << 50 % modulo;   // 16
qDebug() << "Produced Result: " << result.get_d();// 15
qDebug() << "Error:" << fromFloat.get_d() << inverse.get_d(); // 49 & 50

I may have taken an odd route to get to my result:

  1. Create the inverse by simply creating a rational. 1 / 10
  2. Get precision by converting that rational into a float. 0.1
  3. Finding the answer by then multiplying the float with the dividend: 0.1 × 500 = 50
  4. Convert to an integer, that I may use the mpz_mod function, for calculating a modulus. This is where the error seems to be.

Problem is, that the expected result 50 is becoming 49.

My guess?

I am simply ignorant to the nature of float conversions.

For example:

/* Display Float */
mpf_class f(0.1);
mp_exp_t x(-1);
qDebug() << x << QString::fromStdString( f.get_str(x) ) << x;
/* Produces */
// -1 "100000000000000005551" 0
// aka
// 0.100000000000000005551

qDebug() << x << QString::fromStdString( f.get_str(x,10,2) ) << x;
/* Produces */
// -1 "1" 0
// aka
// 0.1

Still: Despite how green I am to math, given that no imprecision should exist with 1 / 10, its hard for me to not consider that some sort of bug. Either way, my guess is that there must be some sort of imprecision lingering that is causing it to floor() down one integer.

Questions:

  1. Should this be regarded as a bug?
  2. Is it a terrible idea to try to calculate the inverse by simply creating a rational?
  3. Could I make my existing code work if I set the precision some how?
  4. Considering this is for cyptography and I will be producing 256 bit sized numbers, what level of precision will I actually need? Is it relatively little considering I will most likely just be rounding up or down?
  5. Should I try to be calculating this by only using the integer type? Or is appropriate to use its float or rational types?

Thanks.

References:

Anon
  • 2,267
  • 3
  • 34
  • 51
  • 2
    This is because `1.0/10.0` is not `0.1`, because floating point math is broken. It is slightly less than `0.1`, so after multiplication and truncation you get a surprise. This is the whole reason for using arbitrary precision libraries, like gmpxx: to avoid floating point errors. But, constructing an mpf_class from mpq_class involves an intermediate conversion to floating point, resulting in this breakage. See the linked question for more information, and gmpxx library reference. – Sam Varshavchik Jan 16 '23 at 00:05
  • 2
    `mpf_class` is floating point. With many digits, but not an infinity. Why do you use it instead of working with rationals (which can represent 1/10 exactly), and converting from rational to integer when you need it? (note that from an efficiency pov, if you can do everything with integers, it will likely be faster) – Marc Glisse Jan 16 '23 at 07:16

0 Answers0