# Generating all rationals (C)

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>>=voidgenerate_rationals(){unsignedintsum, 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);elseif(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)unsignedintgcd(unsignedintx,unsignedinty){while(y != 0){unsignedintt = y; y = x % y; x = t;}returnx;}

## [edit] Test main

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

<<generate_rationals.c>>=header files in least terms verification generate rationalsintmain(){generate_rationals();return0;}

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 |