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. 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) ?
