求一个数的平方根时，当数字极大或极小时，容易触碰到边界。
需要用一些技巧回避这个问题。
如下面容易出问题的代码：

def sqrt(x):
    def sqrt_iter(guess):
        return guess if good_enough(guess) else sqrt_iter(improve(guess))
    def good_enough(guess):
        tolerance = 1e-3
        return abs(guess**2 - x) < tolerance
    def improve(guess):
        return (guess + x/guess)/2
    initial_guess = 1.0
    return sqrt_iter(initial_guess)


print(sqrt(0))
print(sqrt(1e-12))
print(sqrt(1e-10))
print(sqrt(1e-8))
print(sqrt(1e-6))
print(sqrt(1e-4))
print(sqrt(1e-2))
print(sqrt(1e0))
print(sqrt(1e2))
print(sqrt(1e4))
print(sqrt(1e6))
print(sqrt(1e8))
print(sqrt(1e10))
print(sqrt(1e12))
print(sqrt(1e13))

输出结果：

0.03125
0.031250000010656254
0.03125000106562499
0.03125010656242753
0.031260655525445276
0.03230844833048122
0.10032578510960605
1.0
10.000000000139897
100.00000025490743
1000.0000000000118
10000.0
100000.0
1000000.0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 12, in sqrt
  File "<stdin>", line 3, in sqrt_iter
  File "<stdin>", line 3, in sqrt_iter
  File "<stdin>", line 3, in sqrt_iter
  [Previous line repeated 993 more times]
  File "<stdin>", line 6, in good_enough
RecursionError: maximum recursion depth exceeded while calling a Python object

正如我们所看到的,这个简单的程序在处理小数和大数时表现不佳:

• 对于小数(从x=10^-4及以下),容差10^-3太大,导致结果不够精确;
• 对于大数(从x=10^13及以上),容差10^-3太小,程序陷入无限递归。

这两个问题可以通过重新定义good_enough过程来解决,如下所示:

def good_enough(guess, x):
    return abs(improve(guess, x) - guess) < 1e-15 * abs(guess)

这个新的good_enough函数采用了相对误差的概念。它检查新的猜测值improve(guess, x)与当前猜测值guess之间的差值,是否小于当前猜测值的一个很小的比例(1e-15)。

这种方法可以解决之前的两个问题:

1. 对于小数,容差会随着猜测值的减小而减小,从而保证精确度。
2. 对于大数,容差会随着猜测值的增大而增大,避免了无限递归。

实际上,这种方法等同于下面的代码:

def good_enough(guess, x):
    return guess == 0 or improve(guess, x) == guess

这个函数检查当前猜测值是否为0(对应开平方的0),或者通过improve函数得到的新猜测值与当前猜测值相等(达到了要求的精度)。

使用这种相对误差或者检查”不再改变”的方式,就可以很好地处理各种数量级的被开方数了。

下面代码，实现了这里的3种策略：
1、最初的策略是在猜测值的绝对误差小于一个常数容差时停止改进猜测值。对于很小的被开方数,结果不够精确,因为容差没有按比例缩小到较小的被开方数的量级。对于很大的被开方数,sqrt-iter过程会进入无限递归,因为容差没有按比例扩大到较大的被开方数的量级,而且浮点数的表示精度是有限的,所以在那个量级上的绝对误差总是大于容差。对大被开方数观察到的问题,在选择一个使绝对误差在该量级上总是大于容差的容差时,也可以在小被开方数上观察到。
2、一种替代策略是在猜测值的绝对误差小于与被开方数成比例的可变容差时停止改进猜测值,换句话说,当猜测值的相对误差小于一个常数容差时。
3、另一种替代策略是在猜测值的绝对变化量小于与猜测值成比例的可变容差时停止改进猜测值,换句话说,当猜测值的相对变化量小于一个常数容差时。

这里是一个用Scheme实现前三种策略的程序(在sqrt-iter过程中使用相应的good-enough-{strategy-number}?过程来选择一种策略;关于策略2的最小容差的推导,请参见 https://math.stackexchange.com/a/3526215/194826 ;对策略3的最小容差使用了类似的推导):

def sqrt(x):
    def sqrt_iter(guess):
        return guess if good_enough_3(guess) else sqrt_iter(improve(guess))
    def good_enough_1(guess):
        tolerance = 1.0
        try:
            return abs(guess**2 - x) < tolerance
        except OverflowError:
            return False
    def good_enough_2(guess):
        tolerance = 3/2 * sys.float_info.epsilon
        try:
            return abs(guess**2 - x) < (
                sys.float_info.min if x == 0 else tolerance * x
            )
        except OverflowError:
            return False
    def good_enough_3(guess):
        tolerance = 9/4 * sys.float_info.epsilon
        return guess == 0 or abs(improve(guess) - guess) < tolerance * guess
    def improve(guess):
        return (guess + x/guess)/2
    initial_guess = 1.0
    return sqrt_iter(initial_guess)

在这个程序中:

sqrt函数调用sqrt_iter来计算平方根。
sqrt_iter是一个递归函数,它通过不断改进guess值来逼近平方根。
improve函数根据当前的guess值和被开方数x来计算出一个新的更接近平方根的guess值。
average函数计算两个数的平均值。
good_enough_1、good_enough_2和good_enough_3分别实现了三种不同的停止策略。
你可以通过取消对应策略函数的注释,并注释掉其他两个来选择使用哪种策略。

根据题目的要求,我已经实现了三种策略。你可以运行这个程序,并观察对于小数(如0.0001)和大数(如1000000000000)的结果。
需要注意的是,策略1的容差是根据被开方数x的绝对值动态计算的,而策略2和3的容差是固定的。你可以适当调整容差值来获得更好的结果。