gpt4 book ai didi

nasm - 快速整数 sqrt 上限近似

转载 作者:行者123 更新时间:2023-12-01 22:18:07 25 4
gpt4 key购买 nike

这是一个关于我的家庭作业的问题,特别是关于 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/2sqrt(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/2i <= (2^p) , 其中p = ⌈log_2(n)/2⌉或者其他的东西。 ( pn 最高有效位的一半)

最佳答案

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

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 来重置过程。)

关于nasm - 快速整数 sqrt 上限近似,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42732225/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com