How are results guaranteed in algorithms that include intermediate approximation?

41 Views Asked by At

Let me elucidate this vague question with an example. Consider for example the following Gauss sum of roots of unity

$N=(e^{2\pi i/5} + e^{2\pi i/4} e^{4\pi i/5} + e^{4\pi i/4} e^{8\pi i/5} + e^{6\pi i/4} e^{16\pi i/5})^4$.

We know from Galois theory that this is expression is in $\mathbb{Z}[i]$. We could devise an algorithm to determine what this Gaussian integer is:

Approximate $e^{2\pi ij/5}$ via a decimal expansion to $m$ decimal places and use this approximation to compute $N$ while keeping the $4$-th roots of unity as formal symbols. Then round the coefficients to the nearest integers. As $m\rightarrow \infty$, we have that the decimal expansions should approach the correct integers, but

Question: If we are trying to determine a runtime for this algorithm, it must include $m$. Is there an effectively computable $m$ such that we can guarantee that the 'rounding' step returns the correct integers? I am questioning this in general, not just for this specific example: can there be guarantees in such algorithms?


For example, wolfram alpha uses a similar approximation, and returns -14.9999999999999999999999999999999999999999999999999999999999999 + 20.0000000000000000000000000000000000000000000000000000000000000 i. I want to say that this guarantees the expression is $-15+20i$, but is this true?