# Sine Lookup Table with Linear Interpolation

Started by March 16, 2013
```Robert Baer wrote:

> glen herrmannsfeldt wrote:
>
>> In comp.dsp Robert Baer<robertbaer@localnet.com>  wrote:
>>
>> (snip, I wrote)
>>
>>>> See:
>>
>>
>>>> http://ia601506.us.archive.org/8/items/bitsavers_nationaldaMOSIntegratedCircuits_20716690/1972_National_MOS_Integrated_Circuits.pdf
>>>>
>>
>>
>>>> The description starts on page 273.
>>
>>
>> I just tried it, copy and paste from the above link, and it worked.
>>
>> You might be sure to use Adobe reader if that matters.
>>
>> Also, it is page 273 in the document, page 282 in the PDF.
>>
>> (snip)
>>
>>>    Problem with that..could see only front and back cover.
>>>    Different source perhaps?
>>
>>
>   The basic approach given there is very good; use of puny 4 or 5 digit
> tables is a major weakness: sqrt(2)/2 as 0.7071 is junk; CRC in the
> squares, cubes and roots section gives sqrt(2) as 1.414214 (6 digits)
> and sqrt(50) as 7.07168 (also 6 digits).
>   And if one needs more, use the Taylor series (for reasonably small
> angles) as it converges fast (Nth odd power and Nth odd factorial).
>   --or, use the FPU in the computer to get SIN and COS at the same time!
>
>   Reduction from 360 degrees helps:
>   "Split" 180 degrees: sin(-x)=-sin(x)
>   "Split" 90 degrees: sin(180-x)=sin(x)
>   "Split" 45 degrees: sin(90-x)=cos(x)
>   "Split" 22.5 degrees: (sqrt(0.5)*(cos(x)-sin(x))
>   Small angles requires less iterations for a given accuracy.

But, but, but, but,.... we work in radians!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Except maybe a carpenter!

Jamie

```
```On Mon, 18 Mar 2013 18:57:13 -0400, rickman <gnuarm@gmail.com> wrote:

>On 3/18/2013 2:10 PM, Jerry Avins wrote:
>> On 3/17/2013 6:35 PM, rickman wrote:
>>> On 3/17/2013 6:23 PM, langwadt@fonz.dk wrote:
>>>> On Mar 17, 10:56 pm, rickman<gnu...@gmail.com> wrote:
>>>>> On 3/16/2013 8:02 PM, langw...@fonz.dk wrote:
>>>>>
>>>>>> why not skip the lut and just do a full sine approximation
>>>>>
>>>>>> something like this, page 53-54
>>>>>
>>>>>>
>>>>>>
>>>>>
>>>>> I'm not sure this would be easier. The LUT an interpolation require a
>>>>> reasonable amount of logic. This requires raising X to the 5th power
>>>>> and five constant multiplies. My FPGA doesn't have multipliers and this
>>>>> may be too much for the poor little chip. I suppose I could do some of
>>>>> this with a LUT and linear interpolation... lol
>>>>>
>>>>
>>>> I see, I assumed you had an MCU (or fpga) with multipliers
>>>>
>>>> considered CORDIC?
>>>
>>> I should learn that. I know it has been used to good effect in FPGAs.
>>> Right now I am happy with the LUT, but I would like to learn more about
>>> CORDIC. Any useful referrences?
>>
>> http://www.andraka.com/files/crdcsrvy.pdf should be a good start. Do you
>> remember Ray Andraka?
>
>Yes, of course.  I should have thought of that.  I don't go to his site
>often, but his stuff is always excellent.  I may have even downloaded
>this paper before.  I took a look at the CORDIC once a few years ago and
>didn't get too far.  I'm happy with my current approach for the moment,
>but I will dig into this more another time.
>
>I appreciate the link.  Thanks Jerry.

If you just type "CORDIC FPGA" in Google it's the third link that
comes up.

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com
```
```In comp.dsp Robert Baer <robertbaer@localnet.com> wrote:

(snip)
>   I had used my "standard" 4.0 Acrobat; fails in that manner very
> reliably.   ver 7.0 works 100 percent; thanks.

For a long time (years) I was using 5.0 because it had some features
that later ones didn't. I had 8.0 for the cases where that failed, but
you can't run both at once. If you run another one, it just passes
the file to the first one.

Some time ago, I wrote a program to generate LZW compressed PDF
from scanned bitmaps as PDF 1.0 files. (Among other things, only
the usual 7 bit ASCII is allowed.)

Later, I wrote on for JBIG2 compression, which I believe is 1.2
(That is, Acrobat 3.0.)

But yes, many files require newer versions.

-- glen
```
```In comp.dsp Robert Baer <robertbaer@localnet.com> wrote:
>> (snip)

>>>    Problem with that..could see only front and back cover.

>   The basic approach given there is very good; use of puny 4 or 5 digit
> tables is a major weakness: sqrt(2)/2 as 0.7071 is junk; CRC in the
> squares, cubes and roots section gives sqrt(2) as 1.414214 (6 digits)
> and sqrt(50) as 7.07168 (also 6 digits).
>   And if one needs more, use the Taylor series (for reasonably small
> angles) as it converges fast (Nth odd power and Nth odd factorial).
>   --or, use the FPU in the computer to get SIN and COS at the same time!

But not so bad for 43 years ago!

That was close to the beginning of MOS mask ROMs. It requires a 12V
power supply, though the outputs are still TTL compatible, using
both -12V and +5V power supplies.

>   Reduction from 360 degrees helps:
>   "Split" 180 degrees: sin(-x)=-sin(x)
>   "Split" 90 degrees: sin(180-x)=sin(x)
>   "Split" 45 degrees: sin(90-x)=cos(x)
>   "Split" 22.5 degrees: (sqrt(0.5)*(cos(x)-sin(x))
>   Small angles requires less iterations for a given accuracy.

-- glen
```
```On 3/19/13 12:05 AM, glen herrmannsfeldt wrote:
...
>  It requires a 12V
> power supply, though the outputs are still TTL compatible, using
> both -12V and +5V power supplies.
>

my goodness we're old, glen.

--

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

```
```On Tue, 19 Mar 2013 00:18:35 -0400, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 3/19/13 12:05 AM, glen herrmannsfeldt wrote:
>...
>>  It requires a 12V
>> power supply, though the outputs are still TTL compatible, using
>> both -12V and +5V power supplies.
>>
>
>my goodness we're old, glen.

I'm glad it's just you guys.   ;)

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com
```
```On 3/19/13 12:21 AM, Eric Jacobsen wrote:
> On Tue, 19 Mar 2013 00:18:35 -0400, robert bristow-johnson
> <rbj@audioimagination.com>  wrote:
>
>> On 3/19/13 12:05 AM, glen herrmannsfeldt wrote:
>> ...
>>>   It requires a 12V
>>> power supply, though the outputs are still TTL compatible, using
>>> both -12V and +5V power supplies.
>>>
>>
>> my goodness we're old, glen.
>
> I'm glad it's just you guys.   ;)

what was that EPROM?  a 2716 or 2708 or something like that?

--

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

```
```On 3/18/13 1:40 PM, dbd wrote:
> On Monday, March 18, 2013 8:51:48 AM UTC-7, robert bristow-johnson wrote:
>> On 3/18/13 12:56 AM, dbd wrote:
>> ...
>>> For an approach with easier error estimation you could use the three table sine/cosine generator that implements the trig identities:
>>> Sum formulas for sine and cosine
>>>       sin(w + deltaw) = sin(w) * cos(deltaw) + cos(w) * sin(deltaw)
>>>       cos(w + deltaw) = cos(w) * cos(deltaw) &#2013266070; sin(w) * sin(deltaw)
>>>
>>> The tables required are:
>>> #1 one quadrant sin(w)/cos(w) table of 2^M entries
>> i don't understand what this table is for at all?  tan(w)?  what do you
>> do with it?
>
> That's one quadrant used for sine or cosine generation, the usual single lookup table.
>
>>> #2 sin(deltaw) table of 2^N entries
>>> #3 cos(deltaw) table of 2^N entries
>>> (#3 only if cosine is generated as well as sine)
>>
>> you need both tables, even if you only want to generate the sine, using
>> this method.
>
> Right you are. It is a three table method for either sine or cosine.

i still don't get it.  you only need a table or tables for the delta's.
#2 and #3.  i don't get what table #1 is about.

you start out with sin(w)=0 and cos(w)=1 and pick the sin(deltaw) and
cos(deltaw) outa 2 tables (or, if you're a teeny bit clever, a single
table), and then have at it with the recursion equations above.  i don't
see a 3 table method.

--

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

```
```On 2013-03-18, Eric Jacobsen <eric.jacobsen@ieee.org> wrote:
>
> He indicated that his target is an FPGA that has no multiplies.   This
> is the exact environment where the CORDIC excels.  LUTs can be
> expensive in FPGAs depending on the vendor and the device.

yeah, you're right, I looked at the code on the wikipedia page and it
was full of multiplies, but looking closer reveals they are all shifts
and sign changes.

--
&#9858;&#9859; 100% natural

--- news://freenews.netfront.net/ - complaints: news@netfront.net ---
```
```On Monday, March 18, 2013 9:44:51 PM UTC-7, robert bristow-johnson wrote:

sin(w + deltaw) = sin(w) * cos(deltaw) + cos(w) * sin(deltaw)
cos(w + deltaw) = cos(w) * cos(deltaw) &#2013266070; sin(w) * sin(deltaw)
by tables where:
#1 one quadrant sin(w) or cos(w) table of 2^M entries
#2 sin(deltaw) table of 2^N entries
#3 cos(deltaw) table of 2^N entries

> i still don't get it.  you only need a table or tables for the delta's.
>   #2 and #3.  i don't get what table #1 is about.

#1 is the simple sine or cosine lookup table used to generate sin(w) or cos(w) for 2^M values of w in pi/2 (and extended to 2*pi by symmetries)

>
> you start out with sin(w)=0 and cos(w)=1 and pick the sin(deltaw) and
> cos(deltaw) outa 2 tables (or, if you're a teeny bit clever, a single
> table), and then have at it with the recursion equations above.

There is no recursion in the equations.

Tables #2 and #3 represent values of sin(deltaw) and cos(deltaw) for 2^N values of deltaw in the interval between the first two values of w that address table #1, say the interval from 0.0 to 0.5*pi*((2^N)-1)/(2^(M+N)).

> r b-j

Dale B. Dalrymple
```