文档章节

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

BlackJoker
 BlackJoker
发布于 2015/10/13 13:24
字数 459
阅读 31
收藏 0
点赞 0
评论 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)=0 求零根问题 设 r 是 f(x)=0 的一个根,则 x0 处的切线方程为 选取 x0 为接近根的初始值,不断用过 点的切线将 的过程就是迭代过程。 所以 xn 是 的解。 整...

Spance ⋅ 2014/04/28 ⋅ 0

牛顿开方法的算法及其原理

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

Nob ⋅ 2016/02/13 ⋅ 0

微分方程数值分析基础:Euler法

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

zhangphil ⋅ 01/05 ⋅ 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

Newton-Raphson切线法解高次方程近似根

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

zhangphil ⋅ 2017/12/27 ⋅ 0

Common Lisp牛顿法求平方根

1)牛顿法求平方根: 公式:(y + x/y) / 2,首先猜测为1,然后逐渐逼近。 (defun sqrt-iter (guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) (defun improve......

努力喵 ⋅ 2016/02/03 ⋅ 0

优化算法——牛顿法(Newton Method)

一、牛顿法概述 除了前面说的梯度下降法,牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法的基本思想是利用迭代点处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近...

google19890102 ⋅ 2014/11/13 ⋅ 0

ACM程序设计大赛题目分类

第一类:基础算法 (1) 基础算法:枚举,贪心,递归,分治,递推,构造,模拟 (2) 动态规划:背包问题,树形dp,状态压缩dp,单调性优化,插头dp (3) 搜索:dfs,bfs,记忆化搜索,优化...

齐勇cn ⋅ 2016/04/20 ⋅ 0

机器学习之牛顿法

泰勒公式 首先看泰勒公式,对于函数,如果函数平滑且某点存在各阶导数,则可以用一个多项式来描述该点邻域的近似值。公式如下: 牛顿法 牛顿法一般用来求解方程的根和求解极值。 数值优化算法...

超人汪小建 ⋅ 2017/11/16 ⋅ 0

机器学习|逻辑回归里有哪些逻辑?

目录: 1.逻辑回归 2.牛顿法求极值 3.指数分布族与多项分布 4.广义线性模型 前言 在看逻辑回归之前,先回想一下线性回归问题的求解步骤,再顺着线性回归,来介绍逻辑回归。 1.首先假设误差存...

最会设计的科研狗 ⋅ 2017/07/09 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

CENTOS7防火墙命令记录

安装Firewall命令: yum install firewalld firewalld-config Firewall开启常见端口命令: firewall-cmd --zone=public --add-port=80/tcp --permanent firewall-cmd --zone=public --add-po......

cavion ⋅ 41分钟前 ⋅ 0

【C++】【STL】利用chromo来测量程序运行时间与日志时间打印精确到微秒

直接上代码吧,没啥好说的。头疼。 #include <iostream>#include <string>#include <ctime>#include <sstream>#include <iomanip>#include <thread>#include <chrono>using ......

muqiusangyang ⋅ 44分钟前 ⋅ 0

Mac环境下svn的使用

在Windows环境中,我们一般使用TortoiseSVN来搭建svn环境。在Mac环境下,由于Mac自带了svn的服务器端和客户端功能,所以我们可以在不装任何第三方软件的前提下使用svn功能,不过还需做一下简...

故久呵呵 ⋅ 54分钟前 ⋅ 0

破解公司回应苹果“USB限制模式”:已攻破

本周四,苹果发表声明称 iOS 中加入了一项名为“USB 限制模式”的功能,可以防止 iPhone 在连接其他设备的时候被破解,并且强调这一功能并不是针对 FBI 等执法部门,为的是保护用户数据安全。...

六库科技 ⋅ 55分钟前 ⋅ 0

MyBtais整合Spring Boot整合,TypeHandler对枚举类(enum)处理

概要 问题描述 我想用枚举类来表示用户当前状态,枚举类由 code 和 msg 组成,但我只想把 code 保存到数据库,查询处理,能知道用户当前状态,这应该怎么做呢?在 Spring 整合MyBatis 的时候...

Wenyi_Feng ⋅ 今天 ⋅ 0

synchronized与Lock的区别

# <center>王梦龙的读书笔记第一篇</center> ## <center>-synchronized与Lock的区别</centre> ###一、从使用场景来说 + synchronized 是能够注释代码块、类、方法但是它的加锁是和解锁使用一......

我不想加班 ⋅ 今天 ⋅ 0

VConsole的使用

手机端控制台打印输出,方便bug的排查。 首先需要引入vconsole.min.js 文件,然后在文件中创造实例。就能直接使用了。 var vConsole = new VConsole(); vConsole的文件地址...

大美琴 ⋅ 今天 ⋅ 0

Java NIO之字符集

1 字符集和编解码的概念 首先,解释一下什么是字符集。顾名思义,就是字符的集合。它的初衷是把现实世界的符号映射为计算机可以理解的字节。比如我创造一个字符集,叫做sex字符集,就包含两个...

士别三日 ⋅ 今天 ⋅ 0

Spring Bean基础

1、Bean之间引用 <!--如果Bean配置在同一个XML文件中,使用local引用--><ref bean="someBean"/><!--如果Bean配置在不同的XML文件中,使用ref引用--><ref local="someBean"/> 其实两种......

霍淇滨 ⋅ 今天 ⋅ 0

05、基于Consul+Upsync+Nginx实现动态负载均衡

1、Consul环境搭建 下载consul_0.7.5_linux_amd64.zip到/usr/local/src目录 cd /usr/local/srcwget https://releases.hashicorp.com/consul/0.7.5/consul_0.7.5_linux_amd64.zip 解压consu......

北岩 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部