LinuxQuestions.org
Review your favorite Linux distribution.
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-12-2017, 04:03 PM   #16
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,163

Rep: Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370

Quote:
Originally Posted by danielbmartin View Post
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
 
Old 06-12-2017, 04:53 PM   #17
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Mint 17.3
Posts: 1,574

Rep: Reputation: 478Reputation: 478Reputation: 478Reputation: 478Reputation: 478
Quote:
Originally Posted by ntubski View Post
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
 
Old 06-12-2017, 05:07 PM   #18
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 danielbmartin View Post
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().
 
Old 06-12-2017, 05:19 PM   #19
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Mint 17.3
Posts: 1,574

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

Daniel B. Martin
 
Old 06-12-2017, 05:35 PM   #20
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 142Reputation: 142
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.
 
2 members found this post helpful.
Old 06-12-2017, 07:08 PM   #21
GazL
Senior Member
 
Registered: May 2008
Posts: 4,408
Blog Entries: 7

Rep: Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860
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.
 
1 members found this post helpful.
Old 06-12-2017, 07:22 PM   #22
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

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

Last edited by Laserbeak; 06-12-2017 at 07:29 PM.
 
Old 06-12-2017, 09:45 PM   #23
ntubski
Senior Member
 
Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,163

Rep: Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370Reputation: 1370
Quote:
Originally Posted by GazL View Post
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 View Post
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.
 
1 members found this post helpful.
Old 06-12-2017, 10:04 PM   #24
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
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.
 
Old 06-13-2017, 03:30 AM   #25
Laserbeak
Member
 
Registered: Jan 2017
Location: Manhattan, NYC NY
Distribution: Mac OS X, iOS, Solaris
Posts: 508

Rep: Reputation: 142Reputation: 142
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;
}

Last edited by Laserbeak; 06-13-2017 at 03:32 AM.
 
Old 06-13-2017, 04:20 AM   #26
GazL
Senior Member
 
Registered: May 2008
Posts: 4,408
Blog Entries: 7

Rep: Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860
Quote:
Originally Posted by ntubski View Post
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!

Last edited by GazL; 06-13-2017 at 04:34 AM.
 
Old 06-13-2017, 04:30 AM   #27
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
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.
 
Old 06-13-2017, 05:25 AM   #28
pan64
LQ Guru
 
Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 9,570

Rep: Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811Reputation: 2811
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.
 
Old 06-13-2017, 07:47 AM   #29
GazL
Senior Member
 
Registered: May 2008
Posts: 4,408
Blog Entries: 7

Rep: Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860Reputation: 1860
Quote:
Originally Posted by Laserbeak View Post
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:
Attached Files
File Type: txt armstrong.c.txt (1.2 KB, 9 views)

Last edited by GazL; 06-13-2017 at 08:16 AM.
 
Old 06-13-2017, 08:51 AM   #30
KenJackson
Member
 
Registered: Jul 2006
Location: Maryland, USA
Distribution: Fedora, PCLinuxOS
Posts: 648

Rep: Reputation: 84
Quote:
Originally Posted by Laserbeak View Post
..., 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;
}
 
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

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 11:48 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