limits reached

Discussion in 'C Programming' started by O.R.Senthil Kumaran, Oct 24, 2004.

  1. Hi all,
    I am trying with the following Question:
    Q: Consider a function which, for a given whole number n, returns the
    number of ones required when writing out all numbers between 0 and n. For
    eg: f(13)=6. Notice that f(1)=1.

    What is the next largest n such that f(n) =n.

    To solve this, I wrote the following program:

    #include<limits.h>
    #include<stdio.h>
    int main(void)
    {
    unsigned long long int i,n,count;
    for(i=1;i<=ULLONG_MAX;i++)
    {
    count=0;
    while((n=(i%10))>10)
    {
    if(n==1)
    count++;
    i/=10;
    }
    if (n == 1)
    count++;
    if( i == count)
    printf("%llu",i);
    }
    }

    But, the program (a.out) is running for more than 45 minutes! now without
    any output.
    Is it feasible to try out such a program? How should I approach this
    otherwise?

    Regards,
    Senthil



    http://sarovar.org/projects/uthcode/
     
    O.R.Senthil Kumaran, Oct 24, 2004
    #1
    1. Advertising

  2. O.R.Senthil Kumaran

    Artie Gold Guest

    O.R.Senthil Kumaran wrote:
    > Hi all,
    > I am trying with the following Question:
    > Q: Consider a function which, for a given whole number n, returns the
    > number of ones required when writing out all numbers between 0 and n. For
    > eg: f(13)=6. Notice that f(1)=1.
    >
    > What is the next largest n such that f(n) =n.
    >
    > To solve this, I wrote the following program:
    >
    > #include<limits.h>
    > #include<stdio.h>
    > int main(void)
    > {
    > unsigned long long int i,n,count;
    > for(i=1;i<=ULLONG_MAX;i++)
    > {
    > count=0;
    > while((n=(i%10))>10)
    > {
    > if(n==1)
    > count++;
    > i/=10;
    > }
    > if (n == 1)
    > count++;
    > if( i == count)
    > printf("%llu",i);
    > }
    > }
    >
    > But, the program (a.out) is running for more than 45 minutes! now without
    > any output.
    > Is it feasible to try out such a program? How should I approach this
    > otherwise?
    >

    Hint: What is the value of ULLONG_MAX on your implementation?

    HTH,
    --ag

    --
    Artie Gold -- Austin, Texas

    "If you don't think it matters, you're not paying attention."
     
    Artie Gold, Oct 24, 2004
    #2
    1. Advertising

  3. On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
    > Hint: What is the value of ULLONG_MAX on your implementation?


    Maximum value - Unsigned long long int : 18446744073709551615

    Well, the program I posted initially was a wrong one. For the above
    problem, here is the correct program:

    /*Consider a function which, for a given whole number n, returns the
    number of ones required when writing out all numbers between 0 and n. For
    eg: f(13)=6. Notice that f(1)=1.
    What is the next largest n such that f(n) =n */

    #include<limits.h>
    #include<stdio.h>
    unsigned long long int countones(unsigned long long int); int main(void)
    {
    unsigned long long int i,cn;

    for(i = 1; i<= ULLONG_MAX; ++i)
    {
    cn = countones(i);
    if( i == cn)
    printf("%d",i);
    }

    return 0;
    }

    unsigned long long int countones(unsigned long long int i) {
    static unsigned long long int count = 0; int digit;

    while((i/10) >= 1)
    {
    digit = i % 10;

    if(digit == 1)
    count++;
    i /= 10;
    }
    if( i == 1)
    count++;

    return count;
    }
    The problem still remains,I understand unsigned long long integer is a
    HUGE number, but I would like to try out till the limits to get the
    solution to this problem. It is taking a long time and I have not
    reached the end of execution yet!(leave alone the results). Do you have
    any alternative to try out this?

    Senthil

    http://sarovar.org/projects/uthcode/
     
    O.R.Senthil Kumaran, Oct 24, 2004
    #3
  4. O.R.Senthil Kumaran

    Artie Gold Guest

    O.R.Senthil Kumaran wrote:
    > On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
    >
    >>Hint: What is the value of ULLONG_MAX on your implementation?

    >
    >
    > Maximum value - Unsigned long long int : 18446744073709551615


    This is (as you state below) a HUGE number.
    >
    > Well, the program I posted initially was a wrong one. For the above
    > problem, here is the correct program:
    >
    > /*Consider a function which, for a given whole number n, returns the
    > number of ones required when writing out all numbers between 0 and n. For
    > eg: f(13)=6. Notice that f(1)=1.
    > What is the next largest n such that f(n) =n */
    >
    > #include<limits.h>
    > #include<stdio.h>
    > unsigned long long int countones(unsigned long long int); int main(void)
    > {
    > unsigned long long int i,cn;
    >
    > for(i = 1; i<= ULLONG_MAX; ++i)
    > {
    > cn = countones(i);
    > if( i == cn)
    > printf("%d",i);

    Try:
    {
    printf("%d ", i);
    fflush(stdout);
    }
    otherwise you will see no output -- and Bad Things are likely to happen
    first.

    > }
    >
    > return 0;
    > }
    >
    > unsigned long long int countones(unsigned long long int i) {
    > static unsigned long long int count = 0; int digit;
    >
    > while((i/10) >= 1)
    > {
    > digit = i % 10;
    >
    > if(digit == 1)
    > count++;
    > i /= 10;
    > }
    > if( i == 1)
    > count++;
    >
    > return count;
    > }
    > The problem still remains,I understand unsigned long long integer is a
    > HUGE number, but I would like to try out till the limits to get the
    > solution to this problem. It is taking a long time and I have not
    > reached the end of execution yet!(leave alone the results). Do you have
    > any alternative to try out this?


    Right.

    You are executing the loop approximately (4 billion x 4 billion) times.
    4 billion seconds is approxiamtely 120 *years*.

    Do you see the problem?

    HTH,
    --ag


    --
    Artie Gold -- Austin, Texas

    "If you don't think it matters, you're not paying attention."
     
    Artie Gold, Oct 24, 2004
    #4
  5. O.R.Senthil Kumaran

    Jack Klein Guest

    On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
    <> wrote in comp.lang.c:

    > On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
    > > Hint: What is the value of ULLONG_MAX on your implementation?

    >
    > Maximum value - Unsigned long long int : 18446744073709551615
    >
    > Well, the program I posted initially was a wrong one. For the above
    > problem, here is the correct program:
    >
    > /*Consider a function which, for a given whole number n, returns the
    > number of ones required when writing out all numbers between 0 and n. For
    > eg: f(13)=6. Notice that f(1)=1.
    > What is the next largest n such that f(n) =n */
    >
    > #include<limits.h>
    > #include<stdio.h>
    > unsigned long long int countones(unsigned long long int); int main(void)
    > {
    > unsigned long long int i,cn;
    >
    > for(i = 1; i<= ULLONG_MAX; ++i)


    Since the subtle hint did not work, let's try the not-so-subtle hint.

    Your loop will end when 'long long int i' holds a value GREATER than
    ULLONG_MAX.

    If you still don't get it, reread the sentence above slowly.

    Hint:

    long long int i = ULLONG_MAX;

    ++i;

    What is the value of 'i'? It is GREATER than ULLONG_MAX?

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
     
    Jack Klein, Oct 24, 2004
    #5
  6. O.R.Senthil Kumaran

    Chris Torek Guest

    >On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
    >> Hint: What is the value of ULLONG_MAX on your implementation?


    In article <>
    O.R.Senthil Kumaran <> wrote:
    >Maximum value - Unsigned long long int : 18446744073709551615


    OK, now, what happens when i (a variable of type "unsigned long
    long") is equal to 18446744073709551615, and the loop executes the
    "i++" instruction? What is the new value in i? (Remember that
    unsigned arithmetic is modular or "clock" arithmetic, much as on
    a 12-hour clock, the hours count 1,2,3,...,9,10,11,12,1,2,3,... so
    that 12+1 = 1.)

    >... here is the correct program:


    The program still has a bug: your function countones() returns the
    number of '1' digits in the decial expansion of its argument. The
    the problem specifies:

    _n_
    \
    f(n) = > countones(i)
    /__
    i = 1

    but you call countones() only for one number; you need to compute
    the sum of countones() for n numbers (for a brute-force solution,
    which is clearly not the best possible solution).

    A hint for a "better" solution: consider any expansion of some
    number i, expressed in base b, as a series of terms:

    k k-1 1
    d b + d b + ... + d b + d
    k k-1 1 0

    For instance, i=175 in base 10 is 1(100) + 7(10) + 5. Here
    countones(i) is 1 (because there is one "1" digit, for ten squared,
    in the hundreds place). We can immediately see that countones(i-1)
    through countones(i-75) all have a 1 in the hundreds place -- so
    we need only consider the tens and ones places in all the smaller
    numbers. Once i exceeds 199 (up through 999 inclusive), however,
    it will have a 2 or 3 or ... or 9 in the hundreds place. The only
    contributions you can get to "1" digits will come from the tens and
    ones places.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Oct 24, 2004
    #6
  7. O.R.Senthil Kumaran

    Artie Gold Guest

    Jack Klein wrote:
    > On Mon, 25 Oct 2004 02:45:00 +0500, "O.R.Senthil Kumaran"
    > <> wrote in comp.lang.c:
    >
    >
    >>On Sun, 24 Oct 2004 15:39:43 -0500, Artie Gold wrote:
    >>
    >>>Hint: What is the value of ULLONG_MAX on your implementation?

    >>
    >>Maximum value - Unsigned long long int : 18446744073709551615
    >>
    >>Well, the program I posted initially was a wrong one. For the above
    >>problem, here is the correct program:
    >>
    >>/*Consider a function which, for a given whole number n, returns the
    >>number of ones required when writing out all numbers between 0 and n. For
    >>eg: f(13)=6. Notice that f(1)=1.
    >>What is the next largest n such that f(n) =n */
    >>
    >>#include<limits.h>
    >>#include<stdio.h>
    >>unsigned long long int countones(unsigned long long int); int main(void)
    >>{
    >> unsigned long long int i,cn;
    >>
    >> for(i = 1; i<= ULLONG_MAX; ++i)

    >
    >
    > Since the subtle hint did not work, let's try the not-so-subtle hint.
    >
    > Your loop will end when 'long long int i' holds a value GREATER than
    > ULLONG_MAX.
    >
    > If you still don't get it, reread the sentence above slowly.
    >
    > Hint:
    >
    > long long int i = ULLONG_MAX;
    >
    > ++i;
    >
    > What is the value of 'i'? It is GREATER than ULLONG_MAX?
    >

    Jack, the test in the code is `<='.

    The question is, when will it even get that far?

    Cheers,
    --ag

    --
    Artie Gold -- Austin, Texas

    "If you don't think it matters, you're not paying attention."
     
    Artie Gold, Oct 24, 2004
    #7
  8. In article <>,
    Chris Torek <> wrote:
    >
    >but you call countones() only for one number; you need to compute
    >the sum of countones() for n numbers (for a brute-force solution,
    >which is clearly not the best possible solution).


    "count" is declared static in countones(). As long as he calls
    countones in order (countones(1), countones(2), ...), which he does, it
    will return the correct answer.

    -- Brett
     
    Brett Frankenberger, Oct 25, 2004
    #8
  9. In article <>,
    "O.R.Senthil Kumaran" <> wrote:

    > Well, the program I posted initially was a wrong one. For the above
    > problem, here is the correct program:


    (put main on its own line, removed excess blank lines, added one or two
    blank lines)

    > /*Consider a function which, for a given whole number n, returns the
    > number of ones required when writing out all numbers between 0 and n. For
    > eg: f(13)=6. Notice that f(1)=1.
    > What is the next largest n such that f(n) =n */
    >
    > #include<limits.h>
    > #include<stdio.h>
    > unsigned long long int countones(unsigned long long int);
    >
    > int main(void)
    > {
    > unsigned long long int i,cn;
    >
    > for(i = 1; i<= ULLONG_MAX; ++i)
    > {
    > cn = countones(i);
    > if( i == cn)
    > printf("%d",i);
    > }
    > return 0;
    > }
    >
    > unsigned long long int countones(unsigned long long int i) {
    > static unsigned long long int count = 0; int digit;
    >
    > while((i/10) >= 1)
    > {
    > digit = i % 10;
    >
    > if(digit == 1)
    > count++;
    > i /= 10;
    > }
    > if( i == 1)
    > count++;
    >
    > return count;
    > }


    For what it's worth, it shouldn't take that long to get an answer.
    Unless I did something wrong, I get an answer which easily fits in a
    32-bit integer.

    I'd recommend you clean up your code some; the use of "static" in
    countones() is just asking for trouble -- main() should be doing the
    summation. You loop is also more complex than it needs to be.
    Something like:

    while (i > 0) {
    if ((i % 10) == 1)
    count++;
    i /= 10;
    }
    return (count);

    is equivalent, easier to understand, and avoids the fix-up afterwards.
    As someone else already pointed out, your printf() output is being
    buffered -- you should do something like:

    if (i == cn)
    printf("%d\n", i);

    Since stdout is line-buffered, this will guarantee a flush. Note that
    you should get the output "1" immediately -- if you don't, investigate
    your output code, not your algorithm.

    Cheers,
    - jonathan
     
    Jonathan Adams, Oct 25, 2004
    #9
  10. O.R.Senthil Kumaran

    Chris Torek Guest

    >In article <>,
    >Chris Torek <> wrote:
    >>but you call countones() only for one number ...


    In article <news:clhd8i$54r$>
    Brett Frankenberger <> wrote:
    >"count" is declared static in countones(). As long as he calls
    >countones in order (countones(1), countones(2), ...), which he does, it
    >will return the correct answer.


    Oops, quite right. I missed the "static" completely!
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Oct 25, 2004
    #10
  11. On Mon, 25 Oct 2004 01:31:27 +0500, O.R.Senthil Kumaran wrote:

    > Hi all,
    > I am trying with the following Question:
    > Q: Consider a function which, for a given whole number n, returns the
    > number of ones required when writing out all numbers between 0 and n.
    > For eg: f(13)=6. Notice that f(1)=1.
    >
    > What is the next largest n such that f(n) =n.
    >
    > To solve this, I wrote the following program:
    >
    > #include<limits.h>
    > #include<stdio.h>
    > int main(void)
    > {
    > unsigned long long int i,n,count;
    > for(i=1;i<=ULLONG_MAX;i++)
    > {
    > count=0;
    > while((n=(i%10))>10)
    > {
    > if(n==1)
    > count++;
    > i/=10;
    > }
    > if (n == 1)
    > count++;
    > if( i == count)
    > printf("%llu",i);
    > }
    > }
    >
    > But, the program (a.out) is running for more than 45 minutes! now
    > without any output.
    > Is it feasible to try out such a program? How should I approach this
    > otherwise?
    >
    > Regards,
    > Senthil


    I think that Google is looking for people that can solve this without
    going to newgroups for help ;) I might also add that as this is one of
    the easiest questions on the test, you are in bad shape if you are
    thinking about submitting the GLAT :(

    That said, there are a few very simple ways to go about this and it
    shouldn't take more than a fraction of a second for a well-written program
    to come up with the answer, which is just under 200,000. You can also
    solve this purely mathematically, without writing a program but it may
    take longer depending on your level of competence in the area.

    Out of purely educational interest, here is a simple program that will
    find you the answer working in the same vein as your flawed offering:

    #include <stdio.h>

    int
    main (void)
    {
    int ones = 6, i, n;
    for (i = 14; i < 200000; ++i)
    /* You want the first occurance ofter f(13)=6
    * so initialize ones to 6 and start at 14 */
    {
    n = i;
    while ( n > 0 )
    {
    if (n % 10 == 1) ++ones;
    n /= 10;
    }
    if (i == ones)
    {
    printf("%d\n",ones);
    return 0;
    }
    }
    return 1;
    }

    Rob Gamble
     
    Robert Gamble, Oct 25, 2004
    #11
  12. O.R.Senthil Kumaran

    Senthil Guest

    Robert Gamble <> wrote in message
    > I think that Google is looking for people that can solve this without
    > going to newgroups for help ;) I might also add that as this is one of
    > the easiest questions on the test, you are in bad shape if you are
    > thinking about submitting the GLAT :(


    Yeah the problem was from GLAT (No 17). I tried and could devise the
    brute force method of solving and it did. It was a practise for me in
    C programming as well.
    fflush(stdout) was the culprit, which did not print the number 199981!
    :)

    But got interested in the other aspects like time taken inside the
    loop which covers till ULLONG_MAX.

    Nope, I am not thinking of submitting to GLAT, just enjoying it.


    Thanks!
    Senthil
     
    Senthil, Oct 25, 2004
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Vladimir Davidov

    "max pool size was reached" problem again!

    Vladimir Davidov, Nov 20, 2003, in forum: ASP .Net
    Replies:
    1
    Views:
    9,148
    +The_Taco+
    Nov 20, 2003
  2. kw
    Replies:
    5
    Views:
    3,204
    S. Justin Gengo
    Jul 16, 2004
  3. Replies:
    1
    Views:
    10,627
  4. Aj-India

    Reached the 65535 bytes limit

    Aj-India, Sep 5, 2005, in forum: Java
    Replies:
    13
    Views:
    42,398
    Aj-India
    Sep 7, 2005
  5. =?Utf-8?B?Sm9u?=

    Timeout Expired...max pool size was reached.

    =?Utf-8?B?Sm9u?=, Oct 3, 2006, in forum: ASP .Net
    Replies:
    0
    Views:
    675
    =?Utf-8?B?Sm9u?=
    Oct 3, 2006
Loading...

Share This Page