Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to take an algorithm from this page: and convert it to working code. The step-by-step is as follows:

The following algorithm uses a similar (but slightly different) idea. It uses two internal integer variables, m and r, which are not reset at the beginning of the algorithm (in C, you would declare them as "static"). Initially, m = 1 and r = 0. We also have a parameter N, which is a large integer such that 2N can still be represented exactly in the computer. As said before, n is the modulus of the numbers you want to produce (they will be between 0 and (n - 1)), we must have n < N, and we have a function NextBit() that returns a truly random bit.

1. WHILE m < N DO r : = 2*r + NextBit(); m = 2*m; (r is a random
   variable of modulus m)
2. Divide m by n : m = n*q + b
3. IF r >= n*q, let m : = m - n*q, r : = r - n*q (r is still a random
   variable of modulus m), and go to step 1.
4. Otherwise, let x : = r mod n, r : = [r/n], and m : = q, and return 

However, I can't find any indication of what "b" is. Math expert, I am not.

share|cite|improve this question
It seems to be just the remainder of $m/n$. For example if $m=13$ and $n=3$, then $q=4$ and $b=1$. – David Mitra Mar 1 '12 at 17:39

1 Answer 1

As noted by David Mitra in the comments. $b$ denotes the remainder. The Division Algorithm theorem states that the division of integers produces a quotient and a remainder. That is, given a numerator $m$, and a denominator $n$, the division $m / n$ results in a quotient $q$ and a remainder $b$. Or, $$ m = qn + b. $$ In a programming setting, you can obtain $b$ using rem operation on $(m,n)$ if your language has one. Otherwise, you can always divide $m/n$, round down the results to get $q$, then $b$ is given by $b = m-qn$.

share|cite|improve this answer

Your Answer


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

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