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

ntubski · 06-12-2017, 04:03 PM

Quote:

Originally Posted by danielbmartin

Timings ...

I wonder why the sum of user+sys is so much less than real. Can you post for comparison the timing of this "solution":

Code:

cat <<EOF
1
153
370
371
407
EOF

danielbmartin · 06-12-2017, 04:53 PM

Quote:

Originally Posted by ntubski

Can you post for comparison the timing of this "solution" ...

Gladly. I am inexperienced at making time measurements, so corrections and constructive criticisms are welcome.

There are two programs, dbm1796.bin and dbm1796a.bin.
dbm1796.bin is an executive program which invokes a slave.
dbm1796a.bin is the slave program which contains each of six solutions.

To replicate my measurements execute dbm1796 once.

dbm1796.bin

Code:

#!/bin/bash   Daniel B. Martin   Jun17
#
#  To execute this program, launch a terminal session and enter:
#  bash /home/daniel/Desktop/LQfiles/dbm1796.bin
#
#  This program inspired by ...
#    http://www.linuxquestions.org/questions//programming-9/
#      printing-armstrong-numbers-from-1-to-500-c-programming-466789/
 
echo "This program measures the time required to execute"
echo "   different correct solutions to the same problem."
echo "Since the programs run so quickly it is necessary"
echo "  to repeat the execution of each several thousand times to"
echo '  get meaningful results as determined by the Linux system command "time."'

RepCount=1000
echo; echo "Each program will execute $RepCount times."

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin a $RepCount

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin b $RepCount

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin c $RepCount

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin d $RepCount

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin e $RepCount

time bash /home/daniel/Desktop/LQfiles/dbm1796a.bin f $RepCount

echo; echo "Normal end of job."; echo; exit

dbm1796a.bin

Code:

#!/bin/bash   Daniel B. Martin   Jun17
#

#  File identification
      Path=${0%%.*}
    InFile=$Path"inp.txt"
   OutFile=$Path"out.txt"

#echo; echo "Entering program dbm1796a."
#echo "Routine selector = $1; Repetition count = $2"
echo

if [ "$1" == "a" ]; then
  echo "Method #1 of LQ Member danielbmartin, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      seq -w 500  \
      |awk -F "" '{if ($1^3+$2^3+$3^3==$0) print}' >$OutFile
    done
  exit
fi

if [ "$1" == "b" ]; then
  echo "Method #2 of LQ Member danielbmartin, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      seq -w 500        \
      |egrep -v '[89]'  \
      |awk -F "" '{if ($1^3+$2^3+$3^3==$0) print}' >$OutFile
    done
  exit
fi

if [ "$1" == "c" ]; then
  echo "Method #3 of LQ Member danielbmartin, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      awk 'BEGIN{for (j=1;j<=500;j++)
                {k="00"j;
          a=substr(k,length(k)-2,3);  # a = j with leading zeros
          h=substr(a,1,1);  # h = hundreds
          t=substr(a,2,1);  # t = tens
          u=substr(a,3,1);  # u = units
          if (h^3+t^3+u^3==j) print a}}' >$OutFile
    done
  exit
fi

if [ "$1" == "d" ]; then
  echo "Method #1 of LQ Member KenJackson, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      awk 'BEGIN{for (h=0;h<8;h++)
                  for (t=0;t<8;t++)
                   for (u=0;u<8;u++)
         if ((h||t||u) && (h^3+t^3+u^3==h*100+t*10+u)) print h t u}' >$OutFile
    done
  exit
fi

if [ "$1" == "e" ]; then
  echo "Method #1 of LQ Senior Member ntubski, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      awk 'BEGIN{for (j=1;j<=500;j++) {
        h=int(j/100);     # h = hundreds
        t=int(j/10) % 10; # t = tens
        u=j % 10;         # u = units
        if (h^3+t^3+u^3==j) print j}}' >$OutFile
    done
  exit
fi

if [ "$1" == "f" ]; then
  echo "Method #2 of LQ Senior Member ntubski, repeated" $2 "times."
  for ((j=1;j<=$2;j++))
    do
      awk 'BEGIN{for (j=1;j<=500;j++) {
        split(sprintf("%03d", j), digits, "");
        if (digits[1]^3+digits[2]^3+digits[3]^3==j) print j}}' >$OutFile
    done
  exit
fi


echo; echo "Routine selection parameter $1 is undefined."; exit

Daniel B. Martin

Laserbeak · 06-12-2017, 05:07 PM

Quote:

Originally Posted by danielbmartin

calculate every Armstrong number between 1 and 500
... this requires an algorithm. Do you know one?

No, but I had some ideas. I've been distracted so haven't been able to work on or think about the problem since I typed that. If there is a solution beyond simply pruning/making more efficient a brute-force tactic, it almost surely includes fun functions like log() and exp().

danielbmartin · 06-12-2017, 05:19 PM

This web page ...
http://www.magic-squares.net/narciss.htm
... contains a wealth of information but no algorithm.

Daniel B. Martin

Laserbeak · 06-12-2017, 05:35 PM

After spending some time with a pencil, paper and scientific calculator, I gave up and cheated by looking at the Internet. It seems there is no way to calculate all Armstrong numbers mathematically. The numbers are actually a subset of "narcissistic numbers" that are the sums of each of the digits to the power of the length of number so you could have x = a^5 + b^5 + c^5 +d^5 +e ^5 where x is 5 digits long.

GazL · 06-12-2017, 07:08 PM

