Comment by ryao
1 year ago
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.
1 year ago
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.
3 replies →