CS3343/3341 Analysis of Algorithms Weird Topic |
Newton's Method to
Perform Division and Sqrt Presented Side-by-side |
The table below illustrates the remarkable similarity between the program to divide (compute an inverse) and the program to take the square root. The differences are highlighted in bold red. Differences in the comments and in the names of variables are not highlighted. (The variable names on the left mostly have a "r" where those on the right have a "d".) There are only 6 differences, labeled 1 - 6 at the left.
It should be emphasized that these programs only give a "feasibility of concept" and are not remotely the sort of optimized code that would actually be used for tasks like these in a commercial implementation.| Square Root of the arbitrary double r > 0 | Division by the arbitrary double d > 0 |
|---|---|
// Root: use Newton's method for sqrt(r)
// includes normalization.
public class Root {
private double mul; // denormalizing factor
// norm: normalize to 0.25 <= r <= 1.0
public double norm(double r) {
// divide d by power of 2
mul = 1.0; // power of 2
double r0 = r;
while (r0 > 1) {
// divide by 4, will
// later multiply by 2
/*1*/ r0 = r0/4.0;
mul = mul*2.0;
}
/*2*/ while (r0 < 0.25) {
/*3*/ r0 = r0*4.0;
mul = mul/2.0;
}
// r0 now normalized
return r0;
}
// denorm: reverse the normalization
public double denorm(double sqrtR0) {
/*4*/ return sqrtR0*mul;
}
// calculate sqrt(r0), 0.25 <= d0 <= 1
public double sqrt0(double r0) {
// initial approx: x0 = (2/3)r0 + 0.3506
/*5*/ double x0 = 0.66666*r0 + 0.3506;
System.out.println("1st approx to sqrt(r0):"+ x0);
double x1;
for ( ; ; ) {
/*6*/ x1 = x0/2.0 + r0/(2.0*x0);
System.out.println(x1);
if (Math.abs(x1 - x0) < 1.0e-7) break;
x0 = x1;
}
return x1;
}
public static void main(String[] args) {
// calculate sqrt(r) for any r > 0
Root root = new Root();
double r = Double.parseDouble(args[0]);
System.out.println("r:" + r + ", want sqrt(r)");
// normalize to 0.25 <= r<= 1
double r0 = root.norm(r);
// r0 now normalized
System.out.println("normalized, r0:" + r0 +
", want sqrt(r0)");
double sqrtR0 = root.sqrt0(r0);
// denoramlize: multipy sqrtR0 by mul
double sqrtR = root.denorm(sqrtR0);
System.out.println("sqrt(" + r + ") = \t" + sqrtR);
System.out.println("check on ans:\t" +
Math.sqrt(r));
}
}
| // DivD: use Newton's method for 1/d
// only divisions used are by 2
public class DivD {
private double mul; // denormalizing factor
// normalize to 0.5 <= d <= 1
public double norm(double d) {
// divide d by power of 2
mul = 1.0; // power of 2
double d0 = d;
while (d0 > 1) {
// divide by 2, will
// later divide by 2 again
d0 = d0/2.0;
mul = mul*2.0;
}
while (d0 < 0.5) {
d0 = d0*2.0;
mul = mul/2.0;
}
// d0 now normalized
return d0;
}
// denorm: reverse the normalization
public double denorm(double invD0) {
return invD0/mul;
}
// calculate 1/d0, 0.5 <= d0 <= 1
public double invD(double d0) {
// initial approx: 48/17 - 32/17*d0
double x0 = 2.82353 - 1.88235*d0;
System.out.println("1st approx to 1/d0:"+ x0);
double x1;
for ( ; ; ) {
x1 = x0*(2 - d0*x0);
System.out.println(x1);
if (Math.abs(x1 - x0) < 1.0e-7) break;
x0 = x1;
}
return x1;
}
public static void main(String[] args) {
// calculate 1/d for any d > 0
DivD divD = new DivD();
double d = Double.parseDouble(args[0]);
System.out.println("d:" + d + ", want 1/d");
// normalize to 0.5 <= d <= 1
double d0 = divD.norm(d);
// d0 now normalized
System.out.println("normalized, d0:" + d0 +
", want 1/d0");
double invD0 = divD.invD(d0);
// denoramlize: divide invD0 by mul
double invD = divD.denorm(invD0);
System.out.println("1/" + d + " = \t" + invD);
System.out.println("check on ans:\t" +
1.0/d);
}
}
|