Yep, I originally wrote a program to the spec listed in this thread (working with cubes only), but then I read the background on these numbers and reworked it. This is the result

Code:

#define LAST 100000000

#include <stdio.h>
#include <math.h>

int is_armstrong(int num)
{
  int n = 0 ;
  int sum = 0 ;
  
  for ( int i = num ; i > 0 ; i /= 10 )
    n++ ;
  for ( int i = num ; i > 0  && /* optimisation */ sum <= num ; i /= 10 )
    sum += pow(i % 10, n) ;

  return ( num == sum ) ;
}

int main (int argc, char *argv[])
{
  printf("Armstrong numbers between 1 and %d:\n", LAST);

  for (int n = 0 ; n <= LAST ; n++ )
    if ( is_armstrong(n) )
      printf("%d\n", n) ;

  return 0 ;
}

The sum <= num optimisation saves about 20% on cpu and elapsed time.

I'm not a professional programmer, so I dare say it can probably be done better.

Laserbeak · 06-12-2017, 07:22 PM

I was thinking, I wonder if you could do this in binary in assembly code. Then it occurred, it makes no sense in binary since 1^x always equals 1 and 0 ^ x always equals 0. I think that might be part of the problem, since it is totally dependent on the base of the numbers involved.

So it just seems like a human-noticed oddity, not anything mathematically based.

ntubski · 06-12-2017, 09:45 PM

Quote:

Originally Posted by GazL

sum += pow(i % 10, n) ;

I would guess you'd get a significant increase by writing your own pow function that operates only on positive integer powers. The standard pow function has to do a lot more work.

Quote:

Originally Posted by Laserbeak

I was thinking, I wonder if you could do this in binary in assembly code. Then it occurred, it makes no sense in binary since 1^x always equals 1 and 0 ^ x always equals 0.

There's no reason using assembly implies calculating base 2 Armstrong numbers.

Laserbeak · 06-12-2017, 10:04 PM

Quote:

Originally Posted by ntubski

There's no reason using assembly implies calculating base 2 Armstrong numbers.

Yes, but in mathematics, if something isn't true in all bases, it's just an anomaly of a certain base. It's not a mathematical identity. That's why I said it's just an oddity of some numbers in base 10. You could find other numbers in hexadecimal or other bases that have similar oddities, but they'd be different numbers.

Laserbeak · 06-13-2017, 03:30 AM

I was looking into using one of the SSE SIMD commands to see if you could raise each digit to the third power in one instruction, but this runs so fast, even unoptimized, why bother?

Only if you were looking for much longer "narcissistic numbers" would it matter.

My plain vanilla unoptimized code:

Code:

#include <stdio.h>

unsigned int pow3 (unsigned int x);

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);
        
        if (pow3(firstDigit) + pow3(secondDigit) + pow3(thirdDigit) == i)
            printf ("%d is an Armstrong number\n", i);
    }
    return 0;
}

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

GazL · 06-13-2017, 04:20 AM

Quote:

Originally Posted by ntubski

I would guess you'd get a significant increase by writing your own pow function that operates only on positive integer powers. The standard pow function has to do a lot more work.

Yes, thanks for that. It actually occurred to me last night to try that, along with the idea that I should use unsigned ints and probably worry about int overflows.

Using my own power() function reduced the time from 43 to 17 seconds.

edit:
Scratch that: I forgot the -O2 on the compile. It's down to around 5 seconds, so almost by a factor of 10!

Laserbeak · 06-13-2017, 04:30 AM

Quote:

Originally Posted by GazL

the idea that I should use unsigned ints and probably worry about int overflows.

Unless you're using a computer that belongs in a museum, I don't think it's possible to overflow an unsigned int with this program.

pan64 · 06-13-2017, 05:25 AM

Code:

#include <stdio.h>

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

void armstrong1() {
    unsigned int i;
    for (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);

        if (pow3(firstDigit) + pow3(secondDigit) + pow3(thirdDigit) == i)
            printf ("%d is an Armstrong number\n", i);
    }
}

void armstrong3() {
    unsigned int i;
    unsigned int d1, d2, d3;
    unsigned int pd1, pd2, pd3;
    unsigned int dd1, dd2;
    for (d1 = 0; d1<6; d1++ ) {
        pd1 = pow3(d1);
        dd1 = 100*d1;
        for (d2 = 0; d2<10; d2++ ) {
            pd2 = pow3(d2);
            dd2 = 100*d2;
            for (d3 = 0; d3<10; d3++ ) {
                pd3 = pow3(d3);

                i=dd1+dd2+d3;
            if (pd1 + pd2 + pd3 == i)
                printf ("%d is an Armstrong number\n", i);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    unsigned int j;
    for (j=0;  j<100000; j++) {
        armstrong1();
    }
    return 0;
}

optimization (gcc -O3) counts a lot, but also lowering the calls to pow3 helps.

Code:

            armstrong1   armstrong3
compiled      0.84           0.42
gcc -O3       0.31           0.08

time in seconds, measured by: /usr/bin/time -f %E ./a >/dev/null, on my own host.

GazL · 06-13-2017, 07:47 AM

Quote:

Originally Posted by Laserbeak

Unless you're using a computer that belongs in a museum, I don't think it's possible to overflow an unsigned int with this program.

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:

KenJackson · 06-13-2017, 08:51 AM

Quote:

Originally Posted by Laserbeak

..., but this runs so fast, even unoptimized, why bother?

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