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

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题就不是难事了
另外，上述方法也适合求多项式的根，想知道更多，可以去翻《数值分析》

评论

2 楼 OpenMind 2012-02-01  

chenmouren 写道

军哥v5！ps: pythan写错了。

1 楼 chenmouren 2012-02-01  

军哥v5！ps: pythan写错了。