sin/cos function vs lookup table

[LJ]

Hello people - I was wondering if I could have some opinions on an idea for an optimisation on the physics engine in Immersion.
Currently I rotate my objects with your bog standard z rotation matrix.  However this requires at the very least, a sin and a cos call.  These are _very_ expensive and I want to avoid them.  I have a couple of ideas on how to get round this.

One is to keep a lookup table of sins and cosines for each degree of rotation.   I realise it would give me a choppy sine/cos wave but i don't care really because there should't be any done with a resolution of smaller than one degree. 

So what i would like is opinions on is the speed of a lookup in a python dictionary vs. a sine, cosine and a *0.01745... call.

Thanks :mrgreen:


LJ


here is my current call for a 2D rotation about the Z axis

Code: [Select]

        ## |X| | cos(a) -sin(a) ||X|
        ## |Y| | sin(a) cos(a) ||Y|
        fRadians = fDegrees*0.0174532925
        fx = self.oForward.x
        fy = self.oForward.y
        c = math.cos(fRadians)
        s = math.sin(fRadians)
        x = c * fx - s * fy
        y = s * fx + c * fy
        self.oForward.x = x
        self.oForward.y = y


[RCgothic]

Even with a look up table, you should be able to interpolate to a finer resolution.It wouldn't produce absolutely perfect accuracy, but it would allow smooth rotation.

The impression I get in a quick search in google is that lookup + interpolation is pretty common. It wouldn't be common if it wasn't faster.

[MLeo]

As RCGothic said, lookup+interpolation is one of the faster results.
Some of the CPU specific assembly calls for sincos uses lookup tables.

IMO, I'm unsure if a python dictionary is the best choice for this.
Floating point issues could arise from the use of it. I mean, the look up could fail over this.

If you are going to do use degree's as the basis, then a d%360 lookup to a list (the [] variant, it seems more optimised for lookups) could be even faster.


Also, this is very interresting:
http://www.devmaster.net/forums/showthread.php?t=5784

Atleast, for C/C++, but it might also be applicable for Python, it doesn't beat speed for lookup (assuming you do integer lookups), but it's faster than a direct call to sincos and more accurate than a look up (I think).

[Defiant]

censored

[LJ]

Code: [Select]

c func: 2.864436s
lookup: 1.045019s
taylor: 6.341741s
same sorta thing over here   getting a good second's increase which is great.  Thankyou everyone! :mrgreen:

[wz]

A very fast method for both sin and cos computation is the one described in this document: http://www.dspguru.com/comp.dsp/tricks/alg/sincos.htm

HTH,

wz