Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > complexity of trigonometric functions

Reply
Thread Tools

complexity of trigonometric functions

 
 
Vladimir Jovic
Guest
Posts: n/a
 
      09-02-2010
Hello,

I have a piece of code that I am trying to optimize. It is nothing
special - just some calculations, including trigonometric functions
(bunch of multiplications with sin and cos here and there). My code
duplicates in some places, but that is ok.

The questions are :
How complex are sin and cos functions? Are they simple look up tables?
Or are they some super-complex calculations.
If translated to multiplication/addition, how many
multiplications/additions would one sin or cos involve?

I am well aware this is implementation dependant, but it is probably
done in very similar fashion.
 
Reply With Quote
 
 
 
 
Alf P. Steinbach /Usenet
Guest
Posts: n/a
 
      09-02-2010
* Vladimir Jovic, on 02.09.2010 10:22, asked an off-topic question:
> Hello,
>
> I have a piece of code that I am trying to optimize. It is nothing special -
> just some calculations, including trigonometric functions (bunch of
> multiplications with sin and cos here and there). My code duplicates in some
> places, but that is ok.
>
> The questions are :
> How complex are sin and cos functions? Are they simple look up tables? Or are
> they some super-complex calculations.


Depends on the implementation. <g>


> If translated to multiplication/addition, how many multiplications/additions
> would one sin or cos involve?


Not much. Look up the series in e.g. Wikipedia.


> I am well aware this is implementation dependant, but it is probably done in
> very similar fashion.


Most probably the standard lib's 'sin' and 'cos' are the ~fastest possible
general ones on your platform. However, usage patterns can mean that you can
optimize further for your particular application. For example, around zero
crossings 'sin' and 'cos' are almost linear, and can be done as linar
interpolation (that means, replaced by linear function like Ax+B).

The only reasonable general answer is to *measure*.

But please ask such general programming questions in e.g.
[comp.lang.programming], leaving this group for C++ specific questions -- even
if C++ folks generally know what they're talking about...


Cheers & hth.,

- Alf

--
blog at <url: http://alfps.wordpress.com>
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      09-02-2010
On 9/2/2010 4:34 AM, Alf P. Steinbach /Usenet wrote:
> [..]
> But please ask such general programming questions in e.g.
> [comp.lang.programming],


Just a nit pick, I believe Alf meant [comp.programming]. My server for
one doesn't have 'comp.LANG.programming'.

> leaving this group for C++ specific questions
> -- even if C++ folks generally know what they're talking about...


V
--
I do not respond to top-posted replies, please don't ask
 
Reply With Quote
 
Vladimir Jovic
Guest
Posts: n/a
 
      09-02-2010
Alf P. Steinbach /Usenet wrote:
> * Vladimir Jovic, on 02.09.2010 10:22, asked an off-topic question:
>
>> If translated to multiplication/addition, how many
>> multiplications/additions
>> would one sin or cos involve?

>
> Not much. Look up the series in e.g. Wikipedia.
>


>
> Most probably the standard lib's 'sin' and 'cos' are the ~fastest
> possible general ones on your platform. However, usage patterns can mean


I am using standard lib's sin and cos. Where should I look how many
element of the series is taken? Compiler's documentation?

> The only reasonable general answer is to *measure*.
>


Correct, but I thought someone might give an insight on what should I
expect.

> But please ask such general programming questions in e.g.
> [comp.lang.programming], leaving this group for C++ specific questions
> -- even if C++ folks generally know what they're talking about...
>


Ok, thanks (as Victor said it is comp.programming)

btw I just found this :
http://linux.die.net/man/3/sincos
It is an extension I can use, and it perfectly fits my need.
 
Reply With Quote
 
osmium
Guest
Posts: n/a
 
      09-02-2010
"Vladimir Jovic" wrote:

> I have a piece of code that I am trying to optimize. It is nothing
> special - just some calculations, including trigonometric functions (bunch
> of multiplications with sin and cos here and there). My code duplicates in
> some places, but that is ok.
>
> The questions are :
> How complex are sin and cos functions? Are they simple look up tables? Or
> are they some super-complex calculations.
> If translated to multiplication/addition, how many
> multiplications/additions would one sin or cos involve?
>
> I am well aware this is implementation dependant, but it is probably done
> in very similar fashion.


You can get an idea of where things were when the computer started becoming
so pervasive from the link, wander around a few pages in the vicinity -
there are page links at the top. There may have been enormous progress
since then; if the upcoming Pentium MarkVII (or whatever) had a sine
function, I would not be *really* astonished. Though I doubt it.

http://www.math.sfu.ca/~cbm/aands/page_76.htm


 
Reply With Quote
 
Francesco S. Carta
Guest
Posts: n/a
 
      09-02-2010
Vladimir Jovic <(E-Mail Removed)>, on 02/09/2010 16:26:09, wrote:

> Alf P. Steinbach /Usenet wrote:
>> * Vladimir Jovic, on 02.09.2010 10:22, asked an off-topic question:
>>
>>> If translated to multiplication/addition, how many
>>> multiplications/additions
>>> would one sin or cos involve?

>>
>> Not much. Look up the series in e.g. Wikipedia.
>>

>
>>
>> Most probably the standard lib's 'sin' and 'cos' are the ~fastest
>> possible general ones on your platform. However, usage patterns can mean

