5

I know that you can get the digits of a number using modulus and division. The following is how I've done it in the past: (Psuedocode so as to make students reading this do some work for their homework assignment):

int pointer getDigits(int number) 
    initialize int pointer to array of some size
    initialize int i to zero
    while number is greater than zero
       store result of number mod 10 in array at index i
       divide number by 10 and store result in number
       increment i
    return int pointer

Anyway, I was wondering if there is a better, more efficient way to accomplish this task? If not, is there any alternative methods for this task, avoiding the use of strings? C-style or otherwise?

Thanks. I ask because I'm going to be wanting to do this in a personal project of mine, and I would like to do it as efficiently as possible.

Any help and/or insight is greatly appreciated.

2
  • Repeated div/mod is all you can do. Even sprintf() has to do that. Nov 10, 2010 at 3:55
  • 1
    won't the OP algo give digits in reverse order?
    – Chubsdad
    Nov 10, 2010 at 4:12

7 Answers 7

3

The time it takes to extract the digits will be dwarfed by the time required to dynamically allocate the array. Consider returning the result in a struct:

struct extracted_digits
{
    int number_of_digits;
    char digits[12];
};

You'll want to pick a suitable value for the maximum number of digits (12 here, which is enough for a 32-bit integer). Alternatively, you could return a std::array<char, 12> and encode the terminal by using an invalid value (so, after the last value, store a 10 or something else that isn't a digit).

Depending on whether you want to handle negative values, you'll also have to decide how to report the unary minus (-).

1
  • negatives also change the behavior of modulo, so take the absolute value immediately after noting the sign
    – Ben Voigt
    Nov 10, 2010 at 5:04
3

Unless you want the representation of the number in a base that's a power of 2, that's about the only way to do it.

1

Smacks of premature optimisation. If profiling proves it matters, then be sure to compare your algo to itoa - internally it may use some CPU instructions that you don't have explicit access to from C++, and which your compiler's optimiser may not be clever enough to employ (e.g. AAM, which divs while saving the mod result). Experiment (and benchmark) coding the assembler yourself. You might dig around for assembly implementations of ITOA (which isn't identical to what you're asking for, but might suggest the optimal CPU instructions).

3
  • Should check out the functions div(), ldiv() and lldiv(). They return both the quotient and the remainder and almost always optimize well in machine code.
    – Zan Lynx
    Nov 10, 2010 at 6:22
  • Updated: I thought that they optimized but on x86 it appears not.
    – Zan Lynx
    Nov 10, 2010 at 6:31
  • @Zan Lynx: interesting point - you'd certainly hope they'd use the assembly if available, though you'd want to check each one in a debugger to find out which word-sizes were efficient, but crucially in my experience with GCC they're not inlined and that might well overwhelm any performance benefit :-. Nov 10, 2010 at 6:33
1

By "avoiding the use of strings", I'm going to assume you're doing this because a string-only representation is pretty inefficient if you want an integer value.

To that end, I'm going to suggest a slightly unorthodox approach which may be suitable. Don't store them in one form, store them in both. The code below is in C - it will work in C++ but you may want to consider using c++ equivalents - the idea behind it doesn't change however.

By "storing both forms", I mean you can have a structure like:

typedef struct {
    int ival;
    char sval[sizeof("-2147483648")]; // enough for 32-bits
    int dirtyS;
} tIntStr;

and pass around this structure (or its address) rather than the integer itself.

By having macros or inline functions like:

inline void intstrSetI (tIntStr *is, int ival) {
    is->ival = i;
    is->dirtyS = 1;
}
inline char *intstrGetS (tIntStr *is) {
    if (is->dirtyS) {
        sprintf (is->sval, "%d", is->ival);
        is->dirtyS = 0;
    }
    return is->sval;
}

Then, to set the value, you would use:

tIntStr is;
intstrSetI (&is, 42);

And whenever you wanted the string representation:

printf ("%s\n" intstrGetS(&is));
fprintf (logFile, "%s\n" intstrGetS(&is));

This has the advantage of calculating the string representation only when needed (the fprintf above would not have to recalculate the string representation and the printf only if it was dirty).

This is a similar trick I use in SQL with using precomputed columns and triggers. The idea there is that you only perform calculations when needed. So an extra column to hold the indexed lowercased last name along with an insert/update trigger to calculate it, is usually a lot more efficient than select lower(non_lowercased_last_name). That's because it amortises the cost of the calculation (done at write time) across all reads.

In that sense, there's little advantage if your code profile is set-int/use-string/set-int/use-string.... But, if it's set-int/use-string/use-string/use-string/use-string..., you'll get a performance boost.

Granted this has a cost, at the bare minimum extra storage required, but most performance issues boil down to a space/time trade-off.

And, if you really want to avoid strings, you can still use the same method (calculate only when needed), it's just that the calculation (and structure) will be different.


As an aside: you may well want to use the library functions to do this rather than handcrafting your own code. Library functions will normally be heavily optimised, possibly more so than your compiler can make from your code (although that's not guaranteed of course).

It's also likely that an itoa, if you have one, will probably outperform sprintf("%d") as well, given its limited use case. You should, however, measure, not guess! Not just in terms of the library functions, but also this entire solution (and the others).

1

It's fairly trivial to see that a base-100 solution could work as well, using the "digits" 00-99. In each iteration, you'd do a %100 to produce such a digit pair, thus halving the number of steps. The tradeoff is that your digit table is now 200 bytes instead of 10. Still, it easily fits in L1 cache (obviously, this only applies if you're converting a lot of numbers, but otherwise efficientcy is moot anyway). Also, you might end up with a leading zero, as in "0128".

1

Yes, there is a more efficient way, but not portable, though. Intel's FPU has a special BCD format numbers. So, all you have to do is just to call the correspondent assembler instruction that converts ST(0) to BCD format and stores the result in memory. The instruction name is FBSTP.

0

Mathematically speaking, the number of decimal digits of an integer is 1+int(log10(abs(a)+1))+(a<0);.

You will not use strings but go through floating points and the log functions. If your platform has whatever type of FP accelerator (every PC or similar has) that will not be a big deal ,and will beat whatever "sting based" algorithm (that is noting more than an iterative divide by ten and count)

Your Answer

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

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