What's the best way to return a random line in a text file using C?

Question

What's the best way to return a random line in a text file using C? It has to use the standard I/O library (<stdio.h>) because it's for Nintendo DS homebrew.

Clarifications:

• Using a header in the file to store the number of lines won't work for what I want to do.
• I want it to be as random as possible (the best being if each line has an equal probability of being chosen as every other line.)
• The file will never change while the program is being run. (It's the DS, so no multi-tasking.)

Answer 1

Read each line, and use a random number to choose whether to keep that line or ignore it. For the first line, you want odds of 1:1 to keep; for the second, you want odds of 1:2, etc.

count = 0;
while (fgets(line, length, stream) != NULL)
{
    count++;
    if ((rand() * count) / RAND_MAX == 0)
        strcpy(keptline, line);
}

I haven't verified that this has the proper random qualities, but it seems right at first glance.

---

It has been pointed out that integer overflow would quickly become a problem with the way the comparison is coded, and I had independently reached the same conclusion myself. There are probably many ways to fix it, but this is the first that comes to mind:

if ((rand() / (float)RAND_MAX) <= (1.0 / count))