2 ms·
To be fair, I don't think I went through as elaborate mathematical considerations as the writer of the article. But even he mentions that he immediately had a b
by Tichy 18y ago
To be fair, I don't think I went through as elaborate mathematical considerations as the writer of the article. But even he mentions that he immediately had a bad feeling about the wrong solution, simply because it is doing too much work.
The step for me was to move away from the stochastic problem and say "wait a minute, there is a random generator built into my computer already, how can I use it directly". Assuming a horde of mathematicians has already showed that the inbuilt random numbers generator is as good as possible, that way I avoid all the maths issues. And that is a step that seems reasonable to expect from a good programmer.
Edit: just read the Knuth Shuffle entry at wikipedia. Happy that I even reinvented the Knuth optimization myself ;-)