1
$\begingroup$

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to write a pseudorandom number generator.

So now my task is to write a simple function F(seed,n) that will help me generate indices for the pseudorandom permutations of n elements. However, the function has to be extremely simple: My constraint is that I can only use the following operators: +,-,*,/,%, specifically, no address access, binary encoding, bits selection etc. - only arithmetic on numbers. That is fine, I went for linear congruental generators and implemented a (a*x+c)%m procedure.

As I started testing F(seed,2) it immediately went apparent that the results oscilate between zero and one with a period of two.

My problem is: how can I adjust F to avoid that behavior? Maybe I should generate the n-permutations in a different manner?

In practice, I am only interested in n=<32

$\endgroup$
0

1 Answer 1

3
$\begingroup$

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.