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.