Generating all rationals (C)

From LiteratePrograms
Jump to: navigation, search
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.

[edit] 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;
}

[edit] 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
hijacker
hijacker
hijacker
hijacker