How can you generate a sine wave using integers only?

[intervoxel]

TL;DR

A recursive generator of a quadrature signal which fits exactly in a NxN grid, where N is a large power of two.

I need to recursively generate a quadrature signal which fits exactly into a grid NxN, where N is a large power of two.
After unsuccessful research, I decided to develop my own solution, starting from the waveguide-form oscillator taken from Pete Symons' book 'Digital wave generation, p. 100'.

\begin{gather}
\begin{bmatrix}\hat{ y_1}\\\hat{y_2}\end{bmatrix}
=
\begin{bmatrix}
k &k-1\\
k+1&k
\end{bmatrix}
\begin{bmatrix} y_1\\y_2\end{bmatrix}
\end{gather}
where $k=cos(\omega T)$.

This formula works perfectly when using floating point numbers.

In the case of the NxN grid, we have $\omega T=2\pi/N$, and the amplitude is $N/2$.
For $N>>1$, we have $k=N/2-1$.
The difference equations then become
\begin{gather}
\hat{ y_1}=\frac{2((N/2-1)y_1 - y_2)}{N}
\end{gather}
and
\begin{gather}
\hat{ y_2}=\frac{2((N-1)y_1 + (N/2-1)y_2))}{N}
\end{gather}
If we initialize $N=128$ and $y_1=N/2$, $y_2=0$, we get for the first iteration the values $\hat{y_1}=63$ and $\hat{y_2}=127$ (it was expected a low value!). That is, $y_2>N/2$.

What went wrong? Thank you for any help.

 

[mfb]

I don't know where k=N/2 - 1 comes from, but with k getting larger your numbers will get too large as well. This is true for floating point numbers as well.

 

[Svein]

Check out the digital differential analyzer (DDA) (https://en.wikipedia.org/wiki/Digital_differential_analyzer_(graphics_algorithm)).

 

[intervoxel]

Thank you for answering. DDA uses floats not pure integers.

 

[intervoxel]

I don't know where k=N/2 - 1 comes from, but with k getting larger your numbers will get too large as well. This is true for floating point numbers as well.

Of course the modified k grows, it is an integer constant.
The rationale for the modified expression for k is:
$$lim_{N\to\infty} \frac{N}{2}sin(2\pi/N)=\pi$$
$$sin^2\theta+cos^2\theta=1$$
$$\overline{k}=\sqrt{\frac{N^2}{4}-\pi^2}$$
for $N>>1$ we have
$$\sqrt{\frac{N^2}{4}-\pi^2}\approx \frac{N}{2}-1$$

 

[Svein]

Thank you for answering. DDA uses floats not pure integers.

From the Wikipedia article: "The DDA method can be implemented using floating-point or integer arithmetic. " I know that it is so, because a research institute I once worked for implemented a version using only digital logic chips back in the late 60's.

 

[intervoxel]

You are right, a DDA variation called Bresenheim algorithm for circles works with integers. Thank you.