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

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

By the way, I searched around for "cheap tricks" for multiprocessing, and I learned that xargs (the bash command) can be used to schedule a sequence of commands to utilize the available processors. So I modified one of my programs to take a command-line argument for the number of digits, and to write its output to a text file (because redirection to stdout may scramble the results), and tried it out as follows on my dual-processor rig:

As you see by comparing real vs. user time, this method approximately doubled the speed. Scheduling the jobs in reverse order (longest jobs first) gives better utilization of all processors. Otherwise the last (and longest) job would run by itself at the end. This timeline shows the sequence (not to scale):

This is not the most sophisticated kind of multiprocessing, but it can be used for uncoupled jobs, where no information needs to be passed between running processes.

As you see by comparing real vs. user time, this method approximately doubled the speed. Scheduling the jobs in reverse order (longest jobs first) gives better utilization of all processors. Otherwise the last (and longest) job would run by itself at the end. This timeline shows the sequence (not to scale):
This is not the most sophisticated kind of multiprocessing, but it can be used for uncoupled jobs, where no information needs to be passed between running processes.

Wow, cool! I didn't know xargs could do that.

I got around the problem of the big numbers taking longer by making an array of all the numbers to test then shuffling them randomly before splitting the array up according to the number of processors (actually cores) the machine has. The computer I'm running this on now is a tethered (connected to a LCD monitor, external keyboard, mouse, etc.) laptop. But it has an Intel Core i7 processor and shows up as 8 separate cores. And, according to the performance monitor, it was taking up an average of about 780% of the processor time so it seemed to work quite well.

There's just that problem of weird non-narcissistic numbers popping up in 4 and higher digits. I haven't been in the mood to work on it today, but maybe tomorrow. It looks like a weird error that may be hard to pin down. I really want to rewrite that section anyway, so maybe doing that will fix the problem.

Just for fun, I wrote a simple C program to find Armstrong numbers with any number of digits. Numbers are represented as integer arrays with one decimal digit stored in each array element. (This required a few array math functions which I provided as well.)

Tested: Running on a 1.8 GHz Pentium-M (single processor), it obtained all the Armstrong numbers of 1 to 39 digits in just under 18 hours.

New idea (?) for boosting the speed: Count rather than sort digits. One of the inefficiencies of my Python program (see Post 92), besides constantly recalculating the powers of digits, was sorting the digits of the sum. The issue is that sorting takes a lot of CPU cycles, and the sort resides in the innermost loop. An alternative is to count digits: how many zeroes, ones, twos, and so on, up to nines. Then the two numbers (actually their combinations of digits) can be compared by comparing counts. Here is a C implementation of that:

Code:

int count_and_compare_digits(int * array1, int * array2, int ndigits)
{
// array1 and array2 must contain decimal digits
// ndigits is the number of digits to be compared
int i;
int count1[10]; // small static arrays, no need for malloc
int count2[10];
for (i=0;i<10;++i)
{
count1[i] = 0; // initialize counts
count2[i] = 0;
}
for (i=0;i<ndigits;++i)
{
++count1[array1[i]]; // count according to value of digit
++count2[array2[i]];
}
for (i=0;i<10;++i)
{
if (count1[i] != count2[i]) // compare counts
return 0; // return 0 when any difference is detected
}
return 1; // return 1 if all digit counts are identical
}

The time requirement (so-called computational complexity) for this algorithm for N digits scales roughly as O(N), whereas sort algorithms tend to scale as O(N*log(N)), so this should be faster.

yes, I want to try something similar, but needs time to implement it. Actually I posted a better solution (instead of sorting), which is definitely faster.

yes, I want to try something similar, but needs time to implement it. Actually I posted a better solution (instead of sorting), which is definitely faster.

I apologize for not understanding your code and seeing that you did that.

to speed up the process we do not need to check all the numbers, but the ones generated using next_comb_rep. This is a great find and a very good improvement.

This next_comb_rep function works on char (digit) array (arbitrary length) - the result is stored in the variable vec.

We need to sum up power of these digits, which is impossible using predefined c types (because the maximal available length is not enough for us). The already implemented solutions to handle really big numbers are "relatively" slow, therefore I constructed a new type which consist of 3 unsigned long long integers. I restricted their usage to 16 digits, so altogether this can handle 48 digits which is fine for us (and obviously it can be extended if required). Only the required functionality was implemented: set/assign value (to int), multiply by a single digit, add bignum. normalize_bignum is used to handle the internal overflow (when any of internal ulli variables will contain more than 16 digits). Additionally there is a replacement of the traditional to_string or sprintf functionality, because that is quite slow. It is the funtion bignum_to_string which constructs list of digits from left to right (reverse order) and they are in the range 0x0-0x9 instead of '0' - '9' (0x30-0x39), similar way as it was generated/used in next_comb_rep. I use a table to do the conversion, this is named charmap.

