5
\$\begingroup\$

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.

\$\endgroup\$

3 Answers 3

7
\$\begingroup\$

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;
\$\endgroup\$
1
  • \$\begingroup\$ Regarding the quoting problem: I'd just pass the input via stdin. This I think is far easier and more logic. \$\endgroup\$
    – ljrk
    Jul 9, 2016 at 8:07
6
\$\begingroup\$
  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.

\$\endgroup\$
3
\$\begingroup\$

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;
        }
    }
}
\$\endgroup\$
7
  • 2
    \$\begingroup\$ I'd recommend using uint64_t from stdint.h instead of writing out unsigned long long. Shorter yet same (if not more) meaning. \$\endgroup\$
    – syb0rg
    Jul 8, 2016 at 18:09
  • \$\begingroup\$ Can you clarify your last comment, checking against primes? Since the denominator is always a multiple of ten, its only prime factors will be 2 and/or 5. How can I improve that code by checking "against the first twenty primes"? \$\endgroup\$ Jul 8, 2016 at 18:19
  • \$\begingroup\$ @MartinTuskevicius I have removed that part of my answer. You're correct it will always be a multiple of 10. \$\endgroup\$
    – pacmaninbw
    Jul 8, 2016 at 18:41
  • 1
    \$\begingroup\$ I don't agree that main() should be the last function -- this is personal preference imho. I prefer to be structure my code the way that I can read it from top to bottom, just like a book. \$\endgroup\$
    – ljrk
    Jul 9, 2016 at 8:05
  • 1
    \$\begingroup\$ @syb0rg Concerning old machines using non-2's complement (uncommon but not non-existent) may be C11 compliant. "uintN_t ... These types are optional." on such machines. See C11dr §7.20.1.1 for greater detail. \$\endgroup\$ Jul 11, 2016 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.