需要检查整数是否为平方，如果是，则计算根。 我想用整数算术做到这一点。 显然，牛顿法可以用整数实现，但是它需要在每一步进行除法。 但是可以吗？ 求模的平方根为2的幂，然后检查它是否为普通的平方根。
您可以将自己限制为奇数：对于偶数，如果最低有效零位数的数字为奇数，则没有根，但如果为偶数，则可以将数字向右移动，计算奇数的根，然后向左移回原始零位数字的一半。
对于奇数N和2
k ，k> 3，如果N≡1 mod 8，则存在4个不同的根，其模2
k为模，否则没有根。 我们需要x的四个根中的最小根。 其他三个根是2
k -x，2
k-1 + x和2
k -2
k-1 -x
我想要类似于计算
逆模2 k的东西 -将每次迭代的有效位数加倍。
假设我们已经有一个根x
0为N模2
k ：
N-x 0 2 = 2 k a我们希望找到
x 1 = x 0 + 2 k-1 y ，使得在N-x
1 2中有更多的低零位。
N-（x 0 + 2 k-1 y） 2 = 2 k a-2 k x 0 * y-2 2k-2 y 2除以2
k ：
a-x 0 * y-2 k-2 y 2并等于0模2
k-2 ：
y = a * x 0 -1 mod 2 k-2收到
x 1 = x 0 + 2 k-1 a *（x 0 -1 mod 2 k-2 ）最后
x 1 = x 0 +（N-x 0 2 ）/ 2 *（x 0 -1 mod 2 k-2 ）在下一次迭代的k位中，您将获得2（k-1）位。 同时，我们在每次迭代中都认为与根相反。
测试代码：
uint8_t sqr16(uint16_t n) { if (n % 8 != 1) return 0; uint16_t sqr = (n + 1) / 2; //4 bit uint16_t inv = 2 - sqr; sqr += inv * (n-sqr*sqr)/2; //6 bit inv *= 2 - sqr * inv; sqr += inv * (n-sqr*sqr)/2; //10 bit //inv *= 2 - sqr * inv; if (sqr & 256) sqr = 0u - sqr; sqr = (uint8_t)sqr; // lowest root if (n == sqr*sqr) return sqr; return 0; }
添加几次迭代，我们从uint_64获得根