文档章节

69. Sqrt(x)

Do0M
 Do0M
发布于 2017/08/26 21:35
字数 279
阅读 2
收藏 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
Leetcode 69. Sqrt(x)

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Binary Search Newton's Method Reference https://leetcode.com/problems/sqrtx/description/......

SnailTyan
08/03
0
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

没有更多内容

加载失败,请刷新页面

加载更多

70.shell的函数 数组 告警系统需求分析

20.16/20.17 shell中的函数 20.18 shell中的数组 20.19 告警系统需求分析 20.16/20.17 shell中的函数: ~1. 函数就是把一段代码整理到了一个小单元中,并给这个小单元起一个名字,当用到这段...

王鑫linux
今天
2
0
分布式框架spring-session实现session一致性使用问题

前言:项目中使用到spring-session来缓存用户信息,保证服务之间session一致性,但是获取session信息为什么不能再服务层获取? 一、spring-session实现session一致性方式 用户每一次请求都会...

WALK_MAN
今天
6
0
C++ yield()与sleep_for()

C++11 标准库提供了yield()和sleep_for()两个方法。 (1)std::this_thread::yield(): 线程调用该方法时,主动让出CPU,并且不参与CPU的本次调度,从而让其他线程有机会运行。在后续的调度周...

yepanl
今天
4
0
Java并发编程实战(chapter_3)(线程池ThreadPoolExecutor源码分析)

这个系列一直没再写,很多原因,中间经历了换工作,熟悉项目,熟悉新团队等等一系列的事情。并发课题对于Java来说是一个又重要又难的一大块,除非气定神闲、精力满满,否则我本身是不敢随便写...

心中的理想乡
今天
43
0
shell学习之获取用户的输入命令read

在运行脚本的时候,命令行参数是可以传入参数,还有就是在脚本运行过程中需要用户输入参数,比如你想要在脚本运行时问个问题,并等待运行脚本的人来回答。bash shell为此提 供了read命令。 ...

woshixin
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部