Generating all rationals (C)

From LiteratePrograms

Other implementations: C | dc | Haskell | Python

This program generates a list of rational numbers. It is based on a common mathematical proof that the rational numbers are countable and the correctness of the program establishes this fact. In practice the rationals it can list is limited by the size of the int datatype, but it will at least output a prefix of the list of all rationals used by the mathematical proof.

Main implementation

The overall program looks like this:

<<generate rationals>>=
void generate_rationals() {
    unsigned int sum, numerator, denominator;
    printf("0\n");
    for(sum=2; sum < UINT_MAX; sum++) {
        generate all rationals whose numerator and denominator sum to sum
    }
}

For printf and UINT_MAX we need to include header files:

<<header files>>=
#include <stdio.h>
#include <limits.h>

In the central step, we generate all rationals whose numerator and denominator sum to sum, provided that they are in least terms, and along with ther negatives. We conventionally display numbers with a denominator of 1 as an integer:

<<generate all rationals whose numerator and denominator sum to sum>>=
for(numerator=1; numerator <= sum - 1; numerator++) {
    denominator = sum - numerator;
    if (denominator == 1)
        printf("%u\n-%u\n", numerator, numerator);
    else if (in_least_terms(numerator, denominator))
        printf("%u/%u\n-%u/%u\n", numerator, denominator, numerator, denominator);
}

To determine if the fraction is in least terms, we compute the greatest common denominator of the numerator and denominator, which should be 1, using the Euclidean algorithm:

<<in least terms verification>>=
#define in_least_terms(n,d) (gcd((n),(d)) == 1)
unsigned int gcd(unsigned int x, unsigned int y) {
    while (y != 0) {
        unsigned int t = y;
        y = x % y;
        x = t;
    }
    return x;
}

Test main

We can ad hoc test our implementation with this test main:

<<generate_rationals.c>>=
header files
in least terms verification
generate rationals
int main() {
    generate_rationals();
    return 0;
}

Here's the first few entries in the output:

0
1
-1
1/2
-1/2
2
-2
1/3
-1/3
3
-3
1/4
-1/4
2/3
-2/3
3/2
-3/2
4
-4
1/5
-1/5
5
-5
1/6
-1/6
2/5
-2/5
3/4
-3/4
4/3
-4/3
5/2
-5/2
6
-6
1/7
-1/7
3/5
-3/5
5/3
-5/3

Download code