总结求平方根sqrt的三种方法，首先是牛顿迭代法：
function abs(x) {
return x >= 0 ? x : -x;
}
function square(x) {
return x * x;
}
function good_enough(guess, x) {
return abs(square(guess) - x) < 0.001;
}
function average(x, y) {
return (x y) / 2;
}
function improve(guess, x) {
return average(guess, x / guess);
}
function sqrt_iter(guess, x) {
return good_enough(guess, x)
? guess
: sqrt_iter(improve(guess, x), x);
}
function sqrt(x) {
return sqrt_iter(1, x);
}
sqrt(5);
> 2.2360688956433634
其次是二分法：
function average(x, y) {
return (x y) / 2;
}
function positive(x) { return x > 0; }
function negative(x) { return x < 0; }
function abs(x) {
return x >= 0 ? x : -x;
}
function close_enough(x, y) {
return abs(x - y) < 0.001;
}
function search(f, neg_point, pos_point) {
let midpoint = average(neg_point, pos_point);
if (close_enough(neg_point, pos_point)) {
return midpoint;
} else {
let test_value = f(midpoint);
if (positive(test_value)) {
return search(f, neg_point, midpoint);
} else if (negative(test_value)) {
return search(f, midpoint, pos_point);
} else {
return midpoint;
}
}
}
function binary_search_method(f, a, b) {
let a_value = f(a);
let b_value = f(b);
return negative(a_value) && positive(b_value) ? search(f, a, b)
: negative(b_value) && positive(a_value) ? search(f, b, a)
: error("values are not of opposite sign");
}
console.log(binary_search_method(x => x ** 2 - 5, 0, 5));
> 2.23602294921875
最后是“不动点方程”：
function abs(x) {
return x >= 0 ? x : -x;
}
const tolerance = 0.00001;
function fixed_point(f, first_guess) {
function close_enough(x, y) {
return abs(x - y) < tolerance;
}
function try_with(guess) {
const next = f(guess);
return close_enough(guess, next)
? next
: try_with(next);
}
return try_with(first_guess);
}
function average(x, y) {
return (x y) / 2;
}
function sqrt(x) {
return fixed_point(y => average(y, x / y), 1);
}
sqrt(5);
以上为三种求“平方根”的方法。
,
