sin/cos implementation in fixed-point

Thanks Bhaskar.

Actually, I needed a break. I got tired of seeing people who hadn't
tried a problem coming to the regulars of this group for complete
solutions.

I did find a different job.  DSP for humanitarian landmine detection.
I actually get out in the field for once.

Dirk


"Bhaskar Thiagarajan" <bhaskart@my-deja.com> wrote in message news:<2loubjFfbr7lU1@uni-berlin.de>...
> Hi Dirk
> 
> Welcome back....haven't noticed your name here in a long time.
> Is the absence because you found new work and were ramping up?
> 
> Cheers
> Bhaskar
> 
> "Dirk Bell" <dirkman@erols.com> wrote in message
> news:6721a858.0407151847.f13136c@posting.google.com...
> > Hello,
> >
> > Consider having A) a coarsely-spaced table of equally-spaced (cos,sin)
> > values covering the entire circle, and B) a finely-spaced table of
> > equally-spaced (cos,sin) values only covering the coarse table
> > spacing. Then use the equations for cos(small+large), sin(small+large)
> > in terms of cos(large), sin(large), cos(small), and sin(small) to
> > compute cos(small+large) and sin(small+large) with 2 multiplies and 1
> > add each.
> >
> > With a 100-point 'coarse' table and a 100-point 'fine' table, you have
> > the equivalent of a 10000-point table (obviously tables do not need to
> > be equal size).
> >
> > Few instructions, few operations, little memory, simple addressing,
> > small numerical error. Additional simplifying tricks possible with a
> > little thought.
> >
> > Dirk A. Bell
> >
> >
> > axl_fugazi@yahoo.com (Pallav) wrote in message
>  news:<baaddb55.0407142104.58ebbd40@posting.google.com>...
> > > Hello,
> > >
> > > Here's my problem. I converted some code from floating-point to fixed
> > > point. Currently, for sin/cos/tan I'm using the floating point math.h
> > > functions. I have two base formats q.22 and q.28 that I use and play
> > > with.
> > >
> > > I was initially using 1024 values sin/cos tables (in q.28 format).
> > > However, I'm finding that this is not giving me good-enough precision.
> > > I'm getting abosolute differences of about 0.004-0.008 between the
> > > floating point sin/cos and the lookup tables. The alogrithm (I'm
> > > using) seems very sensitive and I'd like to achieve an absolute error
> > > of 0.000001 (10^-6) correct operaion. For such a precision, the lookup
> > > table seems out of the question because the code is going to run on a
> > > embedded processor with limited cache (8-16K).
> > >
> > > So what I'm thinking is maybe to get such a high precision, it may be
> > > possible to write sin/cosine as fixed-point functions (it will be
> > > slower than lookup but hopefully faster than floating point). I was
> > > looking at the implementation of such functions in glibc but couldn't
> > > exactly figure out what's going on in there (mix of assembly/C nasty
> > > stuff).
> > >
> > > One possible way is taylor series approximation. However, this won't
> > > work very well since in 32 bits, 10! (ie. 12 terms) will easily
> > > overflow.
> > >
> > > I'm sure many of you have come across this problem before in DSP
> > > applications. Since I'm not a DSP guy, I'm not familiar with
> > > solutions. Any of you have any ideas on what I can do? I was reading
> > > somewhere that continued fractions might work. Need to find out more
> > > about that. Any of you have any other approximation methods for
> > > sin/cos/tan that could be done in fixed-point (one can always have as
> > > many base formats as needed) to give the high accuracy that I'm
> > > seeking?
> > >
> > > I want to also avoid 64-bit because I plan to then implement parts of
> > > the algorithm in TIE, feed it to Xtensa to generate custom
> > > instructions. However, if 64-bit gives good precision, then I may just
> > > have to stick with it and incur the overhead of doing 64-bit
> > > operations on a 32-bit processor.
> > >
> > > I appreciate your advice/help.
> > >
> > > pallav

Someone wrote:

(snip)

>>Consider having A) a coarsely-spaced table of equally-spaced (cos,sin)
>>values covering the entire circle, and B) a finely-spaced table of
>>equally-spaced (cos,sin) values only covering the coarse table
>>spacing. Then use the equations for cos(small+large), sin(small+large)
>>in terms of cos(large), sin(large), cos(small), and sin(small) to
>>compute cos(small+large) and sin(small+large) with 2 multiplies and 1
>>add each.


I have a data book from many years ago with ROMs for sin/cos.
In the ones in the book I believe that the fine table is a linear
interpolation, and there are adders at the end, no multiplies.
(This is near the beginning of MOS ROMs, maybe 4K bits.)

If you have multiply hardware, polynomials might be the
best way, if not some form of interpolation is what I would try.
If you arrange the multiplies to be a power of two, then it
works out pretty nicely.

-- glen

Pallav wrote:

