Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am asked to create a pseudo-random number generator using the following algorithm:

The generator will generate every integer from 1 to N-1 exactly once

The algorithm for N=2^n

  • Initialize an integer R to be equal to 1 every time the tabling routine is called and then on each successive call for a random number:
  • set R=R*5
  • mask out all but the low-order n+2 bits of the product and place the result in R
  • set p=R/4

What does the algorithm mean when it says mask out all but the low order n+2 bits of the product?

share|improve this question

migrated from stackoverflow.com Jul 7 '11 at 18:01

This question came from our site for professional and enthusiast programmers.

2 Answers 2

Here is a worked example, using the Python interpreter to help with the binary conversion

>>> bin(1234567)
'0b100101101011010000111'

suppose n=4, then I need to mask all but the last 6 bits. Which should give

>>> n=4
>>> 0b000111
7

wikipedia's binary page has some information about bitwise operations. Here we are interested in the AND operation

>>> 1234567 & 0b111111
7

One way to arrive at this mask is to compute the number one larger (since it is a power of 2) and subtract one from it

>>> (1<<n+2)-1
63
>>> bin(63)
'0b111111'

(1<<n+2)-1 can be simplified to (4<<n)-1, but in this instance there is another way

>>> 1234567 % (4<<n)
7

I have replaced the bitwise AND(&) with modulus(%) which has the same effect of masking the lowest n+2 bits

modulus is slightly more work for the CPU than bitwise operations, so if best performance is essential you should use the bitwise method

share|improve this answer

for n = 1 you would mask the 3 least bits

assuming big endian you'd have this bit layout

128 64  32  16  8   4   2   1
X   X   X   X   X   O   O   O

O's would be the bits you wanted to keep and you'd use the bitwise and operator with the value 7 since you need the 4, 2, and 1 bits high in order to mask (bitwise AND) them. myProduct &= 0x07; // force all bits except the 3 least to be 0

share|improve this answer
    
But R is an integer no? what are the bits of an integer –  Ellipsis... Jul 6 '11 at 5:16
    
All data types are represented by a certain numbe of bytes wether it's an integer or a float or class. If a bit is 1 then it gets the value I set above it. So when you have the value 3 in an int you can think of the bits being 00000011 since you need the 2 and the 1 to make 3. This site goes into more detail: helpwithpcs.com/courses/binary-numbers.htm –  JohnKlehm Jul 6 '11 at 6:16
    
Essentially the "mask out" step translates to R &= Math.pow(2, n + 2); This code isn't quite right so don't just turn this in for your homework. I'm hoping by the time you figure out what is missing you'll not have needed my hint anyway :) –  JohnKlehm Jul 6 '11 at 6:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.