Efficient Array Initialization in Visual C++ for a 4-Digit Odometer

[LCKurtz]

Let's say you have a 4 digit "odometer" using just the digits 0 through 7. So it starts at 0000 and works its way up to 7777. So, for example, the next reading after 0007 is 0010 etc. There are $8^4 = 4096$ readings before it rolls over. I want to create and initialize an array with $4096$ rows and $4$ columns with the elements of each row being the corresponding digits (integer type). Like this:$$
\begin {bmatrix}
0 & 0 & 0 & 0\\
0 & 0 & 0 & 1\\
& & \cdots & \\
7 & 7 & 7 & 6\\
7 & 7 & 7 & 7
\end {bmatrix}$$
I'm just experimenting with C$^{++}$ in Microsoft Visual Studio. A code snippet for this would save me a lot of time and likely be more efficient than what I might come up with.

 

[phyzguy]

It would save you a lot of time, but would defeat the purpose of you learning how the code works. Why don't you write a code snippet and let us critique it?

 

[LCKurtz]

It would save you a lot of time, but would defeat the purpose of you learning how the code works. Why don't you write a code snippet and let us critique it?

Because it's part of an almost pointless personal project, because although I have written lots of software over the years, the C$^{++}$ environment is new to me, because I am retired and I have no need to "learn how the code works", and because when (if I bother to) I slog through the new environment for the proper headers and syntax to get it working, I won't need your critique. And I also happen to know that one of the best ways to learn a new environment is to see examples from others who already know. That's why.

 

[Dr Transport]

Because it's part of an almost pointless personal project, because although I have written lots of software over the years, the C$^{++}$ environment is new to me, because I am retired and I have no need to "learn how the code works", and because when (if I bother to) I slog through the new environment for the proper headers and syntax to get it working, I won't need your critique. And I also happen to know that one of the best ways to learn a new environment is to see examples from others who already know. That's why.

Until you slog through getting headers etc going in C/C++, reading someone else's code isn't going to help very much. I tried your approach years ago and until I did it, my C/C++ ability was lacking.

 

[FactChecker]

I can't, offhand, think of any "slick" way to do that. Any simple way you have is probably as good as any. Clearly, four nested loops from 0 to 7 would do it. Modern computers are so fast that they can fill that array in a millisecond. So unless this is something that will be done a very great number of times, I would leave it simple.

 

[Filip Larsen]

If your octal counters are a stable part of your problem domain (i.e. you don't later want to change that to another base), then you may want skip the array and just generate the four counts from the index directly. And in that case you may also want to look up bit fields (hint: it should be possible to generate the four counts directly from a type cast from an int index to a struct with four bit fields).

 

[Klystron]

Combining the two previous posts, your simplest solution appears to be that computing the indices for the hypothetical matrix already gives you the counter value at that index.

 

[wle]

Because it's part of an almost pointless personal project, because although I have written lots of software over the years, the C$^{++}$ environment is new to me, because I am retired and I have no need to "learn how the code works", and because when (if I bother to) I slog through the new environment for the proper headers and syntax to get it working, I won't need your critique. And I also happen to know that one of the best ways to learn a new environment is to see examples from others who already know. That's why.

The problem you're asking about has nothing special to do with the Microsoft Visual Studio environment.

Here's one way to do what you're asking:

unsigned int digits[4096][4];

for (unsigned int i=0; i<4096; ++i) {
    digits[i][0] = (i / 512) % 8;
    digits[i][1] = (i / 64) % 8;
    digits[i][2] = (i / 8) % 8;
    digits[i][3] = i % 8;
}

Since the base happens to be a power of 2, you can alternatively get the digits out of the index with bit operations. E.g., do (i >> 3) & 07 instead of (i / 8) % 8. But that's a bit more cryptic and less general.

Also, in the name "C++", the "++" is not a superscript.

 

[LCKurtz]

The problem you're asking about has nothing special to do with the Microsoft Visual Studio environment.

Here's one way to do what you're asking:

unsigned int digits[4096][4];

for (unsigned int i=0; i<4096; ++i) {
    digits[i][0] = (i / 512) % 8;
    digits[i][1] = (i / 64) % 8;
    digits[i][2] = (i / 8) % 8;
    digits[i][3] = i % 8;
}

Since the base happens to be a power of 2, you can alternatively get the digits out of the index with bit operations. E.g., do (i >> 3) & 07 instead of (i / 8) % 8. But that's a bit more cryptic and less general.

Also, in the name "C++", the "++" is not a superscript.

Thank you. That is very useful.

 

[Mark44]

Here's a different approach from the one presented by @wle, that uses the idea hinted at by @Klystron. This code will fill the array with 0000, 0001, 0002, ... , 7777.
Nested loops aren't ideal for performance, as they cause the CPU pipeline to be invalidated, but I don't think this is a concern for this problem.

const unsigned short MAX = 8;
const unsigned int ROWS = 4096;
unsigned short arr[ROWS][4];

int main()
{
  int rowNum = 0;
  for (unsigned short d0 = 0; d0 < MAX ; d0++)          // Thousands place
      for (unsigned short d1 = 0; d1 < MAX; d1++)        // Hundreds place
         for (unsigned short d2 = 0; d2 < MAX; d2++)     // Tens place
            for (unsigned short d3 = 0; d3 < MAX; d3++)  // Ones place
            {
                rowNum++;
                arr[rowNum][0] = d0;
                arr[rowNum][1] = d1;
                arr[rowNum][2] = d2;
                arr[rowNum][3] = d3;
           }
}

 

[hmmm27]

I have to admit, the proffered code is giving me a blepharospasm ; yeah, I know, "run once", "optimizing compiler". Still ...

What is the actual application ? On-the-fly would probably be more efficient than a 2d-table access, and more elegant than loading said table, for anything I can think of offhand...

 

[newjerseyrunner]

I'm not sure why you would ever want to put all of that into memory. You're storing 16kb of information to store a lookup table for a formula involving 3 of the simplest CPU functions. Lookup tables tend to be used for more complicated maths like trig.

unsigned int digits(int row, int column){
     return (row >> (column << 8)) & 07;  //untested but should produce the same results as everything above
}

When I think about it, this particular function call would almost certainly be faster than calling a lookup table because that would imply: moving the index 0 address into a register, calculating the offset from row and column (which requires multiplication... which is bad,) adding the values together, then grabbing the value from RAM, where the entire function above will take place in the registers without any adding or multiplying.