Return to Answer

• 1

• 28.9k
• 3
• 41
• 83

There's a lot of good reviews already. I'll try to add things that haven't been said yet, and point out how you can really speed the program up.

##Printout##

Your printout is a little strange in that you print all the numbers on one line. That by itself is OK if that's what you prefer, but you should at least print a newline at the very end. For example, in my shell, after I ran your program my shell prompt appeared at the end of your long line of output. Personally, I would prefer one number per line. That way I can more easily compare the results of different runs with varying maximum values.

##Faster way of computing digits and length##

You duplicate work when you first compute the number of digits and then you extract the digits one by one. In each case you have a division loop. There is a much faster way of doing this work, which is to maintain an array of digits, which represents the current number. Each time you move on to the next number, you can increment the ones digit in this array and handle carries as necessary. By maintaining this array, you no longer have to use division or modulus, which are expensive.

I made a sample program that used this idea and it was 19x faster than the original program.

##Incrementally updating the sum##

You can do even better than the above by also maintaining the sum of the digits ^ power. Between one number and the next, usually only one digit changes. So you can just update the sum by adding the difference between that digit and the new digit. Suppose a digit changes from x to x+1. To update the sum, you need to do: sum += (x+1)^length - x^length. When the digit carries over from 9 to 0, you do sum -= 9^length. If you have all of these power differences cached in an array, updating the sum will be as simple as sum += diffCache[digit][length].

I wrote a program using this technique, and the result was 66x faster than the original program.

##Sample program##

Here is my program with the digit array and the incrementally updated sum.

#include <stdio.h>
#include <stdlib.h>
#define MAX_DIGITS 14
void findArmstrong(int maxVal);
int main(int argc, char *argv[])
{
 if (argc < 2) {
 printf("Usage: %s maxval\n", argv[0]);
 return 0;
 }
 int maxVal = atoi(argv[1]);
 if (maxVal < 0)
 return 0;
 findArmstrong(maxVal);
}
/**
 * For this algorithm, an array called digits will contain the current base
 * 10 digits of the number "num". The digits array is in little endian order,
 * which means digits[0] is the ones digit, digits[1] is the tens digit, etc.
 *
 * There is also a diffCache array. This array holds the differences between
 * two consecutive digit ^ power numbers. For example:
 *
 * diffCache[5][8] = 5^8 - 4^8;
 * diffCache[0][8] = 0^8 - 9^8;
 */
void findArmstrong(int maxVal)
{
 int digits[MAX_DIGITS] = {0};
 int length = 1;
 int sum = 0;
 int diffCache[10][MAX_DIGITS];
 // Set up the diffCache array.
 {
 int powerValues[10] = {0,1,2,3,4,5,6,7,8,9};
 for (int j = 1; j < MAX_DIGITS; j++) {
 // powerValues[i] holds the value of: i ^ j
 diffCache[0][j] = -powerValues[9];
 for (int i = 1; i < 10; i++)
 diffCache[i][j] = powerValues[i] - powerValues[i-1];
 // Update powerValues[i] to hold the next higher power
 for (int i = 1; i < 10; i++)
 powerValues[i] *= i;
 }
 }
 // Iterate through every number from 0..maxVal to find Armstrong numbers.
 for (int num = 0; num <= maxVal; num++) {
 // If the number is equal to the sum, this is an Armstrong number.
 if (num == sum)
 printf("%d\n", num);
 // Update digits by adding 1 to the ones digit and carrying to higher
 // digits as necessary. We update the length of the number if we
 // carry to a digit not previously used. The sum is also updated
 // as we update each digit.
 int i = 0;
 while (1) {
 if (++digits[i] == 10) {
 digits[i] = 0;
 sum += diffCache[0][length];
 if (++i == length) {
 // Note that the sum must be 0 at this point, because
 // all the digits are 0 when we carry over to a new length.
 length++;
 }
 continue;
 }
 sum += diffCache[digits[i]][length];
 break;
 }
 }
}

Using a max value of 2000000000, this program ran in 3.3 seconds, compared to the original program which ran in 220 seconds, for a 66x speedup.