Printing Armstrong numbers from 1 to 500. (C Programming)

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

Swapping to unsigned int or even unsigned long postpones the eventuality, but you can definitely hit an overflow and sooner than you expect. With signed ints, the first value it happens at is:
1000000009
Swapping to unsigned only raises that slightly and doesn't appear to be worth the effort:
1000009777

Basically it's the 9^10 + 7^10 etc... that is doing the damage and the extra bit from dropping signedness really doesn't help. Remember, my program is using powers greater than 3.

Here's my final program:

I get UINT_MAX (from limits.h) is equal to 4294967295. I don't see how you can get anywhere close to that number by adding the cubes of 3 one-digit numbers together, as 9^3 * 3 is only equal to 2187.

And making anything unsigned, basically doubles the maximum number, since no negative numbers are expressible.

I get UINT_MAX (from limits.h) is equal to 4294967295. I don't see how you can get anywhere close to that number by adding the cubes of 3 numbers together, as 9^3 * 3 is only equal to 2187.

Just to throw another wrench in, instead of something like this:

Code:

unsigned int pow3 (unsigned int x) {
return x * x * x;
}

Or a lookup table for pre-calculated values, you can also do something like:

Code:

unsigned long long int myPower (unsigned int base, unsigned int power) {
return (unsigned long long int) llroundl (expl(logl(base) * power));
} // returns base ^ power

exp() and log() are generally very fast, they are basically lookup tables themselves, so this should be faster than multiplying the numbers manually.

eliminating the calculation of length ( for ( i = num ; i > 0 ; i /= 10 ) n++ ; ) will make it again definitely faster:
without -O3 1:01.78, with -O3 0:31.78

you are welcome.
This is how I made that, but actually it is not nice, just working:

Code:

int main (int argc, char *argv[])
{
printf("Armstrong numbers between 1 and %d:\n", LAST);
unsigned int n;
unsigned int i, j, k;
for (i=0; i<10; i++)
for (j=1; j<11; j++)
pw[i][j] = power(i, j);
for ( n = 0 ; n <= LAST ; n++ ) {
switch (n) {
case 0: k=1; break;
case 10: k=2; break;
case 100: k=3; break;
case 1000: k=4; break;
case 10000: k=5; break;
case 100000: k=6; break;
case 1000000: k=7; break;
case 10000000: k=8; break;
case 100000000: k=9; break;
case 1000000000: k=10; break;
}
if ( is_armstrong(n, k) ) // this k is passed and used instead of that for loop
printf("%d\n", n) ;
}
return 0 ;
}

I went this way, with an outer loop looping by order of magnitude, generating the current powers array (single dimension) for each order of power and then an inner loop checking the values...

Code:

int powers[10] ;
int is_armstrong(int num)
{
int sum = 0 ;
int t = 0 ;
for ( int i = num ; i > 0 && /* optimisation */ sum <= num ; i /= 10 ) {
t = powers[i % 10] ;
if ( (INT_MAX - sum) >= t)
sum += t ;
else {
fprintf(stderr, "BOOM! Overflow while calculating value: %d\n", num) ;
exit(1);
}
}
return ( num == sum ) ;
}
int main (int argc, char *argv[])
{
int o, s, e, n ; /* Order, Start, End, Num */
printf("Armstrong numbers:\n");
for ( o = 1, s = 0, e = 9 ; o < 10 ; o++, s = e + 1, e = s * 10 - 1 ) {
for ( int i = 0 ; i < 10 ; i++ )
powers[i] = power(i, o) ;
for ( n = s ; n <= e ; n++ )
if ( is_armstrong(n) )
printf("%d\n", n) ;
}
return 0 ;
}

execution is down to 23 seconds now (with -O3) but speed isn't everything -- except when it is ofcourse -- and I thought my original code was easier to maintain. I also don't like that is_armstrong() without the length check is no longer a general/reusable function, but it was an interesting exercise in optimisation.

Thanks to all those who took an interest in this topic. Best Necro post ever!

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.