3 ms·
Imagine a scenario in which you need to generate a large number of samples based on a discrete random variable with a large number of outcomes n. If you had
by talaketu 15y ago
Imagine a scenario in which you need to generate a large number of samples based on a discrete random variable with a large number of outcomes n. If you had a library that implemented both algorithms, which should you use?
Are you skeptical that a domain for that scenario exists?
- mturmon 15y agoI'm just saying that n has to be very large before the O(1) asymptotics kick in, that is, for: c1 log(n) + c2 > c3 where, from what I can see, c3 >> c2 and c1 is low. And the setup time for the other algorithm is also greater (but, the same according to the O() measure). In answer to your rhetorical question: I'd benchmark both. But, I already implemented the simpler algorithm in existing code, and bottlenecks for problems of interest to me are elsewhere. Also, the more complex algorithm is more likely to have a bug -- which might be elusive, as they sometimes are with complex RNGs. I've found bugs in the published algorithms in DeVroye's book, for instance, and that book is considered authoritative. It's hard to convey just how subversive a parameter-dependent bug in a low-level RNG can be.