Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

With this trick you can test while generating the random numbers and if you see both values, you can short circuit the generation of random numbers.


The input generation is outside the scope of this. Otherwise you could directly choose the output values with the apropriate distribution and just skip all the rest.

(Arguably, this criticism applies to exchanging random.randint for a numpy equivalent as well, since that doesn't optimize the solution but only how quickly the question is being generated.)


Iterating a precomputed list is a method of generating random numbers. It is used in the one time pad. Whether we iterate a precomputed list or use a pseudo random number generator, we can short circuit the random number generator using this trick. We cannot directly choose the output values, because then it would not be random.


They’re proposing choosing the output values randomly according to the distribution obtained by choosing input values uniformly at random for the original algorithm.


That removes the random element to this. The way that random numbers work is that it is possible (although unlikely) that the minimum and maximal values in the range will not be selected when generating the million random numbers. If you assume that they will always be selected and thus always return the same output, then your output will be wrong at least some of the time.


I don’t know how you got “always return the same output” from “choose the output randomly according to [a non-uniform] distribution”.




Consider applying for YC's Summer 2026 batch! Applications are open till May 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: