2
\$\begingroup\$

As part of a (slightly) larger program, I needed to write a function that could take an arbitrarily large number and divide it by a small number. In this program, I will be dividing this number specifically by 2 or 5, but from my (rudimentary) testing, my function seems to work for larger divisors as well. All of the inputs in this function will be valid (they are checked before passed to this function in a different part of the program). A valid input is a non-negative, properly-represented number, things like: "123\0" but not "-1000\0" or "00100\0". So input validation is not necessarily to that extent.

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

static inline int toNumber(char c) {
    return c - '0';
}

static inline char toCharacter(int n) {
    return n + '0';
}

char *divide(char *a, unsigned int divisor) {
    int length = strlen(a);
    char *quotient = malloc(length + 1);
    if (quotient == NULL) {
        return NULL;
    }
    int i, j;
    int localDivident = 0;
    for (i = 0, j = 0; i < length; i++) {
        if (a[i] == '0' && localDivident == 0) {
            quotient[j++] = '0';
        } else {
            if (localDivident != 0) {
                localDivident = localDivident * 10 + toNumber(a[i]);
            } else {
                localDivident = toNumber(a[i]);
            }
            int localQuotient = localDivident / divisor;
            if (localQuotient > 0) {
                quotient[j++] = toCharacter(localQuotient);
                localDivident -= localQuotient * divisor;
            }
        }
    }
    quotient[j++] = '\0';
    char *resized = realloc(quotient, j);
    return (resized == NULL) ? quotient : resized;
}

I have tested a variety of inputs and I have found that this function works surprisingly well, especially since I initially designed it with the intention of only handling single-digit divisors. However, I have found that it returns "\0" when the divisor is greater than the numeric interpretation of the input string. For example, divide("8\0", 9) returns "\0". One possible solution is adding a basic check like:

if (strtol(a, NULL, 10) < divisor) {
    char *trivialQuotient = malloc(2);
    if (trivialQuotient == NULL) {
        return NULL;
    }
    trivialQuotient[0] = '0';
    trivialQuotient[1] = '\0';
    return trivialQuotient;
}

But I find this solution inelegant, especially since the added computation of strtol will be pointless for the vast majority of executions, and I feel that there is a more elegant way for my algorithm to account for this scenario. I know that the line:

if (localQuotient > 0) {

is responsible for the result, but I could not think of a good way to modify it.

Also, I am torn between replacing the use of the static inlined functions like toNumber with a simple macro, like:

#define CTON(X) ((X) - '0')

I have read that the compiler may not always inline functions that are attributed with the inline modifier, and I know that the function should be inlined, which is why I am considering just using the macro.

(Also, I am aware that this function returns memory allocated using malloc which means that callers need to eventually free it.)

\$\endgroup\$
4
\$\begingroup\$

Bug

Given the input 91 and dividing by 9, your program gives 1 as the answer instead of 10. The problem is here:

        int localQuotient = localDivident / divisor;
        if (localQuotient > 0) {
            quotient[j++] = toCharacter(localQuotient);
            localDivident -= localQuotient * divisor;
        }

You have an if statement that excludes localQuotient == 0, but it shouldn't. This is what prevents the 0 from being output.

Code simplification

You also have two other special cases dealing with zeros that can be removed, because they are properly handled by the normal case code. Your main loop should be reduced from 16 lines to these 6 lines:

for (i = 0, j = 0; i < length; i++) {
    localDivident = localDivident * 10 + toNumber(a[i]);
    int localQuotient = localDivident / divisor;
    quotient[j++] = toCharacter(localQuotient);
    localDivident -= localQuotient * divisor;
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for the simplification. I've been looking at the same lines for so long that I missed some of the redundancy that I had! However, I found that after making your suggested modifications, the output is prepended with a zero in some cases. For example, divide("16\0", 8) returns "02\0". \$\endgroup\$ – Martin Tuskevicius Jul 20 '16 at 13:58
  • 1
    \$\begingroup\$ @MartinTuskevicius Ah I see. You could fix this by either 1) Using a variable in the main loop (e.g. isLeadingZeros) where you skip zeros if the variable is true and then turn the variable off on the first non-zero, or 2) Use a prepass loop that skips all the leading zeros. In either case, you need to generate a special case for the whole answer being 0 because either solution will leave you with an empty string if you don't check for that. \$\endgroup\$ – JS1 Jul 20 '16 at 17:33
  • \$\begingroup\$ Thanks for your input, I have fixed the bug! (I would - if I could - put the fix in this comment.) \$\endgroup\$ – Martin Tuskevicius Jul 20 '16 at 18:30
3
\$\begingroup\$

Some additional points after @JS1 fine answer.

  1. For array indexing, use size_t rather than int as int may be insufficient. Code goal is "an arbitrarily large number", so be prepared.

  2. Clever and good use of realloc() as a failed re-allocation can return quotient - ([edit] when the re-allocation size > 0, which is always the case here).

    char *resized = realloc(quotient, j);
    return (resized == NULL) ? quotient : resized;
    
  3. Suggest consistent use of types with unsigned int divisor and int localDivident.

  4. Unfamiliar with Divident. Perhaps Dividend.

  5. Since divide() may return NULL, and the function is likely to repeated called, suggest adding NULL test.

    char *divide(char *a, unsigned int divisor) {
      if (a == NULL) return NULL;
      ...
    
  6. Extending divide() to provide the remainder may be useful.

Concerning toNumber(), since it is so simple, code could use direct code. For speed, with such a small issue, profile code to and use what works. Not likely to make much difference on other platforms.

\$\endgroup\$
  • \$\begingroup\$ D'oh! It is dividend, not divident. \$\endgroup\$ – Martin Tuskevicius Jul 20 '16 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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