4
\$\begingroup\$

Inspired by this question (link to original video), I decided to write some code in C to perform this task, and it is much faster than the Python code, even when run with PyPY, up to a billion, it takes just 700 seconds.

For \$10^8\$ (a hundred million) it takes 62 seconds, while Python with pypy about 5 minutes!

Task

Given a number transform it into the length of the English one-zero representation: for example 2 is one_zero = 7. Calculate how many of these numbers end in 13 and in 18 when applying this step repeatedly. (All numbers end in one of the two.)

My code is really simple, but I am a beginner in C so I ask you in case I may have missed optimizations:

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <limits.h>

int letter_sum(int n) {
    int sum = 0;
    while (n != 0) {
        div_t x = div(n, 2);
        n = x.quot;
        sum += x.rem == 0 ? 4 : 3;
    }
    return sum;
}


int ends_in_18(int n) {
  if (n == 18) {return 1;}
  if (n == 13) {return 0;}
  return ends_in_18(letter_sum(n));
}

int main() {
    assert(letter_sum(18) == 18);

    int eighteen_count = 0;
    for (int i = 1; i < 100000000; i++) {
        if (ends_in_18(i)) {
            eighteen_count++;
        }
        else { printf("%d ", i); }
    }
    printf("%d %d\n", 100000000 < INT_MAX, eighteen_count);
}
\$\endgroup\$
5
\$\begingroup\$

Optimization, step by step

I ran your program and it took 38.5 seconds to run on my computer. After playing around with it for a bit, I was able to speed it up by 100x. I went through three different iterations to get to that point.

1) Use bit manipulation instead of division

The first thing I noticed was that your letter_sum() function was doing a loop across the bits, but it was using a division function to do so. If you switched to using bitwise operators, it would speed up the program by a lot. The remainder when dividing n by 2 is simply n & 1. The quotient after dividing n by 2 is n >> 1. In this rewrite, I have switched to using uint32_t to ensure that the shifting is an unsigned shift.

static uint32_t letter_sum(uint32_t n)
{
    uint32_t sum = 0;
    while (n != 0) {
        sum += (n & 1) ? 3 : 4;
        n >>= 1;
    }
    return sum;
}

Switching to this function made the program run in 4.4 seconds, or 8.75 times faster than the original.

2) Use more advanced bit tricks

The function can be improved even more by using more advanced bit counting techniques. Essentially, you are adding 4 for each 0 bit and 3 for each 1 bit, up to the leading 1 bit in the number. You can count these bits without using a loop by using two types of bit counting:

  1. CLZ or Count Leading Zeros, gives you a count of how many zeros appear before the leading 1 bit.
  2. POPCOUNT or Population Count, gives you a count of how many 1 bits are in the number.

Both CLZ and POPCOUNT can often be done in single machine instructions, so they are much more efficient than looping through each bit.

If you have the above two counts, then the letter sum of a 32-bit number will be:

128 - CLZ(n)*4 - POPCOUNT(n)

The reasoning for this equation is that you start with the maximum letter sum, which is 32 zeros = 128 letters. From that, you subtract 4 for each leading zero, because leading zeros do not count towards the letter sum. After that, you subtract 1 for each 1 bit, because "one" has one less letter than "zero". So the function now looks like this (assuming a gcc compiler):

static inline uint32_t letter_sum(uint32_t n)
{
    return 128 - __builtin_clz(n)*4 - __builtin_popcount(n);
}

I added the inline keyword since this function is so simple it should be inlined. After switching to this function, the program now ran in 2.4 seconds, or 16 times faster than the original.

3) Use memoization limited to a small range

The third step is to add memoization to the program. But first, we should realize that the result of letter_sum() can only be in the range 3..127. The lowest letter sum is for 1, with sum 3. The highest letter sum is for 100000...0000, with sum 127. So you can use a boolean array of size 128 to remember whether the sum ends in 18 or 13.

Here is the final rewrite using memoization. I kept your main() function pretty much the same, although I wasn't sure why you were printing 100000000 < INT_MAX.

#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include <limits.h>
#include <stdint.h>
#include <stdbool.h>

// Maximum index will be 127 because a 32-bit number with 1 "one" and 31
// "zero" has 127 letters.
#define CACHE_MAX        128

// cache[i] is true if letter_sum(i) eventually leads to 18.
static bool cache[CACHE_MAX];

// Maximum is 32 "zero" = 128
// Remove 4 letters for each leading zero, since leading zeros don't count
// Remove 1 letters for each "one", because "one" has 1 less letter than "zero"
static inline uint32_t letter_sum(uint32_t n)
{
    return 128 - __builtin_clz(n)*4 - __builtin_popcount(n);
}

static void fillCache(void)
{
    for (uint32_t i=1; i<CACHE_MAX; i++) {
        uint32_t n = i;
        while (n != 13 && n != 18) {
            n = letter_sum(n);
        }
        if (n == 18)
            cache[i] = true;
    }
}

static inline bool ends_in_18(uint32_t n)
{
    return cache[letter_sum(n)];
}

int main(void)
{
    assert(letter_sum(18) == 18);
    fillCache();

    uint32_t eighteen_count = 0;
    for (uint32_t i = 1; i < 100000000; i++) {
        if (ends_in_18(i)) {
            eighteen_count++;
        }
        else { printf("%d ", i); }
    }
    printf("%d %d\n", 100000000 < INT_MAX, eighteen_count);
}

This version ran in 0.39 seconds, or 100x faster than the original.

\$\endgroup\$
  • \$\begingroup\$ 100000000 < INT_MAX is a sanity check to make sure no overflow occurs. Very interesting bitwise knowledge here, I was 99% sure that div was using bitwise for the 2 special case, but I was wrong... \$\endgroup\$ – Caridorc Jan 16 '17 at 14:20
  • \$\begingroup\$ Did you compile my code with -O3 option? \$\endgroup\$ – Caridorc Jan 16 '17 at 14:30
  • 1
    \$\begingroup\$ @Caridorc I used -O2 but I tried -O3 just now and nothing changed. Also, you can use uint32_t to make sure that your integer size is 32 bits and is large enough to reach 10 million. \$\endgroup\$ – JS1 Jan 16 '17 at 18:13
  • 1
    \$\begingroup\$ Note that, in your step #1, you do not need to explicitly write the code using bit-manipulation operators. As long as you avoid using the div_t silliness, any compiler will optimize division and modulo operations to the appropriate bit-twiddling operations (if they are indeed faster on your target architecture). This is not only easier for a human to read and understand, but also makes the code more portable. It'll even do it for signed types, but I agree that unsigned is more appropriate here, and enables even more optimizations. \$\endgroup\$ – Cody Gray Jan 17 '17 at 11:23
  • 1
    \$\begingroup\$ Yes, @Caridorc. I suppose, come to think of it, that's kind of odd. You'd think that it would cause the compiler to do the division only once, giving you both the quotient and the remainder. But in every compiler I've ever seen, div_t turns into a call to a library function that does not get inlined. In fact, constant folding is not even performed! So it's always a pessimization. By the same token, I've never seen a compiler that won't fold together a division and modulo operation on the same values into a single x86 DIV(or IDIV) instruction, so just always use that. \$\endgroup\$ – Cody Gray Jan 18 '17 at 7:06

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.