How can I count in a different number base in C++?

Question

My 15 year old little brother is starting out programming, and he wrote a neat little program that outputs all combination of letters and numbers that are six digits or less. His code was a sextuple-nested for loop that updated the elements of a six level char array. It looked bad, but was certainly fast! I showed him how to do a simple count, and convert those numbers to base 36.

The biggest problem is that my code was so much slower than his, due to the division I was doing. Is there a way that I can simply assume base 36 and output a count from 1 to 36^6?

Ideally, I'm looking to do something like

[base 36]
for(int i = 0; i < 1000000; i++)
   SaveForLaterFileOutput(i);

Answer 1

to convert a number to base 36: make an accumulator and start from a sufficiently high degree, for example 36^6. If accumulator plus that number is less than your number, add it to the accumulator and repeat for the same degree (the count of this is the digit value), if it's greater, throw it away. Repeat for lower degrees until you get to 36^0. Keep track of the count for each degree, and that's your number in base 36.

to print it out in a meaningful way, do something else.

Answer 2

All numbers used in calculations are in base 2. Any other number you see is just an illusion on how it's printed. Hence your SaveForLaterOutput is pointless.

The library function itoa() (that translates to "integer to ASCII") (these days it has been replaced by the secure _itoa_s() function) allows you to specify the base when preparing for output.

Answer 3

It's possible for your brother to update his 6-element array without needing 6 nested loops. By modifying the increment function below, you can count in any "base" you choose:

#include <algorithm>
#include <iostream>

#define NUM_CHARS 6

// assuming ASCII
// advances through a chosen sequence 0 .. 9, a .. z
// or returns -1 on overflow
char increment(char &c) {
    if (c == 'z') return -1;
    if (c == '9') { c = 'a'; return c; }
    return ++c;
}

int main() {
    char source[NUM_CHARS+1] = {0};
    std::fill_n(&source[0], NUM_CHARS, '0');
    while (true) {
        std::cout << source << "\n";
        int idx = NUM_CHARS;
        // increment and test for overflow
        while (increment(source[--idx]) == -1) {
            // overflow occurred: carry the 1
            source[idx] = '0';
            if (idx == 0) return 0;
        }
    }
}

I haven't bothered with the "or fewer" part of the problem: however you've done it with 6 loops will probably work with this technique too. Strictly speaking, this is enumerating combinations, which is nearly but not quite the same thing as counting.