After unearthing and giving a proof of what is now known as the Riemann–Siegel formula for the Riemann zeta function enabling the computation of $zeta(1/2+iT)$ in time $O(T^{1/2})$,

in 1943 Siegel published a generalization for L-functions of Dirichlet characters (sorry, I don’t know how to put a link to that paper). If $m$ denotes the conductor of the character, it

seems to me that the time is now $O((mT)^{1/2})+O(m)$. The $(mT)^{1/2}$ term is clearly

necessary, but I do not see how to remove the $O(m)$ term, which is quite annoying in practice

when $m$ becomes large.

One of the reasons I ask is that in a relatively recent arXiv paper (arXiv:1703.01414v7)

K.~Fisher describes another algorithm which runs in $O((mT)^{1/2})$, without the $O(m)$.

Implementations of both algorithms seem to show that Siegel’s is considerably faster

(i.e., the implicit big-Oh constant is much smaller), but only when $m$ is small, and even

for $m$ as small as $10^5$ the $O(m)$ term becomes a huge problem and Fisher’s algorithm is

much faster. Does anyone have any idea

about this (sorry if too technical/specialized) ?