Calculating the floor of y**(1/m)

技术摘要：计算 $y^{1/m}$ 的地板值

问题陈述
本文探讨了计算自然数 $y$ 的 $m$ 次方根的地板值（即整数部分）$\lfloor y^{1/m} \rfloor$ 的计算问题，其中 $y > 2$ 且 $m > 1$。该计算是数论中的一个基本步骤，特别是在识别一个自然数 $y$ 是否为完全幂数（即是否存在自然数 $x$ 和 $m > 1$ 使得 $y = x^m$）时。虽然传统方法利用二分查找在范围 $[2, \lg y]$ 内寻找 $x$，但作者指出，在算术的位模型（bit model）中，此类方法在计算效率上并不理想，尽管它们在实际应用中很常用。

方法论
本文提出了两种基于牛顿-拉夫逊（Newton-Raphson）方法的不同算法，这些方法是从实数求根法改编而来的，适用于整数算术。两种算法旨在通过迭代优化初始猜测值 $x_0$，直到收敛以计算 $x = \lfloor y^{1/m} \rfloor$。

• 算法 1（直接改编法）：
  该方法修改了针对 $f(x) = y - x^m = 0$ 的标准牛顿-拉夫逊迭代步。实数值更新步 $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ 通过对分式应用地板函数转换为整数算术：
  $$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$$
  初始值 $x_0$ 通过 $y$ 的对数导出，以确保 $x_0 \ge y^{1/m}$。收敛性分析较为复杂，区分了三种情况：

  1. 一个趋于稳定的递减序列（$x_{n+1} = x_n$）。
  2. 一个“翻转”并增加的递减序列（$x_{n+1} > x_n$）。
  3. 持续递减。
     算法在发生翻转或重复时终止，此时通过检查是否满足 $x_n^m \le y < (x_n+1)^m$ 来确定解为 $x_n$ 或 $x_n + 1$。

• 算法 2（精炼整数递推法）：
  该方法利用了牛顿-拉夫逊公式的一种不同的代数重排形式：
  $$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$$
  此公式利用性质 $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ 来保持整数完整性。初始值 $x_0$ 取为 $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$，确保 $x_0 \ge y^{1/m}$。
  算法 2 的收敛证明更为简洁。它确立了只要 $x_i > y^{1/m}$，序列就是非增的。当 $x_{i+1} \ge x_i$ 时算法停止，此时证明表明 $x_i$ 必然等于 $\lfloor y^{1/m} \rfloor$。

主要贡献

1. 整数牛顿-拉夫逊公式化： 本文提出了两种用于计算 $\lfloor y^{1/m} \rfloor$ 的特定整数化改编的牛顿-拉夫逊方法。
2. 收敛性证明： 为两种算法提供了严谨的数学证明，确立了它们收敛于正确的整数地板值。证明分析了序列相对于真实根 $Y = y^{1/m}$ 的行为，处理了序列过冲或稳定等情况。
3. 初始值选择： 两种算法都包含了特定的、计算高效的方法（使用位移和对数）来选择初始猜测值 $x_0$，从而保证序列从大于或等于真实根的值开始。

结果
本文通过使用各种 $y$ 和 $m$ 的值（例如 $y=108, m=8$；$y=96889010407, m=13$）为两种算法提供了说明性示例。

• 两种算法均成功收敛到正确的整数根。
• 在提供的示例中，算法 1 通常比算法 2 需要更少的迭代次数。例如，在 $y=52523350144$ 且 $m=7$ 的情况下，算法 1 在 4 步内收敛（32, 34, 34），而算法 2 需要 7 步（64, 54, 46, 40, 36, 34, 34）。
• 作者将后期示例中的性能差异归因于算法 1 中更具针对性的初始值 $x_0$ 的选择。

意义与声明
本文明确指出，将牛顿-拉夫逊用于整数问题的技术并非首创，并引用了现有文献（特别是参考文献 [2]）。因此，作者并不声称这些底层数学概念具有原创性。相反，本文的意图是为这些特定方法及其详细证明提供一个“存档参考”。这项工作旨在将牛顿-拉夫逊法应用于完全幂数识别的整数过程进行形式化，为位复杂度模型下的二分查找提供一种潜在的高效替代方案，尽管本文对于其优于既定方法的说法保持谦逊。