CS3343/3341 Analysis of Algorithms Spring 2012 |
Newton's Method
|
Newton's Method is used to find successive approximations to the roots of a function. If the function is y = f(x) and x0 is close to a root, then we usually expect x1 = x0 - f(x0) / f'(x0) to be a better approximation.
To get the square root of 2, one could approximate the positive root of the function y = 2 - x2. Plugging this into the formula for Newton's Method above, we get:| Newton's Method, sqrt(2) using double | Newton's Method, sqrt(2) using BigDecimal |
|---|---|
// Sqrt: sqrt 2 with Newton's method
public class Sqrt {
public double sqrt() {
double x = 1;
for (int i = 0; i < 6; i++) {
double xNew = x/2 + 1/x;
x = xNew;
System.out.println(x);
}
return x;
}
public static void main(String[] args) {
Sqrt sqrt = new Sqrt();
double x = sqrt.sqrt();
}
}
Output:
1.5
1.4166666666 666665
1.4142156862 745097
1.4142135623 746899
1.4142135623 73095
1.4142135623 73095
| // SqrtBig: sqrt 2 with Newton's method
import java.math.*;
public class SqrtBig {
BigDecimal one = new BigDecimal(1);
BigDecimal two = new BigDecimal(2);
public BigDecimal sqrt() {
BigDecimal x = one;
for (int i = 0; i < 9; i++) {
BigDecimal xNew = (x.divide(two)).add(one.
divide(x, 400, RoundingMode.HALF_EVEN));
x = xNew;
System.out.println(x);
}
System.out.println(x.multiply(x));
return x;
}
public static void main(String[] args) {
SqrtBig sqrtBig = new SqrtBig();
BigDecimal x = sqrtBig.sqrt();
// System.out.println(x);
}
}
|
sqrt(2) to 500 decimal places (from an independent source) 1. 0 4142135623 7309504880 1688724209 6980785696 7187537694 8073176679 7379907324 7846210703 8850387534 3276415727 1 3501384623 0912297024 9248360558 5073721264 4121497099 9358314132 2266592750 5592755799 9505011527 8206057147 2 0109559971 6059702745 3459686201 4728517418 6408891986 0955232923 0484308714 3214508397 6260362799 5251407989 3 6872533965 4633180882 9640620615 2583523950 5474575028 7759961729 8355752203 3753185701 1354374603 4084988471 4 6038689997 0699004815 0305440277 9031645424 7823068492 9369186215 8057846311 1596668713 0130156185 6898723723 | |
1.50000 1.4166666 1.41421568627 1.4142135623 746899 1.4142135623 7309504880 16896235 1.4142135623 7309504880 1688724209 6980785696 718753772340 1.4142135623 7309504880 1688724209 6980785696 7187537694 8073176679 7379907324 7846210703 8850387534 32764160163 1.4142135623 7309504880 1688724209 6980785696 7187537694 8073176679 7379907324 7846210703 8850387534 3276415727 3501384623 0912297024 9248360558 5073721264 4121497099 9358314132 2266592750 5592755799 9505011527 8206086685 1.4142135623 7309504880 1688724209 6980785696 7187537694 8073176679 7379907324 7846210703 8850387534 3276415727 3501384623 0912297024 9248360558 5073721264 4121497099 9358314132 2266592750 5592755799 9505011527 8206057147 0109559971 6059702745 3459686201 4728517418 6408891986 0955232923 0484308714 3214508397 6260362799 5251407989 6872533965 4633180882 9640620615 2583523950 5474575028 7759961729 8355752203 3753185701 1354374603 4393479974 2.0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0000000000 0872545735 | |