分治法实现的平方根计算代码返回值较正确值小1的问题求助

问题根源 #

你的代码出现这种异常，核心原因有两个：

1. 精度常量SQRT_PRECISION设置过大：如果它被定义成1.0这类较大的值，循环会在high和low的差值还没足够小时就停止，导致mid没有收敛到足够接近真实平方根的位置。
2. 结果被强制截断为整数：如果调用代码时把返回的double值直接转成int，会截断小数部分。对于36、81这类完全平方数，此时mid会略小于真实平方根（比如接近6但不到6），截断后就变成了5、8这类比正确值小1的结果；而12-16之间的数，要么刚好命中square == value（如16）直接返回正确值，要么截断后的整数部分刚好等于真实平方根的整数部分（如12的平方根约3.464，截断后是3，符合预期），所以看起来“正确”。

解决步骤 #

1. 修正精度常量：将SQRT_PRECISION设置为极小的正数，确保循环能收敛到足够精确的结果，比如：

   #define SQRT_PRECISION 1e-6
   

   这个值可以根据需求调整，1e-6表示误差不超过0.000001，足够满足大多数场景。

2. 正确处理结果输出：

   • 如果需要保留小数的精确结果，直接使用返回的double值即可；
   • 如果需要整数结果，不要直接强制转换int，而是用四舍五入函数，比如：

     return round(mid);
     

     或者在输出时使用格式化字符串实现四舍五入：

     printf("%.0f", findSquareRoot(36)); // 输出6而不是5
     

验证修正后的代码 #

调整后的完整代码示例：

#include <math.h> // 用于round函数，若不需要可以去掉
#define SQRT_PRECISION 1e-6

double findSquareRoot( int value )
{
  //initialize functions and variables
  double low = 0, high = value;
  double mid = ( low + high ) / 2;
  double square = mid * mid;

  if (value == 0 || value == 1)
     {
        return value;
     }
  
  while ( ( high - low ) > SQRT_PRECISION )
     {
        if ( square > value )
           {
              high = mid;
           }
        else
           {
              low = mid;
           }
        mid = ( low + high ) / 2;
        square = mid * mid;
     }

   // 如果需要整数结果，返回round(mid)，否则直接返回mid
   return mid;
   // return round(mid);
}

这样修改后，输入36会返回接近6的double值（如5.999999761581421），直接输出会显示为6；如果用round返回整数，会直接得到6，完全符合预期。

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