gmpxx中float转整数出现精度丢失问题及技术咨询

背景 #

这是我在Qt中开发Signal应用库时，进行C++大数运算的学习练习。

问题 #

我尝试通过乘法实现除法时得到错误结果。

/* 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

我的实现步骤如下：

• 通过创建有理数来计算倒数：1 / 10
• 将有理数转换为浮点数以获取精度：0.1
• 将浮点数与被除数相乘得到结果：0.1 × 500 = 50
• 转换为整数以使用mpz_mod函数计算模，错误似乎出现在这一步。

问题在于预期结果50变成了49。

我的猜想 #

我对浮点数转换的特性缺乏了解。

示例如下：

/* 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

尽管我对数学了解不深，但1 / 10本不应存在精度问题，我难免怀疑这是一个bug。不过我猜测是残留的精度问题导致结果被floor()向下取整了一位。

待解答问题 #

1. 这应该被视为bug吗？
2. 通过创建有理数来计算倒数是个糟糕的主意吗？
3. 能否通过设置精度让现有代码正常工作？
4. 考虑到这用于密码学场景，会生成256位大小的数字，我实际需要多少精度？仅做上下取整的话精度需求是否很低？
5. 我应该仅使用整数类型进行计算，还是适合使用浮点数或有理数类型？

解答 #

1. 这应该被视为bug吗？ #

不是bug。浮点数（包括GMP的mpf_class）本质是二进制浮点表示，无法精确存储像0.1这样的十进制分数——因为0.1转换为二进制是无限循环小数，只能近似表示。当你把有理数1/10转成mpf_class时，已经引入了微小的误差，后续计算后，这个误差导致实际值略小于50（比如49.99999999999999...），转换为整数时会被截断为49，这是浮点数的固有特性，而非GMP的bug。

2. 通过创建有理数来计算倒数是个糟糕的主意吗？ #

对于你的场景来说是。你本来可以直接用整数运算完成500 / 10，根本不需要引入有理数或浮点数。但如果是处理无法整除的场景，有理数本身是精确的——问题出在你把有理数转成了浮点数，丢失了精确性。如果全程用mpq_class处理，结果会是精确的，但你没必要绕这一圈。

3. 能否通过设置精度让现有代码正常工作？ #

理论上可以，但非常不推荐。你需要把mpf_class的精度设置到足够高，确保0.1 * 500的结果误差小于0.5，这样截断为整数时能得到正确的50。但这种方法不可靠：当处理更大的数字（比如256位）时，需要的精度会指数级增长，而且始终存在误差溢出的风险，无法保证所有场景都正确。

4. 密码学场景下的精度需求 #

密码学要求绝对精确，不存在“足够近似”的说法。256位整数需要至少256位的精确表示，浮点数的精度（即尾数位数）必须超过这个值才能保证转换时不丢失信息——但即便如此，浮点数的运算误差依然可能导致结果偏差。仅做上下取整也不行，因为任何微小的误差都可能让结果偏离正确值1，而密码学运算中哪怕1位的错误都会导致整个结果失效。

5. 应该选择哪种类型？ #

密码学场景下必须全程使用整数类型（mpz_class）。浮点数和有理数都不适合：

• 浮点数存在固有精度误差，无法保证精确性；
• 有理数虽然精确，但密码学运算大多基于整数模运算，用有理数会引入不必要的复杂度，而且转换过程中容易出错。

你的需求其实是计算(dividend / divisor) mod modulo，直接用GMP的整数除法和模运算即可：

mpz_class dividend(500);
mpz_class divisor(10);
mpz_class modulo(17);

mpz_class quotient;
mpz_div(quotient.get_mpz_t(), dividend.get_mpz_t(), divisor.get_mpz_t());

mpz_class result;
mpz_mod(result.get_mpz_t(), quotient.get_mpz_t(), modulo.get_mpz_t());

// 结果会是正确的16

如果是处理模逆元（即求x使得divisor * x ≡ 1 mod modulo），那应该用GMP的mpz_invert函数，这才是密码学场景下的正确做法。

内容的提问来源于stack exchange，提问作者Anon