>
> I am using standard lib's sin and cos. Where should I look how many
> element of the series is taken? Compiler's documentation?


Yes. You might look at their implementations, but you might discover
that they resolve to some built-in feature that you cannot inspect (as
it seems to be the case with my implementation), so the documentation
would become the only source of information about this - well, also some
search on the Internet could play here.

--
FSC - http://userscripts.org/scripts/show/59948
http://fscode.altervista.org - http://sardinias.com
 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      09-02-2010
On Sep 2, 7:26*am, Vladimir Jovic <(E-Mail Removed)> wrote:

> I am using standard lib's sin and cos. Where should I look how many
> element of the series is taken? Compiler's documentation?


Who says it's even using a series? Maybe it's using your CPU's
FSIN instruction (or equivalent).

 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      09-02-2010
On Sep 2, 7:38*am, "osmium" <(E-Mail Removed)> wrote:

> You can get an idea of where things were when the computer started becoming
> so pervasive from the link, wander around a few pages in the vicinity -
> there are page links at the top. *There may have been enormous progress
> since then; if the upcoming Pentium MarkVII *(or whatever) had a sine
> function, I would not be *really* astonished. *Though I doubt it.


Intel chips have had an FSIN instruction since the '486, IIRC.
Acutally, it's
had it since the '387, but that was a separate coprocessor chip.


 
Reply With Quote
 
BGB / cr88192
Guest
Posts: n/a
 
      09-02-2010

"Vladimir Jovic" <(E-Mail Removed)> wrote in message
news:i5nmrg$nh7$(E-Mail Removed)...
> Hello,
>
> I have a piece of code that I am trying to optimize. It is nothing
> special - just some calculations, including trigonometric functions (bunch
> of multiplications with sin and cos here and there). My code duplicates in
> some places, but that is ok.
>
> The questions are :
> How complex are sin and cos functions? Are they simple look up tables? Or
> are they some super-complex calculations.
> If translated to multiplication/addition, how many
> multiplications/additions would one sin or cos involve?
>
> I am well aware this is implementation dependant, but it is probably done
> in very similar fashion.


on x86, and probably other major architectures, these functions are
essentially built right into the processor, and are typically fairly fast.

most of the 'slowness' one may experience with them (in some cases), is
actually due to things the compiler is doing, rather than the operations
themselves. for example, MSVC defaults to using fairly stupid/inefficient
implementations of the math functions, and their "optimization" is simply to
use less stupid implementations (typically excluding some special case
handling, usually for NaN, Inf, denormals, ...).

(one can also get a major speedup by writing their own ASM functions which
simply send the values directly to the processor and return the result, if
possibly slightly less "safe" at edge cases).


but, at least in a general-purpose floating-point sense, it is unlikely one
will be able to write much of anything faster than the built-in functions.

if using fixed point integer though, and willing to settle with a little
reduced accuracy, it is possible to replace them by a table, which is
typically a little faster, but this is more because conversions between
floats and integers tend to be expensive.

this usually involves either using a modified angle scheme (256 degrees in a
circle, ...), or doing a fixed-point multiply to get the angle into the
correct base, and masking it off to get the array index.

say, 20.12 fixed point scheme in radians(val).
i=(val*10420)>>8; //scale to be in a 256 degree system (0.8
fixed-multiply, result still 20.12)
i=(i>>&4095; //convert into 12 bit table index
ret=foo_sintab[i];


however, usually one avoids fixed point unless really needed, since with
most modern computers it is generally slower (as well as being less
accurate) than the use of floats, except in a few edge cases, such as
processing integer input data to integer output data, as would take place in
a video or audio codec, where often calucaltions such as the DCT or MDCT are
done with fixed point and lookup tables, ...

the main reason for use in codecs is because often otherwise a lot of time
would get used up in conversions between floating point and integer values,
....

or such...


 
Reply With Quote
 
BGB / cr88192
Guest
Posts: n/a
 
      09-02-2010

"red floyd" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
On Sep 2, 7:26 am, Vladimir Jovic <(E-Mail Removed)> wrote:

> I am using standard lib's sin and cos. Where should I look how many
> element of the series is taken? Compiler's documentation?


<--
Who says it's even using a series? Maybe it's using your CPU's
FSIN instruction (or equivalent).
-->

yes, this is what most compilers do for these functions (sin, cos, sqrt,
....).

using a series for these calculations (in a general case) would be a serious
waste of time (even if there were not direct CPU support).


about the only time I have used series for caculating these functions is
typically for things like their quaternion variants, since there is no other
good way to do this...

or such...


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
how to write vhdl code for 1-d trigonometric function rajeswari01 Hardware 0 10-20-2010 11:21 AM
java trigonometric solver Guntius.GIBLI@gmail.com Java 13 09-08-2006 12:56 PM
2.0 Controlling password complexity in Membership =?Utf-8?B?TW9yZ2FuIFJvZGVyaWNr?= ASP .Net 3 04-22-2005 12:23 AM
reducing complexity foldface@yahoo.co.uk ASP .Net 0 10-12-2004 01:05 PM
please help me in distinguish redefining functions, overloading functions and overriding functions. Xiangliang Meng C++ 1 06-21-2004 03:11 AM



Advertisments