6
$\begingroup$

I have been doing a lot of calculations involving cosine and have noticed a pattern. I spent some time and developed this algorithm for calculating cosines.

To calculate the $\cos(x)$ where $x$ is in radians:

  1. Sanitize the input so that $x$ is $[0,2\pi)$:

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

  2. Divide by $\pi$. This is usually fairly trivial as radians are often expressed as multiples of $\pi$.

    $x_2 \gets x_1/\pi$

  3. This is where things get interesting. Use the bitwise XOR operation:

    $x_3 \gets x_2 \veebar 2x_2$

  4. Here we are going to express $x_3$ in binary and map its bits to signs in a repeated root of 2, which will then be assigned to $x_4$. This is easier to illustrate with an example rather than with a formula:

    Bits to Repeated Root

  5. Finally, divide by 2:

    $x_5 \gets x_4/2$

This will result in the $\cos(x)$, i.e. $\cos(x) = x_5$.

I have used this algorithm quite a lot now, and I am confident that it accurately calculates cosines, but I can't explain why there would be this relationship between cosine and bitwise XOR.

Why does this relation exist? Can someone please explain why cosines would be related at all to the bitwise XOR operator like this.

Thanks!


Edit:

For those of you who want a more technical description for step 4, I will need to define some things first:

  • A function $D$ that returns the value of a given digit $d$ for a given number $n$ in a given base $b$:

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

  • A recursive function $f$ that builds repeated roots of 2 with $N$ radicals from the bits of $x$ mapped to the signs:

    $$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{cases} $$

  • A function $F$ that takes the limits of processing all the bits of $x$ into a repeated root:

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

With those defined, step 4 from above would be: $x_4 \gets F(x_3)$

$\endgroup$
3
$\begingroup$

For any $\theta \in [0,2)$, let $(b_0.b_1b_2\cdots)_2$ be following binary representation of $\theta$.

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

Let

  • $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$

We have $$ \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{cases}\\ &= (-1)^{b_0+b_1} \sqrt{2+2\cos(\pi(2b_0 + \theta_1))}\\ &= (-1)^{c_0}\sqrt{2+2\cos(\pi\theta_1)} \end{align} $$ Repeat this process, we get

$$\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} $$ In this process, if we terminate at step $(*1)$ by replacing $\theta_{m+1}$ with $0$, the value of RHS of $(*1)$ becomes $2\cos(\pi\phi_m)$. Since $2\cos(\pi\phi_m) \to 2\cos(\pi\theta)$ as $m \to \infty$, we obtain following nested radical expansion:

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

Now take $x_2 = \theta$, then

$$\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}\\ $$ Aside from the extra rule of ignoring the leading $b_0$ in binary representation of $x_2 \veebar 2x_2$. This is your recipe of computing $\cos(x)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.