北邮实验：牛顿迭代法求解浮点数与整数平方根及倒数精度分析

本次实验主要涉及北邮数值与符号计算课程中的四个关键问题：使用牛顿迭代法求解浮点数平方根、整数平方根、倒数以及模的逆。以下是每个部分的详细讨论： 1. **浮点数平方根（double my_sqrt(double c)）**： 牛顿迭代法是一种常见的数值方法，用于寻找方程f(x)=0的根。对于浮点数平方根，初始迭代选取p=1，q=c作为初值。迭代公式为x_{n+1} = x_n + (c/x_n - x_n^2)/2。由于浮点数c的尾数m已知且c是规格化数，三次迭代足以逼近双精度浮点数的精度。这是因为牛顿法收敛速度通常很快，尤其是对于平滑函数，三次迭代通常足以达到机器精度。 2. **整数平方根（unsigned my_sqrt(unsigned c)）**： 对于整数平方根，同样采用牛顿迭代，但因为没有小数部分，迭代过程更为简单。选取p=1，整数部分m通过循环找到满足m*m<=c的最小整数。之后，根据整数除法进行迭代，三次迭代同样可以保证达到整数结果的准确性。 3. **浮点数倒数（double my_inverse(double c)）**： 倒数的牛顿迭代法中，初始选取p=1，q=c。因为浮点数c已经经过规格化处理，c不为零，所以可以通过循环找到一个近似的倒数m。当c的绝对值接近1时，倒数的精度会迅速提高。通常情况下，为了确保双精度精度，可能需要更多迭代，但具体次数取决于c的初始值和尾数分布。 4. **模的逆（unsigned my_inverse(unsigned c, unsigned modulus））**： 当c为奇数时，求模的逆实际上是寻找一个整数d，使得dc ≡ 1 (mod modulus)。牛顿迭代在此处仍然适用，但需要额外处理模运算。选取适当的初始值p，如模数的约数或模数的平方根，然后利用迭代公式进行求解。由于模运算可能导致数值的周期性，可能需要更多迭代次数才能确保找到正确的模逆，但三次迭代也可能足够，视具体模数而定。 在编写实验报告时，应包括算法的详细解释，每次迭代后的结果分析，以及为何三次迭代就能达到所需精度的理论依据。同时，提供实例来展示函数的正确性和性能，并使用精确计时工具对比与库函数的运行效率。这将帮助验证牛顿迭代法在不同情况下的有效性，并评估其在实际应用中的可行性。