> Here's my problem. I converted some code from floating-point to fixed
> point. Currently, for sin/cos/tan I'm using the floating point math.h
> functions. I have two base formats q.22 and q.28 that I use and play
> with.

I always start by looking at the algorithms in Knuth's
"Metafont: The Program".    Those are the best fixed point
math functions that I know about.

-- glen

Dirk,
Good on you, just be careful where you tread in that field...
Cheers, Syms.
"Dirk Bell" <dirkman@erols.com> wrote in message
news:6721a858.0407170759.1f806647@posting.google.com...
>
> I did find a different job.  DSP for humanitarian landmine detection.
> I actually get out in the field for once.
>
> Dirk

"Dirk Bell" <dirkman@erols.com> wrote in message
news:6721a858.0407170759.1f806647@posting.google.com...
> Thanks Bhaskar.
>
> Actually, I needed a break. I got tired of seeing people who hadn't
> tried a problem coming to the regulars of this group for complete
> solutions.
>
> I did find a different job.  DSP for humanitarian landmine detection.

I thought they had this all figured out around WW-II time frame...I remember
seeing a show on Discovery (or similar) where they showed these huge tanks
with attachments in front (some guy specialized in designing these add-ons
to tanks). They basically flogged the ground ahead of the tank using various
means and set off the mines. I thought that was fairly humanitarian (except
for the tank and add-ons).

So tell us more about this interesting application (or is protected by a
million encryption algorithms?)

Cheers
Bhaskar



> I actually get out in the field for once.
>
> Dirk
>
>
> "Bhaskar Thiagarajan" <bhaskart@my-deja.com> wrote in message
news:<2loubjFfbr7lU1@uni-berlin.de>...
> > Hi Dirk
> >
> > Welcome back....haven't noticed your name here in a long time.
> > Is the absence because you found new work and were ramping up?
> >
> > Cheers
> > Bhaskar
> >
> > "Dirk Bell" <dirkman@erols.com> wrote in message
> > news:6721a858.0407151847.f13136c@posting.google.com...
> > > Hello,
> > >
> > > Consider having A) a coarsely-spaced table of equally-spaced (cos,sin)
> > > values covering the entire circle, and B) a finely-spaced table of
> > > equally-spaced (cos,sin) values only covering the coarse table
> > > spacing. Then use the equations for cos(small+large), sin(small+large)
> > > in terms of cos(large), sin(large), cos(small), and sin(small) to
> > > compute cos(small+large) and sin(small+large) with 2 multiplies and 1
> > > add each.
> > >
> > > With a 100-point 'coarse' table and a 100-point 'fine' table, you have
> > > the equivalent of a 10000-point table (obviously tables do not need to
> > > be equal size).
> > >
> > > Few instructions, few operations, little memory, simple addressing,
> > > small numerical error. Additional simplifying tricks possible with a
> > > little thought.
> > >
> > > Dirk A. Bell
> > >
> > >
> > > axl_fugazi@yahoo.com (Pallav) wrote in message
> >  news:<baaddb55.0407142104.58ebbd40@posting.google.com>...
> > > > Hello,
> > > >
> > > > Here's my problem. I converted some code from floating-point to
fixed
> > > > point. Currently, for sin/cos/tan I'm using the floating point
math.h
> > > > functions. I have two base formats q.22 and q.28 that I use and play
> > > > with.
> > > >
> > > > I was initially using 1024 values sin/cos tables (in q.28 format).
> > > > However, I'm finding that this is not giving me good-enough
precision.
> > > > I'm getting abosolute differences of about 0.004-0.008 between the
> > > > floating point sin/cos and the lookup tables. The alogrithm (I'm
> > > > using) seems very sensitive and I'd like to achieve an absolute
error
> > > > of 0.000001 (10^-6) correct operaion. For such a precision, the
lookup
> > > > table seems out of the question because the code is going to run on
a
> > > > embedded processor with limited cache (8-16K).
> > > >
> > > > So what I'm thinking is maybe to get such a high precision, it may
be
> > > > possible to write sin/cosine as fixed-point functions (it will be
> > > > slower than lookup but hopefully faster than floating point). I was
> > > > looking at the implementation of such functions in glibc but
couldn't
> > > > exactly figure out what's going on in there (mix of assembly/C nasty
> > > > stuff).
> > > >
> > > > One possible way is taylor series approximation. However, this won't
> > > > work very well since in 32 bits, 10! (ie. 12 terms) will easily
> > > > overflow.
> > > >
> > > > I'm sure many of you have come across this problem before in DSP
> > > > applications. Since I'm not a DSP guy, I'm not familiar with
> > > > solutions. Any of you have any ideas on what I can do? I was reading
> > > > somewhere that continued fractions might work. Need to find out more
> > > > about that. Any of you have any other approximation methods for
> > > > sin/cos/tan that could be done in fixed-point (one can always have
as
> > > > many base formats as needed) to give the high accuracy that I'm
> > > > seeking?
> > > >
> > > > I want to also avoid 64-bit because I plan to then implement parts
of
> > > > the algorithm in TIE, feed it to Xtensa to generate custom
> > > > instructions. However, if 64-bit gives good precision, then I may
just
> > > > have to stick with it and incur the overhead of doing 64-bit
> > > > operations on a 32-bit processor.
> > > >
> > > > I appreciate your advice/help.
> > > >
> > > > pallav

On 2004-07-17, Dirk Bell <dirkman@erols.com> wrote:
> Thanks Bhaskar.
>
> Actually, I needed a break. I got tired of seeing people who hadn't
> tried a problem coming to the regulars of this group for complete
> solutions.
>
> I did find a different job.  DSP for humanitarian landmine detection.
> I actually get out in the field for once.
>
> Dirk


That's cool!!!!!! 

I'm really excited by non-military uses of DSP!

There are currently 60-70 MILLION active landmines left in old war
zones after the troops went home (including Africa, Asia, Eastern
Europe, South America...).  Landmines kill and maim tens of thousands
of civilians per year. There are large machines that chew up the
ground to destroy the landmines but they are cost prohibitive for most
places as well as have application problems (they are huge, must be
transported, ground coverage necessary...).  In some places ground
still gets cleared by some poor soul in a padded, somewhat shielded
suit.  Some of the mines are about 2 (two) inches in diameter and
contain virtually no metal. It makes things difficult. There is
actually a lot of work being done (military, universities, private
firms) to develop effective means of detecting the landmines. The
company I work for makes a ground penetrating radar to 'see' the
mines.  The acquired data is processed using DSP and pattern
recognition techniques.

Dirk


"Bhaskar Thiagarajan" <bhaskart@my-deja.com> wrote in message news:<2m3cevFictupU1@uni-berlin.de>...
> "Dirk Bell" <dirkman@erols.com> wrote in message
> news:6721a858.0407170759.1f806647@posting.google.com...
> > Thanks Bhaskar.
> >
> > Actually, I needed a break. I got tired of seeing people who hadn't
> > tried a problem coming to the regulars of this group for complete
> > solutions.
> >
> > I did find a different job.  DSP for humanitarian landmine detection.
> 
> I thought they had this all figured out around WW-II time frame...I remember
> seeing a show on Discovery (or similar) where they showed these huge tanks
> with attachments in front (some guy specialized in designing these add-ons
> to tanks). They basically flogged the ground ahead of the tank using various
> means and set off the mines. I thought that was fairly humanitarian (except
> for the tank and add-ons).
> 
> So tell us more about this interesting application (or is protected by a
> million encryption algorithms?)
> 
> Cheers
> Bhaskar
> 
<snipped>

"Dirk Bell" <dirkman@erols.com> wrote in message
news:6721a858.0407200714.5b3d8508@posting.google.com...
> There are currently 60-70 MILLION active landmines left in old war
> zones after the troops went home (including Africa, Asia, Eastern
> Europe, South America...).  Landmines kill and maim tens of thousands
> of civilians per year. There are large machines that chew up the
> ground to destroy the landmines but they are cost prohibitive for most
> places as well as have application problems (they are huge, must be
> transported, ground coverage necessary...).  In some places ground
> still gets cleared by some poor soul in a padded, somewhat shielded
> suit.  Some of the mines are about 2 (two) inches in diameter and
> contain virtually no metal. It makes things difficult. There is
> actually a lot of work being done (military, universities, private
> firms) to develop effective means of detecting the landmines. The
> company I work for makes a ground penetrating radar to 'see' the
> mines.  The acquired data is processed using DSP and pattern
> recognition techniques.

'Ground penetrating radar'...now that seems to ring a (B)bell. Was there an
article on this in a recent IEEE spectrum or Signal Processing magazine?
I hope you are having fun with your new job - good luck.

Cheers
Bhaskar


>
> Dirk
>
>
> "Bhaskar Thiagarajan" <bhaskart@my-deja.com> wrote in message
news:<2m3cevFictupU1@uni-berlin.de>...
> > "Dirk Bell" <dirkman@erols.com> wrote in message
> > news:6721a858.0407170759.1f806647@posting.google.com...
> > > Thanks Bhaskar.
> > >
> > > Actually, I needed a break. I got tired of seeing people who hadn't
> > > tried a problem coming to the regulars of this group for complete
> > > solutions.
> > >
> > > I did find a different job.  DSP for humanitarian landmine detection.
> >
> > I thought they had this all figured out around WW-II time frame...I
remember
> > seeing a show on Discovery (or similar) where they showed these huge
tanks
> > with attachments in front (some guy specialized in designing these
add-ons
> > to tanks). They basically flogged the ground ahead of the tank using
various
> > means and set off the mines. I thought that was fairly humanitarian
(except
> > for the tank and add-ons).
> >
> > So tell us more about this interesting application (or is protected by a
> > million encryption algorithms?)
> >
> > Cheers
> > Bhaskar
> >
> <snipped>