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:
- CLZ or Count Leading Zeros, gives you a count of how many zeros appear before the leading 1 bit.
- 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.
