I know that there exists CORDIC algorithm, but CORDIC algorithm contains component $\arctan 2^{-i}$, which needs to be looked up. I do not know how this leads to the precision that is advertised by CORDIC algorithm.
Regardless of CORDIC, is there any algorithm that computes sine function within certain precision? If CORDIC can do this job, how?
The first step in calculating the sine function should be a parameter check, to see if an answer would be meaningful. For example, finding $\sin(10^{20})$ would be meaningless if your system cannot handle $19$ digits of precision. If $x$ cannot be pinned down within a precision of $2\pi$ then $\sin(x)$ could literally be anything in the range of sine. So trying to calculate $\sin(10^{20})$ should raise a precision error.
The second step is "range reduction," reducing the range of the parameter. Using the symmetries of the sine function, $\sin x$ is equal to either $\pm\sin u$ or $\pm\cos u$ for some $0\le u\le\frac{\pi}4$.
A standard way of continuing is to use polynomial approximation by Taylor (Maclaurin) series. If we let
$$S_{2n+1}(x)=\sum_{i=0}^n(-1)^i\frac{x^{2i+1}}{(2i+1)!}$$
then we can prove that $\sin x$ is always between any two consecutive terms of the sequence $S_{2n+1}(x)$. We can also prove
$$\left| S_{2n+1}(x)-S_{2n-1}(x)\right|=\frac{|x|^{2n+1}}{(2n+1)!}$$
That expression on the right is therefore an error bound on the sine approximation. Since it has a limit of zero as $n$ approaches infinity, just choose an appropriate value of $n$ and use that polynomial. For example, the double-precision floating point type has between $15$ and $16$ significant digits, so a value of $n=17$ is better than sufficient.
Note that this analysis does not take computation errors into account. In actual application you will probably replace the Taylor polynomial with a Chebyshev polynomial or similar polynomial with fewer terms that gives the same precision. But this should give you an idea of how to get any desired precision for the sine function.