Precalculate sin/cos tables?

[twinbee]

I thought of iths idea a while back, and just remembered it recently. Would it be practical to precalculate massive sin/cos tables, rather than simply removing the trig? Granted, we may need several megabytes of RAM to allow for fine precision, but for the higher powers at least (where the non-trig math can still get quite long) it may be worth it.

[David Makin]

I thought of iths idea a while back, and just remembered it recently. Would it be practical to precalculate massive sin/cos tables, rather than simply removing the trig? Granted, we may need several megabytes of RAM to allow for fine precision, but for the higher powers at least (where the non-trig math can still get quite long) it may be worth it.

I believe iq is using sincos tables in his GPU method.

[twinbee]

It makes one wonder why CPU/GPU manufacturers don't implement tables on the hardware directly (in addition to accurate calculation of trig functions). With RAM being so cheap, it could enhance FPU capabilities...

[cbuchner1]

Precalculated sine/cosines would likely lead to very bad limitations of how far you can zoom in.

On the GPUs the sine/cosines are so fast that it's absolutely not worthwhile to replace them with polynomials or texture lookups. iq stated the polynomial version wasn't any faster on his GPU.

[David Makin]

Precalculated sine/cosines would likely lead to very bad limitations of how far you can zoom in.

On the GPUs the sine/cosines are so fast that it's absolutely not worthwhile to replace them with polynomials or texture lookups. iq stated the polynomial version wasn't any faster on his GPU.

I was remembering this post:

http://www.fractalforums.com/3d-fractal-generation/true-3d-mandlebrot-type-fractal/msg8489/#msg8489

Including "This is disappointing, and might be related to the fact that probably the trig functions are partially implemented by little texture lookups which are fast".

I realise now that maybe he meant that's what the GPU does internally, rather than what he's doing in his own code

As for using full sincos texture tables IMHO if you only have float on the GPU and not double then I think that's more of an accuracy restriction than using tables.

[Buddhi]

I have some bad experience with very big tables with precalculated values. Sometimes it works slower than direct calculations by CPU because direct memory access is really slow when table is bigger than CPU cache. As I know read data from memory can take up to 200 CPU cycles. Another problem is translation form floating point number to address in table, because it needs additional calculations and converting from floating point format (sin or cos argument) to integer (address in array). In my opinion this method is only usable when you want to precalculate some results of complicated formulas which needs many operations in one step and has limited range of arguments.

[keldor314]

On the GPU, lookup tables are a big no-no, since the actual cache is quite small (only a few KB).  In addition, there is dedicated hardware for computing sin and cos which computes with 1/4th to 1/8th the throughput of basic arithmetic.  In fact, sin and cos are faster than division on current hardware (specifically, division is implemented by a reciprocal, which is performed by the same transcendental unit as performs sin or cos, followed by a multiplication.)!  Also, the transcendental units are fully parallel to the standard ALUs, which means that so long as you don't compute more than 1 sin or cos for every 4 or 8 instructions, you essentially get them for free.

[David Makin]

On the GPU, lookup tables are a big no-no, since the actual cache is quite small (only a few KB).  In addition, there is dedicated hardware for computing sin and cos which computes with 1/4th to 1/8th the throughput of basic arithmetic.  In fact, sin and cos are faster than division on current hardware (specifically, division is implemented by a reciprocal, which is performed by the same transcendental unit as performs sin or cos, followed by a multiplication.)!  Also, the transcendental units are fully parallel to the standard ALUs, which means that so long as you don't compute more than 1 sin or cos for every 4 or 8 instructions, you essentially get them for free.

Thanks for that, I'm surprised that handling large areas of data isn't more optimised on GPUs given how much texture handling they normally do

[keldor314]

Well, it is optimized.  GPUs have around 10x the memory bandwidth of CPUs.  It's just that they also have 100x the ALUs.  Thus, per ALU, GPUs only have around 1/10th the bandwidth of CPUs.