Sin() and Cos()

Does Blitz3D use a Sin() Cos() Lookup Table or Maths? Just curious...

Maths

@fredborg: Thanks for the prompt response.

How is this implemented exactly? Systemcall, Taylorrow, Cordic, ...

It's built into the hardware.

Sin and Cos are built into CPU's? Since when? I never got the memo!

Since when? Since the 386 I believe. And since the 486 as an integral part of the CPU (you had to use a coprocessor before that).

Well, at least for PowerPC (G4) i can't remember any Mnemonics for these. Might be a system call, a assembler function or a function out of a c-math-library but still how is it implemented there again?

Koriolis:
I did some research and I guess you're right, but in those days those functions of the FPU must have been slow because demo coders up until 1994 at least were still using lookup tables.

I made a lookup table in BlitzPLus and compared to using Sin and COS and there was basically no speed difference.

Depends on what you're doing, were you're doing it and were you're bottleneck is. For huge amounts it's still faster using a lookup table, if the table fits nicely into the cache.

You can see in this Sin() and Cos() are benchmarked:
http://www.blitzbasic.com/codearcs/codearcs.php?code=1998#comments

When I wrote this http://www.elliottproductions.co.uk/action.html and used a look-up table for the particle effects in Blitz Plus, it gave a big speed-up.

I guess it depends on the CPU you're using. Personally, I don't bother with LUTs, anymore.

@sswift:
Not saying otherwise, I was just responding to your genuine surprise of cos and sin being supported by the CPU. It's been true for a long time, even if back in the day it was pretty inefficient.

Using a LUT in the Sin() Cos() case will save CPU usage by 10 folds, if not more, for this task.

You're wrong. It depends entirely on the problem you're trying to solve. The only case a LUT is faster is in complex, functional algorithms. In almost any other case, out-of-order execution gives a much larger speed boost, and the trade of is not worth it.

This was true when Amiga's were considered fairly fast computers. These days, memory speed lags so far behind CPU speed that things that used to be only (sanely) possible using LUT's are now so limited by RAM access speed that it's faster to do the calculation.

It will always depend on the exact circumstances though, but as time progresses, those circumstances become rare indeed.

I recall when processors couldn't even divide one number by another, it was all done with functions. It was those days, more than anything that I can remember, where LUT's were often much faster.

FlameDuck & vinylpusher, I'm basing myself strictly on command benchmarks. If a Cos() command takes 20 times longer than retrieving a value from a table, then it's fairly safe to say that a LUT is at least 10 times faster in that case, no?

Cheers.

The problem is : how did you do the benchmark? Cache issues are very important. It's very easy in one little benchmark to have the whole table in the cache, but how will it behave in actual real life use? If the table is not entirely in cach when you access it, you'll most certainly have a higher speed hit than if you had just let the CPU compute the value.

So to say things simply, if you have a tiny speed critical loop where you constantly use Sin/Cos, then a LUT may still be a win as in the old days, but otherwise (if the code in interleaved with a bunch of other code) it's not so likely.

Funny how these sin()/cos() posts always spurs on a massive discussion :)

That's natural, we all know it will change the face of programming ;)

Fredbord:
Well they -are- trancendental, and you know how people get when they discuss religion.

I think it's more due to the case that you use these things more or less on a daily basis but you don't really know how it's done and what's the best and when you have nothing to do curiosity shows up.

Exactly! I wrote a program and didn't even have to benchmark, because using a table and pre-calc the game became much smoother. Pre-calculation gets more of an advantage the more complex the calculations. To be honest I was pre-calculating the result of Sin/Cos * a random amount - that is a real world example - not theory.

No. Your CPU, depending on make and model has several ALUs and FPUs - thus you cannot linearly extrapolate your data that way. If your sin takes 2 ns and your LUT takes one, it will take the same time to out-of-order execute the sin on 2 FPUs as it will to sequentially fetch 2 numbers from memory.

Well there's your problem. Your algorithm doesn't take advantage of parallelism. Sure if you insist on only utilizing 1/5th of your CPU speed, then yes - fetching from memory will be faster.

some peopla say, that its faster to do a lookup table in blitz. but its not faster, but slower. also you may only have a certain number of digits...

My program became smoother using just a table, and when I also pre-calculated the random factor (as previously mentioned) it became smoother still. That program runs it's logic 250 times to give smooth movement and to ensure it runs at the same speed on all computers - so pre-calculation really helps. I passed this code onto Grey Alien who seems to have had great success with it for his game framework - so agree or not some people like this method. Never got a thank-you for that btw Jake. :-P Just that you were now using the author's/Retro64's way of doing things (I gave him the author's name with the code). Jake has since made improvements to this very useful piece of code.

I'm quite happy with my algorithms, but am always willing to learn a better approach.

I once did quick Lissajous-line test in BlitzMax and it was noticeable faster with a lookup table.

Yes. I know. I even explained why. Understand however that the assumption that it will always be faster is incorrect. It is highly dependent on hardware and algorithm structure (more).