Sub.jam

Programming Pearls is a nice book on programming by Jon Bentley.

Some bugs

---

1. The first one is found by Joshua Bloch on binary search.

2. This one is for "outputing m sorted random ints in U[0,n)". Here is the code from the book's website.

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

/* sortedrand.cpp -- output m sorted random ints in U[0,n) */

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

int bigrand()
{    
    return RAND_MAX*rand() + rand();
}

int randint(int l, int u)
{    
    return l + bigrand() % (u-l+1);
}

void genknuth(int m, int n)
{
    for (int i = 0; i < n; i++)
        /* select m of remaining n-i */
        if ((bigrand() % (n-i)) < m) {
            cout << i << "\n";
            m--;
        }
}

void gensets(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    while (S.size() < m) {
        int t = bigrand() % n;
        S.insert(t);
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

void genshuf(int m, int n)
{
    int i, j;
    int *x = new int[n];
    for (i = 0; i < n; i++)
        x[i] = i;
    for (i = 0; i < m; i++) {
        j = randint(i, n-1);
        int t = x[i]; x[i] = x[j]; x[j] = t;
    }
    sort(x, x+m);
    for (i = 0; i < m; i++)
        cout << x[i] << "\n";
}

void genfloyd(int m, int n)
{
    set<int> S;
    set<int>::iterator i;
    for (int j = n-m; j < n; j++) {
        int t = bigrand() % (j+1);
        if (S.find(t) == S.end())
            S.insert(t); // t not in S
        else
            S.insert(j); // t in S
    }
    for (i = S.begin(); i != S.end(); ++i)
        cout << *i << "\n";
}

int main(int argc, char *argv[])
{
    int m = atoi(argv[1]);
    int n = atoi(argv[2]);
    //genknuth(m, n);
    gensets(m,n);
    return 0;
}

Note that I changed the algorithm used in main() function from genknuth to gensets (genknuth does not work neither).

I tested the program using

./sortedrand 10 100

Here is the output I got:

-97
-86
-70
-54
-44
-43
-25
11
89
91

I used gcc 4.2.3 in Debian to compile the program. The wrong output is due to the bigrand() function. The return value of this function is way over the size of an integer. So there is an integer overflow. I tested the value of RAND_MAX on my machine and it is 2^31-1 =2147483647. According to the GNU C Library Manul, in the GNU library, RAND_MAX is 2147483647, which is the largest signed integer representable in 32 bits. In other libraries, it may be as low as 32767. According to the book, bigrand() is a function that returns a large random integer (much larger than m and n). Then, how should we modify bigrand()?

NOTE:
According to this article,in order to generate a random integer in the range [0,M),

Do NOT use

y = rand() % M;

as this focuses on the lower bits of rand(). For linear congruential random number generators, which rand() often is, the lower bytes are much less random than the higher bytes. In fact the lowest bit cycles between 0 and 1. Thus rand() may cycle between even and odd (try it out). Note rand() does not have to be a linear congruential random number generator. It's perfectly permissible for it to be something better which does not have this problem.

instead, use

r = ( (double)rand() / ((double)(RAND_MAX)+(double)(1)) );
/* r is a random floating point value in the range [0,1) {including 0, not including 1}. Note we must convert rand() and/or RAND_MAX+1 to floating point values to avoid integer division. In addition, Sean Scanlon pointed out the possibility that RAND_MAX may be the largest positive integer the architecture can represent, so (RAND_MAX+1) may result in an overflow, or more likely the value will end up being the largest negative integer the architecture can represent, so to avoid this we convert RAND_MAX and 1 to doubles before adding. */
x = (r * M);
/* x is a random floating point value in the range [0,M) {including 0, not including M}. */
y = (int) x;
/* y is a random integer in the range [0,M) {including 0, not including M}. If M is an integer then the range is [0,M-1] {inclusive} */
z = y + 1;
/* z is a random integer in the range [1,M+1) {including 1, not including M+1}. If M is an integer then the range is [1,M] {inclusive} */

I also checked rand() manual page in Linux using "man -S 3 rand" and found the following

In Numerical Recipes in C: The Art of Scientific Computing (William H. Press, Brian P. Flannery, Saul A. Teukol-sky, William T. Vetterling; New York: Cambridge University Press, 1992 (2nd ed., p. 277)), the following comments are made:
"If you want to generate a random integer between 1 and 10, you should always do it by using high-order bits, as in

j = 1 + (int) (10.0 * (rand() / (RAND_MAX + 1.0)));

and never by anything resembling

j = 1 + (rand() % 10);

(which uses lower-order bits)."

Here is another discussion on random number generation.


NOTE: remember to initialize the random seed using srand(time(NULL));