zetazero is suboptimal? #958
Description
Here is my test code:
#!/usr/bin/python3
import mpmath
import sys
import time
def method1(ctx, range_):
for x in range_:
ctx.nprint(ctx.im(ctx.zetazero(x)), ctx.dps+2, strip_zeros=False)
def method2(ctx, range_):
for x in range_:
initial = mpmath.fp.im(mpmath.fp.zetazero(x))
k = initial * mpmath.fp.eps
root = ctx.findroot(ctx.siegelz, [initial, initial+k], solver="secant")
ctx.nprint(root, ctx.dps+2, strip_zeros=False)
with mpmath.mp.workprec(100):
t1 = time.time()
method1(mpmath.mp, range(9990, 10000))
t2 = time.time()
print()
method2(mpmath.mp, range(9990, 10000))
t3 = time.time()
print()
with mpmath.mp.extraprec(30):
method2(mpmath.mp, range(9990, 10000))
t4 = time.time()
print(f"Method 1: {t2 - t1} seconds")
print(f"Method 2: {t3 - t2} seconds")
print(f"Method 2 (more digits): {t4 - t3} seconds")On my machine (mpmath 1.3.0) it produces the following:
9868.714659330643201731352988040
9869.812878325986458201906576863
9870.332258556616445749494357358
9872.000623378132955731719993135
9872.558666059604231912379326542
9873.802220903648406406781798992
9874.323957629064029672232728985
9875.218994098846767145580371717
9875.600956248756888587220599532
9876.479017063783790065513504888
9868.714659330643201731352988036
9869.812878325986458201906576864
9870.332258556616445749494357359
9872.000623378132955731719993140
9872.558666059604231912379326545
9873.802220903648406406781798987
9874.323957629064029672232728989
9875.218994098846767145580371711
9875.600956248756888587220599535
9876.479017063783790065513504884
9868.714659330643201731352988035649035334
9869.812878325986458201906576863536161488
9870.332258556616445749494357359202336099
9872.000623378132955731719993139527864878
9872.558666059604231912379326545444598555
9873.802220903648406406781798986980788123
9874.323957629064029672232728988590912143
9875.218994098846767145580371710801805777
9875.600956248756888587220599534886719983
9876.479017063783790065513504884342609249
Method 1: 15.640349388122559 seconds
Method 2: 7.93834376335144 seconds
Method 2 (more digits): 11.716793060302734 seconds
Method 1 is the built-n zetazero at the requested precision. Method 2 uses zetazero in fp context, and then refines that guess to the requested precision using the secant method. Obviously the timings will be different for individual people, and for large enough zeros a lower-precision mp context would need to be used because fp would not be enough. But the speed difference is significant and (for me) consistent across a range of precisions and zeros.
I think what's going on here is that the secant method is just intrinsically more efficient than the custom Newton-based method that zetazero uses. It converges more slowly, but by avoiding the need for a derivative it avoids a lot of extra work which more than makes up the difference.
As a side note, I'm printing the values to 2 extra digits to show that Method 2 also is more accurate.