1
$\begingroup$

I'm trying to take an algorithm from this page: http://mathforum.org/library/drmath/view/65653.html 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     x. 

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

  • 1
    It seems to be just the remainder of $m/n$. For example if $m=13$ and $n=3$, then $q=4$ and $b=1$.2012-03-01

1 Answers 1

3

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$.