Thread: Huge Array Problem

  1. #1
    Registered User
    Join Date
    Dec 2006
    Posts
    14

    Huge Array Problem

    I wrote this code for generating loads of prime numbers.

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<math.h>
    void main()
    {
    long unsigned int limit=4294967294;
    long unsigned int n,i,flag,j=1;
    clrscr();
    for(n=2;n<limit;n++)
    {
    flag=1;
    if(n==2)
    {
    printf("2");
    continue;
    }
    else
    {
    if(n%2==0)
    continue;
    }
    for(i=3;i<=sqrt(n)+1;i+=2)
    {
    if(n%i==0)
    {
    flag=0;
    break;
    }
    }
    if(flag==1)
    {
    j++;
    printf("%luth prime is %lu\n",j,n);
    }
    }
    getch();
    }
    It took 10 minutes on an AMD 64 BIT 2800 with 1 GB of Ram to get 250,000 primes.

    Now I know that everytime the prime is outputted to the screen it slows the program, so wanted to store the primes in an array.

    I created an array like this:

    Code:
    long unsigned int n,i,flag,j=1, a[4294967293];
    I get an error saying Array should have atleast one value.

    If i reduce the array size to say a[10000], it works fine.

    What could be the issue?

  2. #2
    Registered User
    Join Date
    Jan 2007
    Posts
    14
    well i dont know about unsigned ive only learnt about signed but the range of signed is -+32,768 for int

    you should use float.

  3. #3
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    You realized that if an int is 2 bytes you've just taken up 8589934586 bytes (8192 MB or 8 GB) of memory! (Not to mention the other problems with your code).
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  4. #4
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Quote Originally Posted by Niz
    well i dont know about unsigned ive only learnt about signed but the range of signed is -+32,768 for int

    you should use float.
    On most platforms int is a little bit longer
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  5. #5
    MFC killed my cat! manutd's Avatar
    Join Date
    Sep 2006
    Location
    Boston, Massachusetts
    Posts
    870
    Also, using float would make no difference.
    Silence is better than unmeaning words.
    - Pythagoras
    My blog

  6. #6
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    I get that memory part, tell me the other problems please, the above program runs fine so i presume it is right, the primes being given as output are also right, i have checked them.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,983
    Step 1 would be to learn about indentation, then read the FAQ on why void main is wrong.
    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.

  8. #8
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    don't use conio.h and replace getch by other standard input function to prevent closing the window
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  9. #9
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    The following web tool is worth giving a shot... your code seriously needs some beautification.
    http://www.tote-taste.de/X-Project/beautify/

    The literal error message from your compiler would be useful.

    It is possible that even though you are on a 64 bit computer, you are using a 32 bit compiler, which would mean your array must be less than 4,294,967,295 bytes long.
    Assuming that unsigned long ints on your sytem are 4 bytes long, you should do this:
    Code:
    unsigned long int a[1073741823]; // Biggest possible array of 4 byte ints in 32 bit compiler
    If that doesn't work, try cutting it in half.

    Incidentally, you should be hiitting your limit around the 500,000,000th prime.
    And the time it takes to print to screen is definitely not going to meaningfully slow down your program. It's slow because of the amazing number of divisions your program has to perform.
    Callou collei we'll code the way
    Of prime numbers and pings!

  10. #10
    Registered User simguy's Avatar
    Join Date
    Jan 2007
    Location
    Dallas-Ft Worth, TX
    Posts
    10
    Your unsigned int array is going to consume over 30 GB of memory!! long int is 4 bytes ! Unless you have access to a super computer, this will never work. You already stated that you got about 250,00 primes --- why do you need a 4 GB array to hold so many fewer values? You might want to break this down into separate programs to run a range of values instead of running 4 GB worth at one time.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    I don't know you algorithm, but you shouldn't need more than int prime[25000] for 25000 primes.

    To find them, you'll just need to check-divide each (odd) number with the primes that you have found so far. If it is not evenly divisible by any of these, it's a prime (if a number is divisible by 9, it is also divisible by 3 - a prime -, so you won't need to test separately if it can be divided by 9 - or any other non-prime). So the only thing you need to keep in memory - in addition to a few variables - is an array of previously found primes.

    For me, actually printing 25000 values to screen is a problem. The beginning of the output is lost for ever... and it takes much longer to print them than to find them. The 25000th I got was 287,117, though. (If you were using something like a Sieve of Erosthrates you would need an array of 287,117 flags, but you have no way of knowing that before you solve the problem.)
    Last edited by anon; 01-17-2007 at 05:26 PM.

  12. #12
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The 250000th prime is not 287117. That would mean something like 87% of all numbers between 1 and 287117 were prime, which clearly is not the case, since half of them are even numbers!


    Quzah.
    Hope is the first step on the road to disappointment.

  13. #13
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,005
    Quote Originally Posted by torqu3e
    It took 10 minutes on an AMD 64 BIT 2800 with 1 GB of Ram to get 250,000 primes.
    Unless you're a fast reader, wouldn't it serve you better to write to a file? You could probably just pipe the output of your original (and give you a further excuse to ditch getch) to a file and open it in an editor much more quickly.

    @Quzah: 25000/250000
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  14. #14
    Registered User
    Join Date
    Dec 2006
    Posts
    14
    anon, that algorithm finds some numbers known as pseudo primes, thats why you are getting so many primes in such a short range.

    Vart i will switch to "while(!kbhit());" instead of getch();

    If i use a[2147483647] for the array it says "Array size too large"
    If i use a[4294967294] for the array it says "Array must have atleast one element"

  15. #15
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Quote Originally Posted by torqu3e
    If i use a[2147483647] for the array it says "Array size too large"
    If i use a[4294967294] for the array it says "Array must have atleast one element"
    Seems to be explicit conversion of the array index to the int type
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. simple array of char array problem
    By cloudy in forum C++ Programming
    Replies: 5
    Last Post: 09-10-2006, 12:04 PM
  2. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  3. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  4. Help with an Array
    By omalleys in forum C Programming
    Replies: 1
    Last Post: 07-01-2002, 08:31 AM
  5. From stream/file to a string array problem
    By dradsws in forum C Programming
    Replies: 2
    Last Post: 10-01-2001, 06:24 PM