SIN and COS w/out coprocessor
Joseph Rose
I need to calculate the SIN and COS of an angle in MMX and on computers
without a math coprocessor, preferably in integers and based on a
gradient measure or where 64k=full circle in both a given and assumed
radius.
Mark Gibbs
Without the coprocessor? If you are designing for processors that don't
come with that built in math processors, you are probably designing for
older chips (ie, 386 and before). If that's the case, I would strongly
recommend a lookup table. I would offer code, but all I have is in 32-bits,
so I'd have to translate to 16 for older processors.
Let me know if you need it.
Indi
Joseph Rose
If it's integer-based or doesn't try to calculate using polynomials, could you
give me a copy of the code with comments? I can do the translations, and I
already have the polynomial-radian version of SIN.
Daniel M. Pfeffer
"Joseph Rose" <jor...@mail.gis.net> wrote in message
news:sf59ual...@corp.supernews.com...
How accurate must the value be? If it will only be used for plotting values,
try using a lookup table/polynomials for sin()/cos() of angles 0..45, and
doing some pre/post-processing to calculate sin()/cos() for any angle. This
is what you had to do in the bad old days before the FPU had a FSIN/FCOS
instructions.
For example, for sin(x):
0..45 = sin(x)
45..90 = cos(90-x)
90..135 = cos(x-90)
135..180 = sin(180-x)
180..225 = -sin(x-180)
225..270 = -cos(270-x)
270..315 = -cos(x-270)
315..360 = -sin(360-x)
Another option would be to use CORDIC algorithms for calculation of
sin()/cos(). These work only in a range of 0..(slightly over Pi/4), and give
you 1 bit/iteration. You then use the above relations to calculate sin(x)
for any angle.
DDJ had an article about CORDIC algorithms a few years back; I suggest that
you search their site for more information.
Daniel Pfeffer
Dr John Stockton
21:09:02 seen in news:comp.lang.asm.x86, Joseph Rose
<jor...@mail.gis.net> wrote:
>
>I need to calculate the SIN and COS of an angle in MMX and on computers
>without a math coprocessor, preferably in integers and based on a
>gradient measure or where 64k=full circle in both a given and assumed
>radius.
If you mean that literally, then sin is everywhere 0 except at 16k & 48k
where it is +1 & -1 ; or if the nearest value will do ...
More probably, it must depend on how many values you want. If only a
few, then calculate each, perhaps as below; if many, populate a look-up
table. A table need only have 16k+1 entries, as it is easy to transform
the argument of sin & cos of a 16-bit circle into that range of sin.
You could populate a table before assemble-time, using a HLL routine
along the lines of
for J := 0 to $4000 do Writeln(^I'dw'^I,
Round(30000*sin(2*Pi*J/$10000))) ;
or you could populate it at run-time starting from the known values of
sin and cos at 0, 90, ... degrees and using the half-angle formulae
cos A = sqrt((1+cos(2A))/2)
sin A = sqrt((1-cos(2A))/2)
to successively split the gaps (I'd expect that to give fairly good
results, at least). Perhaps start by building a temporary square-root
table.
--
© John Stockton, Surrey, UK. j...@merlyn.demon.co.uk / JR.St...@physics.org ©
Web <URL: http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct 4-line sig. separator is as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)
Joseph Rose
> Joseph Rose wrote:
> >
> > I need to calculate the SIN and COS of an angle in MMX and on computers
> > without a math coprocessor, preferably in integers and based on a
> > gradient measure or where 64k=full circle in both a given and assumed
> > radius.
> >
> Strange, I thought all MMX-enabled processors also had a FPU ...?
>
Unfortunately, MMX uses the FPU registers, so it's either use MMX or
calculate with floating-point.
Joseph Rose
> How accurate must the value be? If it will only be used for plotting values,
Accurate enough to draw good circles and gradient fills on VGA and SVGA. I'd
say 16-bit is enough....
>
> try using a lookup table/polynomials for sin()/cos() of angles 0..45, and
> doing some pre/post-processing to calculate sin()/cos() for any angle. This
> is what you had to do in the bad old days before the FPU had a FSIN/FCOS
> instructions.
I have the polynomial/radian method for SIN and COS (SIN x=x-x^3/3!+x^5/5!-...),
but I don't have a method for degrees/gradients or integers. I might use a
look-up table, but how do I do that in MMX where each byte represents a
different pixel with a slightly different value in the gradient.
>
>
> For example, for sin(x):
>
> 0..45 = sin(x)
> 45..90 = cos(90-x)
> 90..135 = cos(x-90)
> 135..180 = sin(180-x)
> 180..225 = -sin(x-180)
> 225..270 = -cos(270-x)
> 270..315 = -cos(x-270)
> 315..360 = -sin(360-x)
>
> Another option would be to use CORDIC algorithms for calculation of
> sin()/cos(). These work only in a range of 0..(slightly over Pi/4), and give
> you 1 bit/iteration. You then use the above relations to calculate sin(x)
> for any angle.
I don't like what I hear about that method. Are there any others?
>
> DDJ had an article about CORDIC algorithms a few years back; I suggest that
> you search their site for more information.
What's the URL? 1 bit/iteration won't be that bad on 8-bit and 16-bit values.
>
> Daniel Pfeffer
>
>
. == -|-=-
|\_/| ; ----/ -= -
/ .-=| \[/ - -=|-\=--=
| ..-==\ --==+==-- --=-|=|- -=
/ .---==\ /[\ =- /==-==-
/ ..---===\ ; =-|- -\--
--__----__--- . | - |
```` ` / \
Robert Redelmeier
> How accurate must the value be? If it will only be used for plotting values,
Dare I mention it? For small x [in radians], sin(x)=x, cos(x)=1
(or sqrt(1-x^2) if you must). This simplification is pretty good
for angles less than 0.1 radians (5.7 degrees),
-- Robert
Joseph Rose
Dr John Stockton wrote:
> JRS: In article <sf4gne...@corp.supernews.com> of Mon, 10 Apr 2000
> 21:09:02 seen in news:comp.lang.asm.x86, Joseph Rose
> <jor...@mail.gis.net> wrote:
> >
> >I need to calculate the SIN and COS of an angle in MMX and on computers
> >without a math coprocessor, preferably in integers and based on a
> >gradient measure or where 64k=full circle in both a given and assumed
> >radius.
>
> If you mean that literally, then sin is everywhere 0 except at 16k & 48k
> where it is +1 & -1 ; or if the nearest value will do ...
>
I need a constant scale range (i.e. -1k to 1k, and I'll multiply and ignore the
lower 10 bits) or a given variable range -radius to +radius.
>
> More probably, it must depend on how many values you want. If only a
> few, then calculate each, perhaps as below; if many, populate a look-up
> table. A table need only have 16k+1 entries, as it is easy to transform
> the argument of sin & cos of a 16-bit circle into that range of sin.
>
> You could populate a table before assemble-time, using a HLL routine
> along the lines of
> for J := 0 to $4000 do Writeln(^I'dw'^I,
> Round(30000*sin(2*Pi*J/$10000))) ;
> or you could populate it at run-time starting from the known values of
> sin and cos at 0, 90, ... degrees and using the half-angle formulae
> cos A = sqrt((1+cos(2A))/2)
> sin A = sqrt((1-cos(2A))/2)
> to successively split the gaps (I'd expect that to give fairly good
> results, at least). Perhaps start by building a temporary square-root
> table.
>
I'll create the table if necessary at run-time, but there might be a quick way to
do actual integer SIN and COS, especially on MMX, which for all I know can't use
look-up tables, and old computers which don't have the memory to hold a table.
Daniel M. Pfeffer
> "Daniel M. Pfeffer" wrote:
[snip]
> > Another option would be to use CORDIC algorithms for calculation of
> > sin()/cos(). These work only in a range of 0..(slightly over Pi/4), and
give
> > you 1 bit/iteration. You then use the above relations to calculate
sin(x)
> > for any angle.
>
> I don't like what I hear about that method. Are there any others?
>
> >
> > DDJ had an article about CORDIC algorithms a few years back; I suggest
that
> > you search their site for more information.
>
> What's the URL? 1 bit/iteration won't be that bad on 8-bit and 16-bit
values.
I looked in the Dr. Dobbs Journal (DDJ) site (http://www.ddj.com), but
unfortunately - the article is only present on their CD-ROM of old articles.
FWIW, the article was published in the October '90 issue. You can order the
CD-ROM from their site. It contains all of their articles, code etc. since
January 1988.
I found another article, which describes the application of CORDIC
algorithms to calculating sin(x), cos(x):
http://www.ezcomm.com/~cyliax/Articles/RobNav/sidebar.html
Daniel Pfeffer
Dr John Stockton
JRS: In article <8d0l5p$bvf$1...@bob.news.rcn.net> of Wed, 12 Apr 2000
01:57:13 seen in news:comp.lang.asm.x86, Joseph Rose
<jor...@mail.gis.net> wrote:
>Accurate enough to draw good circles and gradient fills on VGA and SVGA. I'd
>say 16-bit is enough....
For drawing circles, Bresenham's algorithm may be best. It has been
well described in a news posting somewhere earlier this week, which is
more or less AFAIR a copy of
From: "Hayden Rosser" <siko...@nospam.yahoo.com>
Newsgroups: comp.lang.asm.x86
Subject: Re: circle
Date: Wed, 12 Jan 2000 05:23:55 GMT
Message-ID: <s7o3vb...@corp.supernews.com>
Lines: 75
citing <A HREF="http://www.qzx.com/pc-gpe/">PCGPE</A>.
--
© John Stockton, Surrey, UK. j...@merlyn.demon.co.uk Turnpike v4.00 MIME. ©
<URL: http://www.merlyn.demon.co.uk/> TP/BP/Delphi/&c., FAQqy topics & links;
<URL: ftp://garbo.uwasa.fi/pc/link/tsfaqp.zip> Timo Salmi's Turbo Pascal FAQ;
<URL: http://www.merlyn.demon.co.uk/clpb-faq.txt> Pedt Scragg: c.l.p.b. mFAQ.
Indiana Jones
Joseph Rose wrote:
> If it's integer-based or doesn't try to calculate using polynomials, could you
> give me a copy of the code with comments? I can do the translations, and I
> already have the polynomial-radian version of SIN.
It could be integer based, and it doesn't calculate anything using anything. All
it does is take the x in sin(x), and read a table of values like:
x | sin(x)
-----------
0 | 0
5 | 0.087
10 | 0.174
15 | 0.259
: | :
90 | 1
The values of sin(x) can be as accurate or as inaccurate as you like - they can
even be integers (if you want sin(x)*10000, or fixed point values). Still
interested? Let me know and I'll dig it up.
Indi
DR....@dos.edu
In article <sf80bse...@corp.supernews.com>, Joseph says...
>I'll create the table if necessary at run-time, but there might be a quick way
>to
>do actual integer SIN and COS, especially on MMX, which for all I know can't use
>look-up tables, and old computers which don't have the memory to hold a table.
Memory can be traded for execution speed.
Use a look-up table combined with interpolation.
SIN and COS have fairly small second derivatives so you
don't need many points if you are willing to pay the
execution cost of interpolation.
Terje Mathisen
This is a very good suggestion, it is a special case of the approach
used by most modern mathlibs:
Use a polynomial approximation between known points on the function,
with a table lookup to determine the starting point(s) and the
approximation to be used.
In the simplest case, this is just a linear interpolation, i.e.:
isin(int x) /* 0 <= x <= 64K */
{
int x0, x1, s0, s1, s;
x0 = x >> 12; /* Use a 17-entry lookup table */
x &= 0xfff; /* Remainder, used for interpolation */
s0 = isin_tab[x0]; /* Scaled integer sin value */
s1 = isin_tab[x0+1]; /* Next table entry */
s = s0 * x + s1 * (0x1000 - x);
return (s >> SCALE_FACTOR);
}
Using MMX, the two table lookups, the multiplies and add, and the
scaling at the end can probably be done in about 6 cycles, so something
like 10 cycles total should be doable.
Terje
--
- <Terje.M...@hda.hydro.com>
Using self-discipline, see http://www.eiffel.com/discipline
"almost all programming can be viewed as an exercise in caching"
Dr John Stockton
04:54:20 seen in news:comp.lang.asm.x86, Joseph Rose
<jor...@mail.gis.net> wrote:
>> You could populate a table before assemble-time, using a HLL routine
>> along the lines of
>> for J := 0 to $4000 do Writeln(^I'dw'^I,
>> Round(30000*sin(2*Pi*J/$10000))) ;
>> or you could populate it at run-time starting from the known values of
>> sin and cos at 0, 90, ... degrees and using the half-angle formulae
>> cos A = sqrt((1+cos(2A))/2)
>> sin A = sqrt((1-cos(2A))/2)
>> to successively split the gaps (I'd expect that to give fairly good
>> results, at least). Perhaps start by building a temporary square-root
>> table.
>>
>
>to
>do actual integer SIN and COS, especially on MMX, which for all I know can't use
>look-up tables, and old computers which don't have the memory to hold a table.
The formulae I quoted are valid, but not, alas, the ones you really
want.
use sin((A+B)/2) = (sin(A)+sin(B))/(2*cos((A-B)/2))
for the first quadrant of sin; only a few values of the divisor are
needed, and can be obtained from the earlier formulae.
You might also look into the possibility of making a table of
sin((2^-n)*90) for n=0..?10, decomposing the angle into binary
fractions, and using the sin(A+B) formula.
Alternatively, depending on your purpose, it might be possible to use
Bresenham's circle-drawing algorithm as a foundation; AIUI, it's
somewhere in http://www.qzx.com/pc-gpe/
Joseph Rose
gradients, so I need general information.
Terje Mathisen wrote:
> DR....@DOS.EDU wrote:
> >
> > In article <sf80bse...@corp.supernews.com>, Joseph says...
> >
> > >I'll create the table if necessary at run-time, but there might be a quick way
> > >to
> > >do actual integer SIN and COS, especially on MMX, which for all I know can't use
> > >look-up tables, and old computers which don't have the memory to hold a table.
> >