Is this function pure? (Random computation, deterministic result)

Question

A pure function is defined as a function that:

1. Returns the same value for the same arguments, and
2. Does not produce any side effects (mutation of non-local variables, I/O operations, etc.)

Consider a function that calculates the greatest common divisor of two positive integers by randomly sampling integers between 1 and the lowest of the two numbers, and determining if the sampled integer divides the two given integers. When all of the integers have been visited, the function returns the highest sampled integer. Assume the random number generator used is uniform.

Intuitively, it seems to me that this function is pure, despite its computation being non-deterministic. It produces the same value for the same arguments, and does not produce any side effects. The only possible "side effect" I can think of is there is the possibility of the computation going on forever, given a large enough input. Am I correct in labeling this function pure?

Answer 1

No, I don't think so.

As for random number generators, there are two possibilities:

1. It is a Pseudo-RNG. It means it has an N-bit state, and each time a new random number is generated, the state gets updated. So there is a side effect - a change in the RNG state.

2. A True random generator, which draws random bits from entropy source. Again, the pool will be drawn upon and might be exhausted - here is a sign of a non-pure function.