文档章节

69. Sqrt(x)

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 279
阅读 2
收藏 0
点赞 0
评论 0

Implement int sqrt(int x).

Compute and return the square root of x.

实现一个求平方根的算法,直接调用sqrt好像也行,不过不能用float,要用int记录(2147395599开平方是46339.99989,如果用float直接变成46340)。

int mySqrt(int x) {
    int a=sqrt(x);
    return a;
}


一般有两种算法,二分法和牛顿迭代法(泰勒公式)。还有一种是卡马克的开平方根取倒数改的算法,速度非常快,可惜是估计值,精度很低,所以不行。

二分法:

int mySqrt(int x)
{
	long long low = 0;
	long long high = x;

	while (low < high)
	{
		long long mid = (high - low) / 2 + low;

		if (mid * mid == x)
			return mid;
		else if (mid * mid > x)
			high = mid - 1;
		else
			low = mid + 1;//因为是取整数,所以直接加1就可以
	}

	return low * low > x ? low - 1 : low;
}

牛顿迭代法:

long r = x;
    while (r*r > x)
        r = (r + x/r) / 2;
    return r;

关于卡马克求平方根的论述:

http://blog.csdn.net/hunterlew/article/details/45341253

文中可以看到,虽然迭代公式和牛顿迭代略有不同(卡马克求的是开根号取导数,所以目标函数不同),但本质一样。


本文转载自:http://blog.csdn.net/limk96/article/details/72901599

共有 人打赏支持
Do0M
粉丝 0
博文 8
码字总数 24
作品 0
【机器学习实战】极大似然法

http://baike.baidu.com/link?url=3Ej1VIItwWd35sXeoRWRhcJkJLCFvzPzNIoTkAfai8ZIS4Ppcch4maQ25FjNCU1Eplsp4k3oPKLyv6VIsPhsq 一、 最大似然法是一种具有理论性的点估计法,基本思想是,当从......

HarryWu
2016/03/21
52
0
matlab 最小值问题 编程???急急急!!!!!!!!!

45<=y<=70, x<=140 sqrt(x-50).^2+(y-0).^2)+sqrt((x-120).^2+(y-100).^2)-170.8917786<=0 sqrt((x-160).^2+(y-0).^2)+sqrt((x-120).^2+(y-100).^2)-150.7846146'<=0 求z=sqrt(x-50).^2+(y-......

774886372
2012/05/01
485
2
for循环+list+append求解释返回结果 ps:每次i的值都保留了吗

>>> i=[] >>> d={'num':0,'sqrt':0} >>> for x in [1,2,3]: d['num']=x d['sqrt']=x*x i.append(d) print(i) [{'num': 1, 'sqrt': 1}] [{'num': 2, 'sqrt': 4}, {'num': 2, 'sqrt': 4}] [{'n......

awaken_
2017/01/17
320
4
Spark MLlib 之 大规模数据集的相似度计算原理探索

无论是在ICF还是UCF或者基于内容的推荐,最基本的环节都是计算相似度。如果样本特征维度很高或者的维度很大,都会导致无法直接计算。设想一下100w*100w的二维矩阵,计算相似度怎么算? 更多内...

xingoo
07/11
0
0
【概率论与数理统计】小结9-3 - 区间估计

注:区间估计是除点估计之外的另一类参数估计。相对于点估计只给出一个具体的数值,区间估计能够给出一个估计的范围。 0. 点估计 vs 区间估计 根据具体样本观察值,点估计提供了一个明确的数...

昕-2008
07/16
0
0
Oracle常用函数系列之四:数值函数(2)

本文将演示以下6个 Oracle中的常用数值函数。 函数 功能 LOG(x,y) 返回x为底y的对数 MOD(x,y) 返回x除以y的余数 POWER(x,y) 返回x的y次幂 ROUND(x[,y]) 返回x在第y位四舍五入 SQRT(x) 返回x...

博为峰教研组
2016/12/06
2
0
欧拉计划的Python解法(11-13)

Problem 11. Largest product in a grid In the 20x20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 ......

prpr
2014/03/14
0
0
浪漫情人节:Google用函数秀出情人节惊喜

浪漫的数字怪才,你的机会来了。 用户Huckberry给我们提出这个点子:在Google搜索里输入由多个函数构成的代数方程式可绘制出心形图案。 它们包括了高中时学到的数学函数:平方根、绝对值和余...

虫虫
2012/02/11
2.5K
6
求解二元二次方程式解

已知 x1,y1,r1 已知 x2,y2,r2 已知 x3,y3,r3 已知条件为: l1 = sqrt((x-x1)^2+(y-y1)^2) l2 = sqrt((x-x2)^2+(y-y2)^2) l3 = sqrt((x-x3)^2+(y-y3)^2) l1/l2 = r2/r1 l1/l3 = r3/r1 l2/l3 =......

刘晓敏
2016/04/12
54
0
如何使“根号2”乘以“根号3” == “根号6”判断成立?

Php代码: $G2 = sqrt(2); $G3 = sqrt(3); $G6 = sqrt(6); echo "G2: {$G2} n"; echo "G3: {$G3} n"; echo "G6: {$G6} n"; echo "G2 x G3 = ".($G2$G3)." n"; echo "G2 x G3 == G6: ".($G2$......

方棱
2013/07/30
1K
9

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Android 复制和粘贴功能

做了一回搬运工,原文地址:https://blog.csdn.net/kennethyo/article/details/76602765 Android 复制和粘贴功能,需要调用系统服务ClipboardManager来实现。 ClipboardManager mClipboardM...

她叫我小渝
27分钟前
0
0
拦截SQLSERVER的SSL加密通道替换传输过程中的用户名密码实现运维审计(一)

工作准备 •一台SQLSERVER 2005/SQLSERVER 2008服务 •SQLSERVER jdbc驱动程序 •Java开发环境eclipse + jdk1.8 •java反编译工具JD-Core 反编译JDBC分析SQLSERVER客户端与服务器通信原理 SQ...

紅顏為君笑
43分钟前
4
0
jQuery零基础入门——(六)修改DOM结构

《jQuery零基础入门》系列博文是在廖雪峰老师的博文基础上,可能补充了个人的理解和日常遇到的点,用我的理解表述出来,主干出处来自廖雪峰老师的技术分享。 在《零基础入门JavaScript》的时...

JandenMa
今天
0
0
linux mint 1.9 qq 安装

转: https://www.jianshu.com/p/cdc3d03c144d 1. 下载 qq 轻聊版,可在百度搜索后下载 QQ7.9Light.exe 2. 去wine的官网(https://wiki.winehq.org/Ubuntu) 安装 wine . 提醒网页可以切换成中...

Canaan_
今天
0
0
PHP后台运行命令并管理运行程序

php后台运行命令并管理后台运行程序 class ProcessModel{ private $pid; private $command; private $resultToFile = ''; public function __construct($cl=false){......

colin_86
今天
1
0
数据结构与算法4

在此程序中,HighArray类中的find()方法用数据项的值作为参数传递,它的返回值决定是否找到此数据项。 insert()方法向数组下一个空位置放置一个新的数据项。一个名为nElems的字段跟踪记录着...

沉迷于编程的小菜菜
今天
1
1
fiddler安装和基本使用以及代理设置

项目需求 由于开发过程中客户端和服务器数据交互非常频繁,有时候服务端需要知道客户端调用接口传了哪些参数过来,这个时候就需要一个工具可以监听这些接口请求参数,已经接口的响应的数据,这种...

银装素裹
今天
0
0
Python分析《我不是药神》豆瓣评论

读取 Mongo 中的短评数据,进行中文分词 对分词结果取 Top50 生成词云 生成词云效果 看来网上关于 我不是药神 vs 达拉斯 的争论很热啊。关于词频统计就这些,代码中也会完成一些其它的分析任...

猫咪编程
今天
0
0
虚拟机怎么安装vmware tools

https://blog.csdn.net/tjcwt2011/article/details/72638977

AndyZhouX
昨天
1
0
There is no session with id[xxx]

参考网页 https://blog.csdn.net/caimengyuan/article/details/52526765 报错 2018-07-19 23:04:35,330 [http-nio-1008-exec-8] DEBUG [org.apache.shiro.web.servlet.SimpleCookie] - Found......

karma123
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部