vendredi 21 octobre 2016

Non-repeating PRGN algorithm

I have been discussing with another member of a forum I participate the following algorithm which generates an array of non-repeating random numbers (the example is written in Fortran 95):

program test
implicit none

real :: x
integer :: i, aux
integer, dimension(100) :: y

do i=1,100
  call RANDOM_NUMBER(x)
  aux = int(3 * x) + 1 ! random number: 1, 2 or 3
  aux = aux + y(i-1) ! adding previous selected number
  y(i) = MOD(aux,4) ! mod 4 gives the final result: 0, 1, 2 or 3
  print*, y(i)
enddo

end program test

This other member of the forum proposed this algorithm as a solution to a challenge of how to output non-repeating numbers using a regular random number generator and a fixed amount of operations per loop (so for instance cycling when a random value is the same as the previous would not give a constant number of operations per loop).

His algorithm seems to work well, the results are uniformly distributed and there are no obvious patterns in any sub-strings of any in the output (I searched for sub-strings of sizes 2 to 5 and all behaved as expected). But what puzzles me in this solution is that the random number generator is outputting only three possible numbers (0, 1 or 2) and yet the whole algorithm outputs four possible results (0, 1, 2 or 3). How is this possible? I thought that mapping down the results of a PRGN could be done, but not mapping it up (e.g. if a PRGN produces numbers between 0 and 7, they can be mapped as 0-3 => 0 and 4-7 =>1, but a PRGN producing only 0's and 1's cannot produce results between 0-7 in a same loop – since one could obviously group three results in order to map 000 => 0, 001 => 1, ... 111 => 7).




Aucun commentaire:

Enregistrer un commentaire