[Sesse__]

> At least I think sqrt, sin, and cos are generally considered to be slow. […] Based on X you can calculate a range of legal Y that will still fall within the circle.

Yup, that calculation is called sqrt(1 - x²).

> Try to use a lookup table+interpolation with desired resolution to make this really fast

On modern hardware (like, most architectures from 1995-ish onwards), LUTs are mostly slower than polynomial-based solutions for the same level of accuracy.

> 1. Generate random X [-1 to 1]

As others have pointed out, this is already wrong unless you intend to reject some of the solutions later.