Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$ where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i x}$. I'm interested in knowing if there is a faster way to calculate values of this rather than just adding up the $\varphi(c) \leq c$ values of the sum. By calculate here, I just mean to find a good numerical approximation; the definition already gives an exact expression for it as an element of $\mathbb{Z}[e^{2\pi i/c}]$ which probably can't be improved by much in general. I'm interested in $m$ and $n$ fixed, and how fast it can be computed in terms of $c$. The case $c=$prime is probably the most interesting. I'd also be interested to know if people have considered the speed of evaluation of the full list of values of $S(m,n;c)$ for $c \leq C$.

For the case of a Gauss sum to modulus $q$, I have heard that it is "well-known" how to calculate it in around $\sqrt{q}$ steps as follows. The main point is to use the fact that the completed Dirichlet $L$-function has the approximate functional equation (See Theorem 5.3 of Iwaniec and Kowalski's book) $$L(1/2, \chi) = \sum_{n} \frac{\chi(n)}{\sqrt{n}} V(\frac{n}{X \sqrt{q}}) + \epsilon(\chi) \sum_{n} \frac{\overline{\chi}(n)}{\sqrt{n}} V(nX/\sqrt{q}).$$ Here $V$ is a special function that in practice can be calculated (e.g. in Mike Rubinstein's Lcalc package), $\epsilon(\chi) = i^{-a} \tau(\chi) q^{-1/2}$ where $a$ is $0$ or $1$ if $\chi$ is even or odd, $\tau(\chi)$ is the Gauss sum, and $X> 0$ is a parameter to choose. Write this in the form $L(1/2, \chi) = A(X) + \epsilon(\chi)B(X)$. Taking say $X=1$ and another value of $X$ close to $1$ will give different values for $A(X)$ and $B(X)$, and so one can solve for $\epsilon(\chi)$. The function $V(x)$ has rapid decay for $x \gg 1$, so it takes around $\sqrt{q}$ terms in the sum to evaluate $A(X)$ and $B(X)$, far fewer than the full $q$ terms needed to evaluate the Gauss sum by definition.