Coseno relacionado con Bitwise XOR a través de raíces repetidas

Question

He estado haciendo un montón de cálculos que involucran coseno y he notado un patrón. Pasé algún tiempo y desarrolló este algoritmo para calcular los cosenos.

Para calcular el $\cos(x)$ donde $x$ está en radianes:

1. Desinfectar la entrada de manera que $x$ es $[0,2\pi)$:

   $x_1 \gets (|x| \mod 2\pi )$

2. Dividir por $\pi$. Esto por lo general es bastante trivial como radianes a menudo se expresan como múltiplos de $\pi$.

   $x_2 \gets x_1/\pi$

3. Esto es donde las cosas se ponen interesantes. El uso de la operación XOR en modo bit:

   $x_3 \gets x_2 \veebar 2x_2$

4. Aquí vamos a expresar $x_3$ en binario y mapa de su bits a las señales en una repetición de la raíz de 2, el cual será asignado a $x_4$. Esto es más fácil de ilustrar con un ejemplo más que con una fórmula:

   

5. Por último, dividir por 2:

   $x_5 \gets x_4/2$

Esto resultará en la $\cos(x)$, es decir, $\cos(x) = x_5$.

He utilizado este algoritmo bastante mucho ahora, y estoy seguro de que se calcula con precisión los cosenos, pero no puedo explicar por qué no iba a ser de esta relación entre el coseno y la operación XOR bit a bit.

¿Por qué esta relación existe? Por favor alguien puede explicar por qué los cosenos estaría relacionado con el operador XOR bit a bit como este.

Gracias!

---

Editar:

Para aquellos de ustedes que quieren una descripción más técnica para el paso 4, me tendrá que definir algunas cosas primero:

• Una función de $D$ que devuelve el valor de un dígito $d$ para un determinado número de $n$ en una base $b$:

  $$D(n,d,b) = \left \lfloor{n \cdot b^{-d}} \right \rfloor \mod b$$

• Una función recursiva $f$ que construye repetido raíces de 2 con $N$ radicales de los bits de $x$ asignado a los signos:

  $$f(x,n,N) = \begin{cases} 0 & n\geq N \\ (-1)^{D(x,-n,2)}\sqrt{2+f(x,n+1,N)} & n \lt N \end{casos} $$

• Una función de $F$ que se lleva a los límites de procesamiento de todos los bits de $x$ en la repetición de una raíz:

  $$F(x) = \lim_{N\to\infty} f(x,0,N)$$

Con los definidos, el paso 4 de arriba sería: $x_4 \gets F(x_3)$

Answer 1

Para cualquier $\theta \in [0,2)$, vamos a $(b_0.b_1b_2\cdots)_2$ la siguiente representación binaria de $\theta$.

$$\theta = \sum_{n=0}^\infty \frac{b_n}{2^n} \quad\text{ con }\quad b_n = {\rm mod}(\lfloor 2^n \theta \rfloor, 2) \in \{ 0, 1 \}$$

Vamos

• $c_n = b_n \veebar b_{n+1}$
• $\theta_0 = \theta$, $\theta_1 = (b_1.b_2b_3\cdots)_2$, $\theta_2 = (b_2\cdot b_3b_4\cdots)_2, \ldots$
• $\phi_0 = b_0$, $\phi_1 = (b_0.b_1)_2, \ldots, \phi_n = (b_0.b_1b_2\cdots b_n)_2\ldots$

Tenemos $$ \begin{align}2\cos(\pi\theta) = 2\cos(\pi\theta_0) &= \sqrt{2 + 2\cos(2\pi\theta_0)} \times \begin{cases} -1, & \theta_0 \in [\frac12,\frac32)\\ 1, & \text{ otherwise } \end{casos}\\ Y= (-1)^{b_0+b_1} \sqrt{2+2\cos(\pi(2b_0 + \theta_1))}\\ Y= (-1)^{c_0}\sqrt{2+2\cos(\pi\theta_1)} \end{align} $$ Repita este proceso, obtenemos

$$\begin{align}2\cos(\pi\theta) = & (-1)^{c_0}\sqrt{2 + (-1)^{c_1}\sqrt{2 + 2\cos(\pi \theta_2)}}\\ \vdots\; &\\ = & (-1)^{c_0}\sqrt{2 + (-1)^{c_1}\sqrt{2 + (-1)^{c_2}\sqrt{\cdots (-1)^{c_m} \sqrt{2 + 2\cos(\pi\theta_{m+1})}}}}\tag{*1}\\ \vdots\;& \end{align} $$ En este proceso, si queremos terminar en el paso $(*1)$ reemplazando $\theta_{m+1}$ con $0$, el valor de RHS de $(*1)$ hace $2\cos(\pi\phi_m)$. Desde $2\cos(\pi\phi_m) \to 2\cos(\pi\theta)$ como $m \to \infty$, obtenemos siguiente anidado radical de expansión:

$$2\cos(\pi\theta) = (-1)^{c_0}\sqrt{2 + (-1)^{c_1}\sqrt{2 + (-1)^{c_2}\sqrt{ 2 + \cdots }}}$$

Ahora tome $x_2 = \theta$, luego

$$\begin{align} x_3 &= x_2 \veebar 2x_2 = (b_0c_0.c_1c_2\ldots)_2\\ \text{and}\quad x_4 &= 2\cos(\pi\theta)\\ &\,\Downarrow\\ x_5 &= \frac{x_4}{2} = \cos(\pi x_2) = \cos(x_1) = \cos(|x|) = \cos(x) \end{align}\\ $$ Aparte de la extra regla de ignorar el líder de $b_0$ en la representación binaria de $x_2 \veebar 2x_2$. Esta es la receta de la informática $\cos(x)$.