a more sophisticated application of the turing method

[p15-git-acc]

This PR makes more efficient use of evaluated nodes to sometimes speed up isolation of a zero of the Hardy Z-function. For example the time required to isolate the 8637740722917th and 8637740722918th zeros is reduced by ~25%.

When n is large, the mpmath algorithm immediately starts looking for 2*B consecutive good blocks above the predicted zero location and for 2*B consecutive good blocks below the predicted zero location, where B is a Turing method bound. An advantage of this strategy is that N(t) is known with certainty at the Gram point in the middle of each stretch of consecutive good blocks. This certainty simplifies the algorithm.

But it's not always necessary to have a 2*B stretch to learn N(t). If you can find k sign changes in a region of k Gram intervals then if this region is bracketed by stretches of B consecutive good blocks, this is sufficient to learn N(t) at the endpoints of the region and therefore to isolate the nth Hardy Z-function zero if it's in that region. The mpmath algorithm uses this idea when it checks whether it can find k sign changes in k Gram intervals bracketed by the 2*B stretches that it has found, before it resorts to using the Gram point in the middle of the 2*B stretches.

The improvement in this PR is to pause when we first reach B-sized stretches on our way to searching for the 2*B-sized stretches. At that point in the search we check whether we can find enough sign changes in the bracketed region to know N(t). If we don't have enough sign changes then we continue as in the mpmath algorithm. But if we see enough sign changes then we report the isolated zero and do not continue the search for 2*B-sized stretches.

[fredrik-johansson]

Fantastic!

[fredrik-johansson]

The improvement is apparently even bigger for generic large n.

Timings before this patch (prec = 53):

n = 10^0  0.004  
n = 10^1  0.004  
n = 10^2  0.0064  
n = 10^3  0.0117  
n = 10^4  0.0135  
n = 10^5  0.0091  
n = 10^6  0.0093  
n = 10^7  0.019  
n = 10^8  0.054  
n = 10^9  0.207  
n = 10^10  0.506  
n = 10^11  1.276  
n = 10^12  6.099  
n = 10^13  15.326  
n = 10^14  56.285  
n = 10^15  134.899  
n = 10^16  679.095  

After this patch:

n = 10^0  0.004  
n = 10^1  0.0039  
n = 10^2  0.0063  
n = 10^3  0.0116  
n = 10^4  0.0133  
n = 10^5  0.0089  
n = 10^6  0.0093  
n = 10^7  0.0176  
n = 10^8  0.042  
n = 10^9  0.169  
n = 10^10  0.39  
n = 10^11  0.939  
n = 10^12  3.942  
n = 10^13  8.478  
n = 10^14  36.133  
n = 10^15  79.428  
n = 10^16  285.492