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, Sep 12 '12 at 09:21
int is more than enough 9*9^9 is the biggest part which fits in int — huseyin tugrul buyukisik, Sep 12 '12 at 09:22
@unwind, if he uses `unsigned int` it would fit. `9^9 * 9` is `3,486,784,401`. — Shahbaz, Sep 12 '12 at 09:22
@Sulthan Not using VS, just gcc version 4.6.1. Of course I changed _tmain and _TCHAR to main and char — Jack, Sep 12 '12 at 09:37
Here is a recursion version，that is I want http://www.cnblogs.com/c-hy/archive/2012/09/12/2682642.html — chyanog, Sep 12 '12 at 16:05

score 2 · Accepted Answer · edited May 23 '17 at 12:27

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 '17 at 12:27

Community

1
1

answered Sep 12 '12 at 09:27

Shahbaz

46,337
19
116
182

Exactly what I thought - but also note he uses only 9 different powers so he can efficiently put them into an array. – Sulthan Sep 12 '12 at 09:31
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) – Jack Sep 12 '12 at 09:34
@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. – Shahbaz Sep 12 '12 at 09:36
@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 Sep 12 '12 at 10:00
@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 Sep 12 '12 at 10:11
@Jack, just FYI, to get the digits, `*printf` finds a digit by `%10` and then does a `/10` to get the rest of the number. In most CPUs, `/` and `%` can be computed in one instruction. That is why it is fast. Of course, manual conversion is slightly faster (since `*printf` is a more generic function), but I'm not convinced it's _that_ faster. Do you have any figures from your test? – Shahbaz Sep 12 '12 at 15:49
@Shahbaz Not that faster, just faster: 0.75 of the time. No figures, i already deleted the code. Thanks for clarification about %10 and /10. Fasterer of course – Jack Sep 12 '12 at 16:47

score 1 · Answer 2 · answered Sep 12 '12 at 09:32

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 :)

score 0 · Answer 3 · answered Sep 12 '12 at 09:30

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.

simplifying nested for loop in C

3 Answers3