Some Simple Gamma Variate Generators
R. C. H. Cheng, G. M. Feast · Journal of the Royal Statistical Society Series C (Applied Statistics) · 1979
SUMMARY Gamma variates with index a> 1 are produced by combining two adaptations of Kinderman and Monahan's technique for generating random variates by the use of the ratio of uniform variates. Expensive logarithmic/exponential evaluation is frequently avoided. The method is uniformly fast for all cc> 1, is compact and easy to program. KINDERMAN AND MONAHAN (1977) describe an interesting method for generating random variates which uses the ratio of uniform variates, and they apply it to various different distributions, but not to the gamma distribution. We give two particular versions of the method for generating gamma variates with density function f(x) = x e/-l P(cx). The two are complementary in that they are efficient over different ranges of ax but can readily be combined to give a composite algorithm that is consistently fast for all a> 1. In making comparisons we shall only consider those algorithms which are compact and easy to implement in machine independent languages like Fortran. Compact methods usually rely on a rejection technique whereby test variates are subject to trials for acceptance or rejection. Such techniques are well known (see, for example, Tadikamalla, 1978), and we do not give details here except to note that their speed depends on the average number of trials needed for each variate accepted, as well as on the amount of computation required per trial. The number of trials needed will not vary with machine, but the speed of calculation will vary; not only with machine, but also with compiler and its optimization level. The most time-consuming calculations are for the generation of random numbers and logarithmic/ exponential evaluations, but on some machines these operations are relatively fast. In the timings to be given later we try to give a reasonably complete picture by timing on two machines with rather different characteristics. The effort required to set up should also be borne in mind. These constants actually depend on ax, and if ax has to be varied frequently, then constant set-up time has to be taken into account in assessing the speed of variate generation. Of previously published algorithms no single one is uniformly best for all cx> 1. Roughly speaking they fall into two types. Firstly, there are those which are fast for small cx, but which slow as ax increases. Of these the most competitive are those of Atkinson (1977) and Tadikamalla (1978). Fishman's GF routine, described by Atkinson and Pearce (1976), is fastest if ax is very close to 1, but is outperformed even for values of ca as low as 1-5. Then there are those methods whose efficiency increases with a. These are preferable for large cx; the most competitive seem to be the GO method of Ahrens and Dieter (1974) and the GB method of Cheng (1977). The method XG of Best (1978) is not considered in detail as it is competitive only in the special case for which ax varies with each call, when it is slightly faster than GB. When ax is fixed, it is outperformed by GB. All the above methods except XG are limited in speed by requiring at least two logarithmic/exponential evaluations per trial.