整数平方根：整数开方及大整数开方解决方法 |
您所在的位置：网站首页 › 二分法求平方根c语言 › 整数平方根：整数开方及大整数开方解决方法 |
整数平方根：整数开方及大整数开方解决方法
|
求整数N的开方，精度在0.001 二分法 若N大于1,则从[1, N]开始，low = 1, high = N, mid = low + (high - low) >> 1开始进行数值逼近 若N小于1,则从[N, 1]开始，low = 0, high = N, mid = low + (high - low) >> 1开始进行数值逼近 #include #include #include #define ACCURACY 0.001 double newSqrt(double n) { double low, high, mid, tmp; // 获取上下界 if (n > 1) { low = 1; high = n; } else { low = n; high = 1; } // 二分法求开方 while (low n) { high = mid; } else { low = mid; } } return -1.000; } int main(void) { double n, res; while (scanf("%lf", &n) != EOF) { res = newSqrt(n); printf("%lf\n", res); } return 0; }牛顿迭代法思路求解： #include using namespace std; int main() { int N; coutN double x1 = 1;//初值 double x2 = x1/2.0+N/2.0/x1; while( fabs(x2-x1)>0.001) { x1 = x2; x2 = x1/2.0+N/2.0/x1; } cout return x; } while(sum_n unsigned long sum_n = 0; unsigned n = (x >> 1); unsigned top = x; unsigned bottom = 0; if (x sum_n = n * n; if (sum_n top = n; n -= ((top - bottom) >>1); if (n == top) return n-1; } else { return n; } } }
算法2 Newton 法 把这个问题转换为方程求根问题，即: 而方程求根的问题可以用Newton 法来解决。现在的问题有一点不同，即所求的根必须是整数。通过证明，我们可以发现，Newton迭代公式是适用于整数情况的，于是有： 另外，初值的选择也是很重要的一环，这里我们选择大于等于 OK，下面给出程序： 
unsigned newton_method(unsigned
long x)
{
unsigned
long x1 = x -
1;
unsigned s =
1;
unsigned g0,g1;
/*
初值设定 通常将初始值设为1，但是只有1的开方才会是1，通过预处理找到更精确地初始值a[n]
*/
if (x1 >
65535) {s +=
8; x1 >>=
16;}
if (x1 >
255) {s +=
4; x1 >>=
8;}
if (x1 >
15) {s +=
2; x1 >>=
4;}
if (x1 >
3) {s +=
1; x1 >>=
2;}
/*
迭代
*/
g0 =
1 s)) >>
1;
while(g1 >
1;
}
return g0;
}
算法3 逐比特确认法 逐比特确认法认为一个32位整数求根，结果应该是一个16位整数。求这个16位整数，其实质是确认每位的比特是0还是1.我们把这个根分为两个相加的部分，一部分是已确认的值，另一部分是未确认的值。从高位到低位，每次迭代确认一位。初始时，已确认部分为0。则问题的初始形式为： 下面给出源代码：
unsigned bitwise_verification(unsigned
long x)
{
unsigned
long temp =
0;
unsigned v_bit =
15;
unsigned n =
0;
unsigned b =
0x8000;
if (x 接下来介绍一种手动模拟求平方根算法。非常巧妙，非常神奇。可能自己智商有点问题哈，仔细琢磨了几个小时才彻底明白。先仔细介绍如何使用这种算法模拟求平方根，然后再简要说一说它的原理吧！
（a）首先将要开方根的数从小数点分别向右及向左每两个位一组分开，如98765.432内小数点前的65是一组，87是一组，9是一组，小数点后的43是一组，之后是单独的一个2，要补一个0而得20是一组。
（b）将最左一组的数减去最接近又不大于它的平方数，并将该平方数的开方（应该是个位数）记下。
（c) 将上一步所得之差乘以100，和下一组数加起来。
（d）将记下的数乘以20，然后将它加上某个个位数，再乘以这个个位数，令这个积不大于又最接近上一步所得之差，并将该个位数记下，且将上一步所得之差减去所得之积。
（e）记下的数依次隔两位记下。
（f）重复第3步，直到找到答案。
(g) 可以在数字的最右补上多组的00，以求得理想的精确度未止。
|
，求x。
至于是怎么证明的，可以参考hacker’s delight。
的最小的2的幂次数。
算法发明者为：James Ulery 论文:Computing Integer Square Roots【本文地址】
今日新闻 |
推荐新闻 |