I guess it's too late for a comment, but it here it is anyway:
1 You don't need to check for collision on every frame, doing this 10 times per second looks fine. Knowing start/end positions you can interpolate animation to any frame rate.
2 Use space subdivision and collision groups. For instance divide a game field into squares (or cubes) and only check for collision if both objects belong to same volume. Bullets group should collide with enemies group, but not within each-other. Biggest possible slowdown is checking each object with other. For N objects it yields N*(N-1)/2 complexity and doesn't scale well. The more space volumes you use - the more memory usage, but less collision computations.
3 Simple optimization for most functions is a lookup table with interpolation (linear as the simplest and cheapest to implement). Sacrifice memory for performance.
4 Adobe flash has a built-in collision detection functions (BitmapData HitTest) for visible objects which is pixel-based. Quite fast, especially for objects with complex geometry.
5 Square roots and trigonometric functions can be approximated via Taylor series
P.S. There was a time when I thought like described in the post, same questions and problems. Hope my comment would help somehow.
Knuckstrike
When I read all this I'm happy I'm making a simple bullet hell game for christmas in HTML5...