Now we can invoke the function sum_of_power_of_digits on the generated vec using this bignum type,

convert the result bignum_to_string, check its length

count the different digits of vec and this bignum and compare them

and finally if everything was ok I convert the string to a printable char * (adding 48 to each digit and by reversing the order)

with this code the generation of all the 10 based narcissistic numbers was completed within 30 minutes (28:53.03) on my host.

And a few words about multithreading:
generation of 39 digit numbers was running at about 6 minutes (5:55.33) - 38 digits: 5 minutes (4:54.24), 37 digits: 4 minutes (3:55.28), 36 digits: 3 minutes (3:03.60) ...
so probably if we can have enough threads/CPU we can complete it in 6 minutes.

to speed up the process we do not need to check all the numbers, but the ones generated using next_comb_rep. This is a great find and a very good improvement.

This next_comb_rep function works on char (digit) array (arbitrary length) - the result is stored in the variable vec.

We need to sum up power of these digits, which is impossible using predefined c types (because the maximal available length is not enough for us). The already implemented solutions to handle really big numbers are "relatively" slow, therefore I constructed a new type which consist of 3 unsigned long long integers. I restricted their usage to 16 digits, so altogether this can handle 48 digits which is fine for us (and obviously it can be extended if required). Only the required functionality was implemented: set/assign value (to int), multiply by a single digit, add bignum. normalize_bignum is used to handle the internal overflow (when any of internal ulli variables will contain more than 16 digits). Additionally there is a replacement of the traditional to_string or sprintf functionality, because that is quite slow. It is the funtion bignum_to_string which constructs list of digits from left to right (reverse order) and they are in the range 0x0-0x9 instead of '0' - '9' (0x30-0x39), similar way as it was generated/used in next_comb_rep. I use a table to do the conversion, this is named charmap.

Now we can invoke the function sum_of_power_of_digits on the generated vec using this bignum type,

convert the result bignum_to_string, check its length

count the different digits of vec and this bignum and compare them

and finally if everything was ok I convert the string to a printable char * (adding 48 to each digit and by reversing the order)

sorting is still missing at the end.

Code:

...

with this code the generation of all the 10 based narcissistic numbers was completed within 30 minutes (28:53.03) on my host.

And a few words about multithreading:
generation of 39 digit numbers was running at about 6 minutes (5:55.33) - 38 digits: 5 minutes (4:54.24), 37 digits: 4 minutes (3:55.28), 36 digits: 3 minutes (3:03.60) ...
so probably if we can have enough threads/CPU we can complete it in 6 minutes.

Thanks for the explanations. I think I understand it all now. You have done a great job coding it for speed.

I see that you made at least two speed-related improvements since your previous code (in Post 125):

Converting bignum to string with charmap[], a lookup table for 4-digit segments, should be much quicker than using /10 and %10 for every digit. This is important because this conversion is done for every number that is tested.

Without going into a detailed analysis or test, I suspect that compare_digits() requires fewer operations than del(), so it should be faster.

I was wondering why you dimension powers[12] and fill it up to the 10th power. I thought powers[10] and filling only to the 9th power would be sufficient. Similarly I think it would be sufficient to dimension charmap[10000]. Did I miss the reason for the extra elements? (These would not impact the speed. I am just wondering whether this is a matter of function or style.)

I am sure that is clever and interesting in some way, but please maintain the focused spirit of unobfuscated and shared knowledge already established in this thread by providing some elucidation!

Distribution: M$ Windows / Debian / Ubuntu / DSL / many others

Posts: 2,339

Rep:

Quote:

Originally Posted by astrogeek

I am sure that is clever and interesting in some way, but please maintain the focused spirit of unobfuscated and shared knowledge already established in this thread by providing some elucidation!

Alright. That BF isn't written by hand. It is generated as specified by a scripting language.

The input script:

Code:

VAR A
VAR am
VAR B
VAR bm
VAR C
VAR cm
VAR total
VAR sum
DO
MULTIPLY cm C C
MULTIPLY cm C
MULTIPLY bm B B
MULTIPLY bm B
MULTIPLY am A A
MULTIPLY am A
ASSIGN sum cm
ADD sum bm
ADD sum am
IF sum = total
IF A > 0
ADD A 48
PRINT A
SUBTRACT A 48
ADD B 48
PRINT B
SUBTRACT B 48
ENDIF
ADD C 48
PRINT C
PRINT 10
SUBTRACT C 48
ENDIF
INC C
IF C > 9
CLEAR C
INC B
ENDIF
IF B > 9
CLEAR B
INC A
ENDIF
INC total
WHILE total != 500

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.