How many bullets are you talking about? I've got loads of sin/cos calcs going with loads of bullet and particle calculations with no problems... Of course, the sin/cos is just used once to get the initial deltas (in fixed float) for the animation.
Of course, I'm talking about dozens of calculations, not hundreds or thousands...
It sounds like you may be spending a lot of time for nothing.
