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

pan64 · 06-13-2017, 09:28 AM

Quote:

Originally Posted by KenJackson

Because we're not on the clock, we're having fun.

Haven't compiled it, but here's my hyper efficient pow3 function for this use only:

Code:

unsigned pow3(unsigned x)
{
    static unsigned cube[] = { 0, 1, 8, 64, 125, 216, 343, 512, 729 };
    return (x < 10) ? cube[x] : 0;
}

No, I mean there is still a better way:

Code:

unsigned int pw[10];

// inside main:
    for (i=0; i<10; i++) {
        pw[i] = pow3(i);
    }

and you can use an array, there is no function call at all. But I'm afraid gcc -O3 knows still better way.

Laserbeak · 06-13-2017, 09:29 AM

Quote:

Originally Posted by GazL

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.

pan64 · 06-13-2017, 09:34 AM

Quote:

Originally Posted by Laserbeak

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.

that means you can calculate up to 9 digits

GazL · 06-13-2017, 09:44 AM

My program doesn't stop at cubes.

Quote:

An Armstrong number is an n-digit number that is equal to the sum of the nth powers of its digits.

So, for the values between 1000 and 9999 my program uses ^4
e.g. 1634 = 1^4 + 6^4 + 3^4 + 4^4.
For values 10000 to 99999 it uses ^5 and so on.

Once you get up to the higher powers, it's very easy to overflow.

Laserbeak · 06-13-2017, 09:45 AM

Quote:

Originally Posted by pan64

that means you can calculate up to 9 digits

I'm not exactly sure what you're getting at -- in this you only have to add the cubes of 3 digits.

However, you can always make it an unsigned long long and you get a full 64-bit max of 18446744073709551615

Laserbeak · 06-13-2017, 09:50 AM

Quote:

Originally Posted by GazL

My program doesn't stop at cubes.

So, for the values between 1000 and 9999 my program uses ^4
e.g. 1634 = 1^4 + 6^4 + 3^4 + 4^4.
For values 10000 to 99999 it uses ^5 and so on.

Once you get up to the higher powers, it's very easy to overflow.

OK, I forgot you wrote a more generalized program.

So basically you need 9^9 * 9, which is 3486784401 which is still within the limits of unsigned int.

pan64 · 06-13-2017, 10:00 AM

Quote:

Originally Posted by GazL

Here's my final program:

here are my tests using your code on my host, there is only one addition, I used an array instead of your power function:

Code:

int pw[11][11];

// in main()

  for (i=0; i<10; i++)
    for (j=1; j<11; j++)
       pw[i][j] = power(i, j);

// in is_armstrong()
     int t = pw[i % 10][n] ;

Code:

           function    array
compiled    3:52.33    1:35.03    # without any -O flags
gcc -O3     1:15:93    0:43.89

Laserbeak · 06-13-2017, 10:25 AM

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.

pan64 · 06-13-2017, 10:31 AM

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

GazL · 06-13-2017, 11:00 AM

Thanks Pan. That's a significant speed-up by anyone's standards. I'll have to incorporate that one before I file away the finished product.

pan64 · 06-13-2017, 11:27 AM

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 ;
}

Laserbeak · 06-13-2017, 12:42 PM

OMG, I actually did it with SSE!!! This is my first vector program (with some help from reading a lot of things and one post to another site):

Code:

#include <stdio.h>
#include <smmintrin.h>  // SSE 4.1

__m128i vcube(const __m128i v)
{
    return _mm_mullo_epi32(v, _mm_mullo_epi32(v, v));
}


int main(int argc, const char * argv[]) {
    for (unsigned int i = 1; i <= 500; i++) {
        unsigned int firstDigit = i / 100;
        unsigned int secondDigit = (i - firstDigit * 100) / 10;
        unsigned int thirdDigit = (i - firstDigit * 100 - secondDigit * 10);
        
        __m128i v = _mm_setr_epi32(0, firstDigit, secondDigit, thirdDigit);
        __m128i v3 = vcube(v);
        
        v3 = _mm_hadd_ps(v3,v3);
        v3 = _mm_hadd_ps(v3,v3);

        if (_mm_extract_epi32(v3, 0) == i)
            printf ("%d is an Armstrong number\n", i);
    }
    return 0;
}

It'd be great if you can test its speed!

ntubski · 06-13-2017, 12:54 PM

Quote:

Originally Posted by Laserbeak

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

Since they deal with floating point numbers, the table lookup is going to be a lot more complicated than 3 multiplies.
References:
https://sourceware.org/glibc/wiki/Ob...ns%20on%20libm
https://github.com/evanphx/ulysses-l...src/math/exp.c

Laserbeak · 06-13-2017, 12:56 PM

Quote:

Originally Posted by ntubski

Since they deal with floating point numbers, the table lookup is going to be a lot more complicated than 3 multiplies.

OK, well try the SSE version I just posted, at least according to Intel's marketing, it should be wicked fast!

GazL · 06-13-2017, 01:11 PM

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!