Very cool. The summed frequency array was one of the ideas I implemented, though I shot myself in the foot after that part. I was so determined to squeeze every ounce of speed out that I constructed an array of length $sf[n], with $freq[i] elements with value i for each i. The lookup is O(1), which beats the pants off O(logn) and O(n). Unfortunately, my n actually is fairly large (~10,000), and I ran out of memory pretty quickly (even with 2GB/proc). The O(n) linear search over @sf was going to be my next attempt, but I'll certainly compare it to the binary search.
Yep, overall it's a typical speed/space tradeoff. Another benefit of the linear or binary traversal solutions is, your frequencies needn't be integers (well, assuming rand() works correctly with non-integers, that is).