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?
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. To be honest I was pre-calculating the result of Sin/Cos * a random amount - that is a real world example - not theory.
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.