Actually, no, rejection sampling is far from the only way of proceeding. Unfortunately, considering that computers store all information as bits, and thus can only manipulate random bits of information, any algorithm to draw a uniform random variable of range $N$ will be infinite, if the binary base development of $N$ is infinite.

This theorem is a classical result by Knuth and Yao (1976), who developed the framework of DDG-trees (discrete distribution generating trees).

The methods exposed by Gilles are the typical sort of thing that has been done to mitigate the waste incurred by rejection, but of course if one can generate following Knuth and Yao's trees it is much, much more efficient - on average 96% of random bits are saved.

I have given more information on this in the following CStheory post.

Actually, no, rejection sampling is far from the only way of proceeding. Unfortunately, considering that computers store all information as bits, and thus can only manipulate random bits of information, any algorithm to draw a uniform random variable of range $N$ will be infinite, if the binary base development of $N$ is infinite.

This theorem is a classical result by Knuth and Yao (1976), who developed the framework of DDG-trees (discrete distribution generating trees).

The methods exposed by Gilles are the typical sort of thing that has been done to mitigate the waste incurred by rejection, but of course if one can generate following Knuth and Yao's trees it is much, much more efficient - on average 96% of random bits are saved.

I have given more information on this in the following CStheory post.