Converting a decimal into a fraction

Question

I have written a small program that converts a decimal number into a reduced fraction representation. I also designed this little program to be fairly robust, so that it can give the correct output for various inputs.

For example:

./a.out 3,000.375
24003/8
./a.out "3 000,375"
24003/8
./a.out 3.000,375
24003/8
./a.out 3000.375
24003/8

Here is the complete code for the program:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int isDigit(char);
void simplify(unsigned long long *, unsigned long long *);

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Please enter a number to fractionize.\n");
        return EXIT_FAILURE;
    }
    char *input = argv[1];
    int i;
    char c;
    unsigned long long previous, denominator = 1, numerator = 0;
    for (i = strlen(input) - 1; i >= 0; i--, denominator *= 10) {
        c = input[i];
        if (!isDigit(c)) {
            break;
        }
        previous = numerator;
        numerator = (c - '0') * denominator + numerator;
        if (previous > numerator) {
            return EXIT_FAILURE;
        }
    }
    if (c == '-' || isDigit(c)) {
        printf("%llu/1\n", numerator);
        return EXIT_SUCCESS;
    }
    simplify(&numerator, &denominator);
    int j, negative = 0;
    unsigned long long whole = 0;
    for (j = 0; j < i; j++) {
        char c = input[j];
        if (c == '-') {
            negative = 1;
        } else if (isDigit(c)) {
            previous = whole;
            whole = whole * 10 + (c - '0');
            if (previous > whole) {
                return EXIT_FAILURE;
            }
        }
    }
    previous = numerator;
    numerator += whole * denominator;
    if (previous > numerator) {
        return EXIT_FAILURE;
    }
    simplify(&numerator, &denominator);
    if (negative) {
        printf("-");
    }
    printf("%llu/%llu\n", numerator, denominator);
    return EXIT_SUCCESS;
}

int isDigit(char c) {
    return c >= '0' && c <= '9';
}

void simplify(unsigned long long *numerator, unsigned long long *denominator) {
    while (1) {
        if ((*numerator % 2 == 0) && (*denominator % 2 == 0)) {
            *numerator   /= 2;
            *denominator /= 2;
        } else if ((*numerator % 5 == 0) && (*denominator % 5 == 0)) {
            *numerator   /= 5;
            *denominator /= 5;
        } else {
            break;
        }
    }
}

My algorithm is basically to first process the number right to left. As soon as a non-digit is detected, the part of the input that has been processed is deemed the "fractional part". This fractional part is then simplified (when possible). For example "12.34" would be processed as 34 and 100, which would then be simplified to 17 and 50.

Then, the input is processed left to right up to the point where the first scan terminated. Any non-digit characters are ignored (except the minus sign), and digits are accumulated (12 in this case). This is deemed the "whole part".

Then, the whole part is multiplied by the (simplified) denominator and it is added to the (simplified) fractional part (in this case, the fraction would be 617 over 50). The fraction is then again simplified (when possible) and the result is printed out.

My main concern is how I handle overflow. Because I am using unsigned types, overflow would simply cause the number to wrap around towards 0, so I simply check if the number before the computation (stored in previous) is larger than the number after the computation. If it is, then overflow has occurred. This seems like a fairly naive way to do it, but it seems to work for the inputs that I have tried.

Otherwise, any stylistic or performance-related inputs are always appreciated.

Answer 1

I think you're being too lenient with your input checking, which results in some unexpected results:

-3,000,0 results in: -3000/1

3,000 results in: 3/1

3 results in 3/1

3-1 results in 1/1

Personally, I'd pick an expected format and then ensure that the input complies with it. If you want to support multiple decimal marks, then I would suggest having a function for each supported format that validates the input and returns it in one common format which is then used by the rest of the code.

argc & argv

In your example you have ./a.out "3 000,375". You're quoting the space in order to ensure it's all pushed as part of argv[1]. It seems likely that this could be forgotten. If it was, then you would end up with the output of 3/1. Your argc checking only checks for no parameters being supplied:

if (argc < 2) {
    fprintf(stderr, "Please enter a number to fractionize.\n");
    return EXIT_FAILURE;
}

Unless you're going to continue through the arguments supplied, appending them to the input it would be better to do something like this:

if (argc != 2) {
    fprintf(stderr, "Usage: %s <number to fractionize>\n", argv[0]);
    return EXIT_FAILURE;
}

One declaration per line

This is obviously subjective, but I don't particularly like multiple declarations on a single line. I don't mind it so much when you're declaring several uninitialised variables, however when you're assigning values to the variables it would be better to have each declaration on a new line. For me, denominator and previous get a bit lost on this line:

unsigned long long previous, denominator = 1, numerator = 0;

Answer 2

1. The simplify() works, but to offer a quick and more general approach, find the gcd() with Euclid's Algorithm. The following is not specialized for 2 and 5.

   unsigned long long gcd_ull(unsigned long long a, unsigned long long b) {
     while (b) {
       a %= b;
       if (a == 0) return b;
       b %= a;
     }
     return a;
   }
   
   void simplify(unsigned long long *num, unsigned long long *den) {
     unsigned long long gcd = gcd_ull(*num, *dem);
     if (gcd) {
       *num /= gcd;
       *dem /= gcd;
     }
   }
   

2. It's unclear why code uses unsigned long long. Use unsigned for quickness. Use uintmax_t for maximum width without resorting to more elaborate code.

3. Overflow protection: use basic overflow protection, to ensure that the math does not overflow. if (previous > whole) { approach will detect some overflow, but not all.

   // whole = whole * 10 + (c - '0');
   if (whole >= ULLONG_MAX/10 && 
       (whole > ULLONG_MAX/10 || (c-'0') > ULLONG_MAX%10)) {
     Overflow();
   } else {
     whole = whole * 10 + (c - '0');
   }
   

4. simplify() attempts /0 should *numerator == 0. Use #1

5. if (argc != 2) { would be a stronger test than argc < 2 to detect an unexpected parameter count.

6. Lack of overflow protection on denominator *= 10 which occurs when whole is large like 18446744073709551615 or input has lots of leading zeros like "0.000000000000000000001".

7. I recommend a new approach for a robust solution. In theory, select text input with 64 significant decimal digits could have a representable answer as a unsigned long long. TBD a good solution - which I suspect would be entirely text based.

Answer 3

Your use of descriptive variable names and function names is good.

Main is too long
Your main() function contains too much code which makes it difficult to maintain. You have code for at least 2 more functions in main(). Both of the for loops are good candidates for functions. A well written function performs one and only one action.

Define functions before use If you define your functions before you use them in main() you don't need these declarations at the top of the file.

int isDigit(char);
void simplify(unsigned long long *, unsigned long long *);

In the long run these definitions could be maintenance problems if you need to change the parameters to the functions. The way your code is written to add a parameter to a function you need to do it in 2 different locations. A good habit might be to make main() the last function in the file.

As your programs get more complex, you may have multiple files. You may want to reuse a function name in another file. To make you functions local only to the file:

static int isDigit(char) {
    return c >= '0' && c <= '9';
}
static void simplify(unsigned long long *, unsigned long long *)  {
    while (1) {
        if ((*numerator % 2 == 0) && (*denominator % 2 == 0)) {
            *numerator   /= 2;
            *denominator /= 2;
        } else if ((*numerator % 5 == 0) && (*denominator % 5 == 0)) {
            *numerator   /= 5;
            *denominator /= 5;
        } else {
            break;
        }
    }
}