nasm - 快速整数 sqrt 上限近似

Question

这是一个关于我的家庭作业的问题，特别是关于 NASM 的。

我正在编写一种算法来查找数字的最小整数因子。 (大于 1)

用伪代码可以概括为:

if(n%2==0)
    return 2;
for(i=3; i <= n/2; i+=2)
    if(n%i==0)
        return i;
return n;

该程序仅比大数的要求稍慢。 ( n > 1 000 000 000)

(对我而言)最明显的改进是替换 n/2与 sqrt(n) .但是，我不应该知道如何使用 float ，并且通过牛顿法找到整数 sqrt 似乎有点矫枉过正。 (因为我实际上不需要知道确切的值，虽然我没有测试过它，但我想递归/迭代地找到 isqrt 会很慢)

所以我想知道，是否有一些函数的快速算法，例如 sqrt(n) < f(n) < n/2 .我所说的“快”是指最好是常数时间，而 f(n) < n/2我的意思是大 n 明显更少.

我正在考虑的一些选项是:

• 检查 i <= min(sqrt(2^32), n/2) , 其中sqrt(2^32) = 2^16是常数。

• 替换i <= n/2与 i <= (2^p) , 其中p = ⌈log_2(n)/2⌉或者其他的东西。 ( p 是 n 最高有效位的一半)

Answer 1

有一个寻找平方根的迭代过程:

def approximate_sqrt(number, depth, start_val):
    for i in range(depth):
        start_val=(start_val+number/start_val)/2
    return start_val

初始猜测(start_val)越好，它收敛到合理解的速度就越快。

If start_val>sqrt(number) 

then every iterative value>sqrt(number) 

因此它提供了一个上限(类似于 start_val < sqrt(number) )。如果您的初始猜测非常接近，您可以将迭代深度减少到 1 或 2。因此，为了迭代地猜测素数候选的上限，例如你可以调用

sqrt_appr=approximate_sqrt(i, 1, sqrt_appr+1) 

对于下一个素数候选者，先前估计为 sqrt_appr 的平方根并获得误差约为 10E-6 的上限.(虽然每次我检查近似值的接近程度时，我都会设置 sqrt_appr=sqrt(number)+1 来重置过程。)