为什么提高精度会使这个程序更快？

Question

我正在解决 Project Euler 上的问题 26，我需要计算 1/n 的重复部分的长度，其中 n 是 1 到 1000 之间的所有整数，并查看哪个数字是最长的重复部分。这意味着我需要更精确地完成我的部门。因此，我通过更改 来玩弄我的小数精度getContext().prec，但随后以某种方式提高精度使程序速度更快。我使用 Python 3.7 运行了这个程序。这是代码：

import re

import time

s = time.time()

from decimal import *

getcontext().prec = 500 #This part

recurring = 0

answer = 0

p = re.compile(r"([0-9]+?)\1{3,}")

for i in range(1, 1000):

    f = p.search(str(Decimal(1) / Decimal(i))[5:])

    if f:

        number = f.group(1)

        if len(str(number)) > len(str(recurring)):

            recurring = number

            answer = i

print(answer)

print(time.time() - s)

这是我使用 500 精度时的结果：

>>> print(answer)

349

>>> print(time.time() - s)

2.923844575881958

...这就是我使用 5000 精度时得到的结果：

>>> print(answer)

983

>>> print(time.time() - s)

0.07812714576721191

我把 500 换成了 5000，它不仅给了我正确的答案，因为 1/answer 的重复部分可能比 500 长，而且速度也快得多。我已经用在线 Python 解释器尝试过这个，它也给了我类似的结果。为什么会这样？

Answer 1

在 prec == 4000 附近发生了一些事情。所有答案都等于 983，并且时间从 4000 开始仅略微线性变化。也许仔细看看那里。2000 年左右也有小幅下降。您需要分别测量十进制除法期间经过的时间和正则表达式搜索期间经过的时间以获取更多信息。在此图像上：prec（水平）与时间（以秒为单位）（垂直）