文档章节

Project Euler Problem 80-高精度开方-牛顿逼近法

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 459
阅读 40
收藏 0
It is well known that if the square root of a natural number is not an integer, then it is irrational. The decimal expansion of such square roots is infinite without any repeating pattern at all.

The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits for all the irrational square roots.

这个题涉及到高精度开方,像python,haskell等语言原生支持高精度小数,做这个题不成问题,直接使用api即可。我习惯用java,研究BigDecimal发现里面没有开方的方法,所以需要手动实现。可以采用牛顿逼近法解决开方问题,可以用BigDecimal实现高精度。牛顿逼近法参见:http://baike.baidu.com/view/1514354.htm
// 0.0000001是精度,f是待求根的函数,df是f的导数,x0是初值
  public static double newtonMehtod(F f, DF df, double x0) {
		double x1 = x0 - f.f(x0) / df.df(x0);
		while (Math.abs(x1 - x0) > 0.0000001) {
			x0 = x1;
			x1 = x0 - f.f(x0) / df.df(x0);
		}
		return x1;
  }
//函数f(x)
public interface F {
	double f(double x);
}
//f(x)的导数f'(x)
public interface DF {
	double df(double x);
}

F和DF的实现类没贴上来。
下面用BigDecimal把上述算法翻译一遍:
static int prec = 100;
	static BigDecimal precE;
	static {
		String e = "-0.";
		for (int i = 0; i < prec; i++) {
			e += "0";
		}
		e += "1";
		precE = new BigDecimal(e);
	}

	public static BigDecimal newtonMehtod(F f, DF df, double x00) {
		BigDecimal x0 = BigDecimal.valueOf(x00);
		BigDecimal x1 = x0.add(f.f(x0)
				.divide(df.df(x0), BigDecimal.ROUND_HALF_EVEN).negate());
		while (x1.add(x0.negate()).abs().add(precE).compareTo(BigDecimal.ZERO) > 0) {
			x0 = x1;
			x1 = x0.add(f.f(x0).divide(df.df(x0), BigDecimal.ROUND_HALF_EVEN)
					.negate());
		}
		return x1;
	}

public interface F {
	BigDecimal f(BigDecimal x);
}
public interface DF {
	BigDecimal df(BigDecimal x);
}

当prec取100时,算出来2的平方根是:
1.4142135623730950488016887242096980785696718
753769480731766797379907324784621070388503875
343276415727350138462309122970249248360558507
372126441214970999358314132226659275055927557
999505011527820605714701095599716059702745345
968620147285174186408891986095523.
有了上面的探索,解决80题就不是难事了
另外,上述方法也适合求多项式的根,想知道更多,可以去翻《数值分析》

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
牛顿开方法的算法及其原理

【牛顿迭代法】 假设方程 在 附近有一个根,那么用以下迭代式子: 依次计算、、、……,那么序列将无限逼近方程的根。 牛顿迭代法的原理很简单,其实是根据f(x)在x0附近的值和斜率,估计f(x...

Nob
2016/02/13
230
0
微分方程数值分析基础:Euler法

微分方程数值分析基础:Euler法 Euler法作为数值分析的一种方法,主要解决微分方程在求出精确公式没有必要,求不到或者非常困难情况下有用。为数值分析提供了一种渐变的分析手段,但是也要看...

zhangphil
01/05
0
0
LeetCode:Sqrt(x) - 整数开方

1、题目名称 Sqrt(x)(整数开方) 2、题目地址 https://leetcode.com/problems/sqrtx 3、题目内容 英文:Implement int sqrt(int x). Compute and return the square root of x. 中文:实现函......

北风其凉
2015/08/12
0
0
【数学基础篇】---详解极限与微分学与Jensen 不等式

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/LHWorldBlog/article/details/82599231

LHWorldBlog
09/09
0
0
Newton-Raphson切线法解高次方程近似根

Newton-Raphson切线法解高次方程近似根 对于一般的一次,二次方程来说,求解方程的根比较简单。但是对于四次、五次甚至更高次方程,求解方程的f(x)=0的根变得十分困难甚至不可能完成。为此N...

zhangphil
2017/12/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

no such module 'pop'问题

在github上 clone 了一个 swift 项目,编译时提示"no such module 'POP'"错误,查了一下居然是因为podfile中指定的最低版本是iOS 11.0,大于我测试手机的iOS版本10.3.3,将Podfile中的最低版...

yoyoso
50分钟前
1
0
redis 系列一 -- 简介及安装

1.简介 redis -- remote dictionary server 远程字典服务 使用 C 语言编写; 高性能的 key-value数据库; 内存数据库,支持数据持久化。 Redis 是一个开源(BSD许可)的,内存中的数据结构存...

imbiao
今天
3
0
nginx log记录请求响应时间

有时为了方便分析接口性能等,需要记录请求的时长,通过修改nginx的日志格式可以做到,如 添加一个新的log_format log_format timed_combined '$remote_addr - $remote_user [$time_local] "...

swingcoder
今天
4
0
Spring MVC之RequestMappingHandlerMapping匹配

对于RequestMappingHandlerMapping,使用Spring的同学基本都不会陌生,该类的作用有两个: 通过request查找对应的HandlerMethod,即当前request具体是由Controller中的哪个方法进行处理; 查...

爱宝贝丶
今天
3
0
Java Web--增删改查之二界面后台java代码(转载参考)

/** *  *//** * @author Administrator * */package dao; import java.sql.*;public class DBConn {/** * 链接数据库 * @return */  ...

小橙子的曼曼
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部