用牛顿迭代法求整数的平方根
浏览:2439次 出处信息
这是一个挺常见的面试题,解法也五花八门。
下面的代码用牛顿迭代法解决这个问题。因为输入和输出都是整数,所以只要前后两项相差小于1,就可以终止了
int sqrt(int x) { if (x < 0) abort(); if (x == 0) return 0; if (x == 1) return 1; double t = x >> 1; t = (t + x / t) / 2; while (true) { double v = (t + x / t) / 2; if (fabs(v - t) < 1) { t = v; break; } t = v; } t=floor(t); if (t * t > x) t--; return t; }
我本来想用有理数运算来代替double,后来发现不行,迭代次数过多后,如果分子分母约分约不下去,就溢出了。
上面这段代码其实也就只能应付面试,实际有很多比这个更优的方案,比如打表。
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:关于libmemcached中的crc的实现
后一篇:在2048里能够得到的最大的数是多少? >>
文章信息
- 作者:A programmer's life 来源: A programmer's life
- 标签: 平方根 牛顿 迭代法
- 发布时间:2014-11-25 22:50:14
近3天十大热文
- [57] 招聘技巧一二
- [15] [译]Google Chrome中的高性能网
- [14] 关于Linux的文件系统cache
- [14] 在FreeNAS/BSD搭建基于Nginx+
- [13] 最近总结的一些技巧(vim,python,s
- [12] Linux常用系统信息查看命令
- [9] Linux(Ubuntu 10.04)上安装
- [9] 我对技术方向的一些反思
- [8] base64_encode 和 urlenc
- [8] Redis和Memcached的区别