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$
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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.