Is there still room for optimization in this part of the code?

Let’s start by a minor rewrite of your code – like:

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {  // Reduced by a factor 10 compared to OP code
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 10 ? m % 10 : m;
                sum += t * t;
                m /= 10;
            }
            n = sum;
        }
    }
    return n;
}

int main(void) {
  printf("%d\n", HappyTest());
}

Running this on my system takes 10.7 seconds.

Your code is about: take a number and calculate the sum of all its digits squared.

So your multiplications are limited to 10 different multiplications, i.e. 0*0, 1*1, …, 9*9

So one idea for optimization could be to put the results into a table and do a table look-up instead of a multiplication. Like:

int mul_tab_10[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81};

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 10 ? m % 10 : m;
                sum += mul_tab_10[t];
                m /= 10;
            }
            n = sum;
        }
    }
    return n;
}

Running this on my system takes 12.9 seconds. So it is slower.

But what if we took this one step further? Instead of just using a table with 10 elements we could use a table with 100 elements. Like:

int mul_tab_100[100] = {0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 1, 2, 5, 10, 17, 26, 37, 50, 65, 82, 4, 5, 8, 13, 20, 29, 40, 53, 68, 85, 9, 10, 13, 18, 25, 34, 45, 58, 73, 90, 16, 17, 20, 25, 32, 41, 52, 65, 80, 97, 25, 26, 29, 34, 41, 50, 61, 74, 89, 106, 36, 37, 40, 45, 52, 61, 72, 85, 100, 117, 49, 50, 53, 58, 65, 74, 85, 98, 113, 130, 64, 65, 68, 73, 80, 89, 100, 113, 128, 145, 81, 82, 85, 90, 97, 106, 117, 130, 145, 162};

int HappyTest()
{
    int n;
    for (int i = 0; i < 210000000; i++) {
        n = i;
        while (n >= 10) {
            int m = n, sum = 0;
            while (m != 0) {
                int t = m >= 100 ? m % 100 : m;  // Notice this change
                sum += mul_tab_100[t];
                m /= 100;                        // Notice this change
            }
            n = sum;
        }
    }
    return n;
}

Running this on my system takes 6.9 seconds. So the performance is improved.

Taking it one step further (i.e. 1000 elements) results in 5.3 seconds – again a improvement.

So yes, you can improve run time performance.

Browse More Popular Posts

Leave a Comment