Efficient generation of a von Mises-Fisher distribution

The von Mises-Fisher distribution is a probability distribution on the ($p-1$)-sphere. I'm interested in the efficient generation of this distribution for a relatively high dimension ($1000$ or greater) for application in a search step in a meta-heuristic.

¿Is there a numerical algorithm to efficiently generate such a distribution?

I'll be sampling a lot of vectors, so I'm more interested in efficiency that exactitude. I could use some approximation, or any other easily generated distribution that allows me to select a direction with a mean and a concentration parameter, similar to von Mises-Fisher.