simplifying nested for loop in C

Question

I am looking for a narcissistic number with 3 to 9 digits. I have working code, but the use of nested loops is cumbersome. I think I could use recursion, how?

#include "stdafx.h"
#include <time.h>

int power(int a,int b)
{
    int t=1,i;
    for (i=0;i<b;i++)
        t*=a;
    return t;
}

int _tmain(int argc, _TCHAR* argv[])
{
    double t0=clock();
    int a,b,c,d,e,f,g,h,i;
    int len=9;
    for (a=1;a<=9;a++)
        for (b=0;b<=9;b++)
            for (c=0;c<=9;c++)
                for (d=0;d<=9;d++)
                    for (e=0;e<=9;e++)
                        for (f=0;f<=9;f++)
                            for (g=0;g<=9;g++)
                                for (h=0;h<=9;h++)
                                    for(i=0;i<=9;i++)
                                {
                                    int num=10*(10*(1000000*a+100000*b+10000*c+1000*d+100*e+10*f+g)+h)+i;
                                    if (num==power(a,len)+power(b,len)+power(c,len)+power(d,len)+power(e,len)+power(f,len)+power(g,len)+power(h,len)+power(i,len))
                                        printf(" %d ",num);
                                }
                                printf("\n耗时： %f s",(clock()-t0)/CLOCKS_PER_SEC);

    return 0;
}

I would be surprised if this doesn't suffer from a lot of integer overflow, as written. Investigate a bignum library. — unwind
– unwind, Commented Sep 12, 2012 at 9:21
int is more than enough 9*9^9 is the biggest part which fits in int — huseyin tugrul buyukisik
– huseyin tugrul buyukisik, Commented Sep 12, 2012 at 9:22
@unwind, if he uses unsigned int it would fit. 9^9 * 9 is 3,486,784,401. — Shahbaz
– Shahbaz, Commented Sep 12, 2012 at 9:22

Community · Accepted Answer · 2017-05-23 12:27:15Z

2

Your num is simply iterating through all numbers from 0 (See Edit 2) to 999,999,999. So you really don't need to iterator over every digit. A simple way of doing what you want, even though probably not anymore efficient is this:

unsigned int num;
for (num = 0; num < 1000000000; ++num)      // will take long
{
    char digits[15];
    unsigned int i, other_num;
    sprintf(digits, "%09u", i);             // division used here
    other_num = 0;
    for (j = 0; j < 9; ++j)
        other_num += power(digits[j] - '0', len);
    if (num == other_num)
        printf(" %d ",num);
}

Note that you can do your power function in a more efficient way. See this question.

Edit 1: (Note: see Edit 2)

I am reading through the wikipedia page, and it turns out that you shouldn't set len to 9, because if you have for example 153, the other_num should be 1^3 + 5^3 + 3^3 (example from Wikipedia).

So you should adjust the loop in the following way:

unsigned int num;
for (num = 0; num < 1000000000; ++num)
{
    char digits[15];
    unsigned int i, other_num, len;
    len = snprintf(digits, 10, "%u", i);    // len returned by snprintf
    other_num = 0;
    for (j = 0; j < len; ++j)               // changed 9 to len
        other_num += power(digits[j] - '0', len);
    if (num == other_num)
        printf(" %d ",num);
}

Edit 2:

I just noticed that your number starts from 100,000,000, so you don't really need to pay attention to Edit 1. Nevertheless, I believe it's good to know it in case you needed to change the range of your numbers.

edited May 23, 2017 at 12:27

CommunityBot

11 silver badge

answered Sep 12, 2012 at 9:27

Shahbaz

47.8k19 gold badges120 silver badges187 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

Sulthan Over a year ago

Exactly what I thought - but also note he uses only 9 different powers so he can efficiently put them into an array.

Jack Over a year ago

Num is starting from 100000000 in the original post, and you don't need to put the number into an array of char to get the digit at position n: you can improve performance using num % 10^(n+1)

Shahbaz Over a year ago

@Jack, you are right, I missed that. I'll edit it. Also, num % 10^(n+1) has worse performance than snprintf. With *printf, there are as many divisions as the number of digits. In your method, there is one division (comes with %) and a power per digit.

Jack Over a year ago

@Shahbaz i'm not completely agree. sprintf() is very expensive compared to math operations. It parses the format string, has conditional jumps on length condition, and must copy chars into buffer. Plus, to obtain the decimal representation in somehow it must use a method similar to num%10^n, isn't it? A benchmark would be interesting

Jack Over a year ago

@Shahbaz Ok i tested it :). Using num % pow(10, num+1) is very slow compared to sprintf(). But caching the power of ten (int pow[] = {10, 100, 1000, 10000, ...}) make it go faster than sprintf(). Cheers

|

Jack · Accepted Answer · 2012-09-12 09:32:11Z

1

Wonderful loop. What about this:

for( num = 100000000; num <= 999999999; num++ ) {
    int compare = 0;
    for( k = 0; k < 10; k++ ) {
        int position = pow(10, k+1);
        int s = num%position;
        compare += pow(s, 9);
    }
    if( num == compare ) {
        printf("%d\n", num);
    }
}

Of course, check for boundaries :)

answered Sep 12, 2012 at 9:32

Jack

1,6161 gold badge15 silver badges24 bronze badges

Comments

Sulthan · Accepted Answer · 2012-09-12 09:30:06Z

0

Actually, you are inspecting all values (num) from 1 to 10^len, if I am not mistaken. So, a simple for cycle from 1 to 10^len would be enough. Then you can take the digits from num and calculate the power value.

I would strongly suggest to calculate the powers 1^len, 2^len ... 9^len first and put them into an array. It will greatly improve performance.

answered Sep 12, 2012 at 9:30

Sulthan

130k23 gold badges223 silver badges277 bronze badges

Collectives™ on Stack Overflow

simplifying nested for loop in C

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related