Visit Jeremy's Blog.
 LinuxQuestions.org Printing Armstrong numbers from 1 to 500. (C Programming)
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

06-13-2017, 09:28 AM   #31
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep:

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.

06-13-2017, 09:29 AM   #32
Laserbeak
Member

Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep:
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.

Last edited by Laserbeak; 06-13-2017 at 09:34 AM.

06-13-2017, 09:34 AM   #33
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep:
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

06-13-2017, 09:44 AM   #34
GazL
LQ Veteran

Registered: May 2008
Posts: 5,789

Rep:
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.

06-13-2017, 09:45 AM   #35
Laserbeak
Member

Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep:
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

06-13-2017, 09:50 AM   #36
Laserbeak
Member

Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep:
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.

06-13-2017, 10:00 AM   #37
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 16,207

Rep:
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```

1 members found this post helpful.
 06-13-2017, 10:25 AM #38 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: 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.
 06-13-2017, 10:31 AM #39 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: 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
 06-13-2017, 11:00 AM #40 GazL LQ Veteran   Registered: May 2008 Posts: 5,789 Rep: 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.
 06-13-2017, 11:27 AM #41 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 16,207 Rep: 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 ; }``` 1 members found this post helpful.
 06-13-2017, 12:42 PM #42 Laserbeak Member   Registered: Jan 2017 Location: Manhattan, NYC NY Distribution: Mac OS X, iOS, Solaris Posts: 508 Rep: 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 #include // 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!
06-13-2017, 12:54 PM   #43
ntubski
Senior Member

Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,590

Rep:
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

06-13-2017, 12:56 PM   #44
Laserbeak
Member

Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep:
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!

 06-13-2017, 01:11 PM #45 GazL LQ Veteran   Registered: May 2008 Posts: 5,789 Rep: 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! Last edited by GazL; 06-13-2017 at 01:14 PM. 1 members found this post helpful.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post bauer172uw Programming 3 04-13-2006 11:10 PM Gigantor Programming 8 12-05-2005 10:32 PM mrobertson Programming 1 06-28-2005 08:19 AM vijeesh_ep Programming 18 09-08-2004 11:59 AM fisheromen1031 Programming 1 07-27-2004 02:19 PM

LinuxQuestions.org

All times are GMT -5. The time now is 02:43 PM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -