LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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


Reply
  Search this Thread
Old 06-13-2017, 09:28 AM   #31
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,355

Rep: Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750

Quote:
Originally Posted by KenJackson View Post
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.
 
Old 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: Reputation: 142Reputation: 142
Quote:
Originally Posted by GazL View Post
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.
 
Old 06-13-2017, 09:34 AM   #33
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,355

Rep: Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750
Quote:
Originally Posted by Laserbeak View Post
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
 
Old 06-13-2017, 09:44 AM   #34
GazL
Senior Member
 
Registered: May 2008
Posts: 4,339
Blog Entries: 7

Rep: Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790
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.
 
Old 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: Reputation: 142Reputation: 142
Quote:
Originally Posted by pan64 View Post
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
 
Old 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: Reputation: 142Reputation: 142
Quote:
Originally Posted by GazL View Post
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.
 
Old 06-13-2017, 10:00 AM   #37
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,355

Rep: Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750
Quote:
Originally Posted by GazL View Post

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.
Old 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: Reputation: 142Reputation: 142
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.
 
Old 06-13-2017, 10:31 AM   #39
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,355

Rep: Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750
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
 
Old 06-13-2017, 11:00 AM   #40
GazL
Senior Member
 
Registered: May 2008
Posts: 4,339
Blog Entries: 7

Rep: Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790Reputation: 1790
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.
 
Old 06-13-2017, 11:27 AM   #41
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,355

Rep: Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750Reputation: 2750
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.
Old 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: Reputation: 142Reputation: 142
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!
 
Old 06-13-2017, 12:54 PM   #43
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Arch
Posts: 3,136

Rep: Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336Reputation: 1336
Quote:
Originally Posted by Laserbeak View Post
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
 
Old 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: Reputation: 142Reputation: 142
Quote:
Originally Posted by ntubski View Post
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!
 
Old 06-13-2017, 01:11 PM   #45
GazL
Senior Member
 
Registered: May 2008
Posts: 4,339
Blog Entries: 7

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


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
printing line numbers for code bauer172uw Programming 3 04-13-2006 11:10 PM
C programming - sorting random numbers Gigantor Programming 8 12-05-2005 10:32 PM
Printing numbers from a text file dynamically mrobertson Programming 1 06-28-2005 08:19 AM
printing numbers without using semicolon vijeesh_ep Programming 18 09-08-2004 11:59 AM
printing line numbers? fisheromen1031 Programming 1 07-27-2004 02:19 PM


All times are GMT -5. The time now is 02:59 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration