c wont run my

This is a discussion on c wont run my within the C Programming forums, part of the General Programming Boards category; hi forum i've been trying to solve this problem: The following iterative sequence is defined for the set of positive ...

  1. #1
    Registered User
    Join Date
    Feb 2011
    Posts
    3

    c wont run my

    hi forum
    i've been trying to solve this problem:
    The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)

    Using the rule above and starting with 13, we generate the following sequence:
    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

    Which starting number, under one million, produces the longest chain?


    the code i've written looks like this:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    
    int main()
    {
        int *a, seq, maxseq=1, i, j, num=1;
        a=malloc(1000000 * sizeof(int));
        if(a==NULL){
            printf("........!");
            return 1;
        }
        a[1]=1;
        for(i=2; i<1000000; i++){
            seq=0;
            j=i;
            while(j>=i){
                if(j%2)
                    j=3*j+1;
                else
                    j/=2;
                seq++;
            }
            seq+=a[j];
            a[i]=seq;
            if(seq>maxseq){
                maxseq=seq;
                num=i;
            }
        }
        free(a);
        printf("%d",num);
    
    
        return 0;
    }
    the problem is every time i try to run it i get a message that says:
    "code.c has stopped working" and it shuts down... it works when i run it up to 100,000
    or so but it wont work for 1,000,000- can anyone help??
    btw im using code::blocks with GNU GCC compiler, dont know if thats relevant..

  2. #2
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by ajl913 View Post
    hi forum
    i've been trying to solve this problem:
    [I]The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)
    n → 3n + 1 (n is odd)
    This one intrigues me... I ran your code and here's a screen snip of what I got...

    Attachment 10356

    This is happening right at the end of your while (j <= i) and it's being caused by
    accessing the array in seq += a[j]; although I don't see exactly why you're doing that.
    Last edited by CommonTater; 03-16-2011 at 12:52 PM.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,761
    Aren't you supposed to be stopping at j == 1?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Registered User
    Join Date
    Feb 2011
    Posts
    3
    the program adds the sequence in place a[j] to what it counted so far to save time..
    once i know the number has reached a previous number which i already checked i can just add that numbers sequence

  5. #5
    Registered User
    Join Date
    Feb 2011
    Posts
    3
    thanks tater i changed i and j to unsigned longs and now it works

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,752
    thanks tater i changed i and j to unsigned longs and now it works
    Except that's not the problem.

    The problem with invoking undefined behavior is that you could "fix" something entirely unrelated, and get positive results. Commontater's access violation message is more typical of out of bounds array access.

    What do we have in the program that looks like that?
    Code:
     a[1]=1;
        for(i=2; i<1000000; i++){
    The acceptable range for an array is from 0 to n-1, inclusive. In this case, n is one million.

  7. #7
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by whiteflags View Post
    Except that's not the problem.

    The problem with invoking undefined behavior is that you could "fix" something entirely unrelated, and get positive results. Commontater's access violation message is more typical of out of bounds array access.

    What do we have in the program that looks like that?
    Code:
     a[1]=1;
        for(i=2; i<1000000; i++){
    The acceptable range for an array is from 0 to n-1, inclusive. In this case, n is one million.
    In this case if he starts the *calculations* at 0 or 1 it just hangs.

    As for the array... totally unnecessary... I elminated that from the program and got this...

    Attachment 10357

    Code:
    #include "global.h"
    #include <errorx.h>
    #includ <windows.h>
    
    int _cdecl main(int argc, char *argv[])
      { 
    
        unsigned int seq, maxseq=0, i, j, num=0;
        unsigned int ticks;     
    
        ticks= GetTickCount();
    
        for(i=2; i<1000000; i++){
            seq=0;
            j = i;
            while(j >= i){
                if(j & 1)
                    j=(j * 3) + 1;
                else
                    j /= 2;
                seq++;
           }
            if(seq>maxseq){
                maxseq=seq;
                num=i;
            }
        }
        ticks = GetTickCount() - ticks;
        printf("\nThe longest sequence results from %d, taking %d iterations\n",num,maxseq);
        printf("Runtime = %d milliseconds\n\n",ticks);
        return 0; }
    Last edited by CommonTater; 03-16-2011 at 12:52 PM.

  8. #8
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Ok one more pass, this time altering the code to correctly bring j down to 1...

    Attachment 10358

    Code:
    #include "global.h"
    #include <errorx.h>
    #include <windows.h>
    
    int _cdecl main(int argc, char *argv[])
      { unsigned int ticks;     
        unsigned int seq, maxseq=0, i, num=0;
        register unsigned int j;
    
        ticks= GetTickCount();
    
        for(i=2; i<1000000; i++)
          { seq=0;
            j = i;
            while(j > 1)
              { if(j & 1)
                  j=(j * 3) + 1;
                else
                  j /= 2;
                seq++; }
            if(seq>maxseq){
                maxseq=seq;
                num=i;
            }
        }
        ticks = GetTickCount() - ticks;
        printf("\nThe longest sequence results from %d, taking %d iterations\n",num,maxseq);
        printf("Runtime = %d milliseconds\n\n",ticks);
        return 0; }
    With j as a register variable it took nearly 200ms off the time.
    Using & instead of % to check for odd numbers saved an additional 80ms.
    Last edited by CommonTater; 03-16-2011 at 12:52 PM.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,157
    Quote Originally Posted by CommonTater
    With j as a register variable it took nearly 200ms off the time.
    That is surprising since conventional wisdom is that the register keyword is useless because modern compilers are able to determine very well what variables should take advantage of registers.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by laserlight View Post
    That is surprising since conventional wisdom is that the register keyword is useless because modern compilers are able to determine very well what variables should take advantage of registers.
    I was surprised too... However, there may have been a secondary effect here... In PellesC before the register keyword is used, you have to enable other optimizations ("Increase Speed More", in the IDE Ox and Ot at the command line) I didn't check, but it's entirely possible the gain was more due to those flags than the keyword.

    EDIT: I checked with the optimizations on then with and without the register keyword... about 12ms faster with the keyword, so apparently it does matter (a little bit) on PellesC. But your compiler's mileage may vary




    That was fun... Thanks to the OP for giving me a challenge today!
    Last edited by CommonTater; 02-15-2011 at 12:58 PM.

  11. #11
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,636
    Some compilers make no effort to optimize unless you say so explicitly, so they generate code in a very formulaic and not-so-efficient way, meaning they don't make best use of registers. But they will try to honor the register keyword if you say so. It appears that can often be trumped by optimizations however. We had an interesting discussion going about this a few weeks ago: Register and For loop.

  12. #12
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,636
    Oh, and is the OP aware that even for some numbers below 1,000,000, they will climb beyond the bounds of a 32-bit int before resolving to 1? There are likely going to be overflow issues in his/her code to consider. If possible, use something like uint64_t.

  13. #13
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by anduril462 View Post
    Oh, and is the OP aware that even for some numbers below 1,000,000, they will climb beyond the bounds of a 32-bit int before resolving to 1? There are likely going to be overflow issues in his/her code to consider. If possible, use something like uint64_t.
    The overflow was the original problem... So yes it's a real concern.
    No errors with unsigned ints though.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Re-doing a C program to run in Win2000 or XP
    By fifi in forum C Programming
    Replies: 5
    Last Post: 08-17-2007, 06:32 PM
  2. how to run an exe command in c++ and get back the results?
    By mitilkhatoon in forum C++ Programming
    Replies: 5
    Last Post: 09-21-2006, 07:00 PM
  3. calculating the mode
    By bigggame in forum C Programming
    Replies: 10
    Last Post: 06-13-2006, 04:04 AM
  4. How I can Run exe file in C++
    By palang in forum C++ Programming
    Replies: 2
    Last Post: 05-10-2006, 12:55 PM
  5. Replies: 2
    Last Post: 10-29-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21