array of large size

[pooh1234qwerty]

why can't we take an array :- a[10000000]??
what is the alternative?

[Trentacle]

Why do you need an array that size?

How would you rewrite your program so that such a large array is not necessary?

[Schol-R-LEA]

In addition to Trentacle's questions, I would also ask, what compiler are you using, under what kind of system? The reason I ask is because, while a ten million item array is almost certainly excessive, it should be possible to declare and use one under a modern 32-bit or 64-bit compiler - I have no trouble declaring such an array under either Visual C++ 2010 Express or MinGW GCC 4.4.1 x86, for example, and I assume that Pelles C would be able to as well - but an older, 16-bit compiler almost certainly wouldn't be able to declare an array larger than 65535KiB total size.

Also, you fail to mention what it is an array of. Keep in mind that an int array would require more memory than a char array of the same size, for example.

As for alternatives, it would depend on the nature of the data being stored in the array. If it relatively sparse - that is to say, most of the values aren't being used, or are set to some default value - it may be possible to use a linked list to emulate a sparse array. If the data is in any way heirarchical, a tree or some other complex structure may be useful for it. If only part of the data is needed at any given point - which is generally the case - It may be possible to use a to keep part of the data on disk rather than having it all in memory; if it is both a tree structure and easily decomposed into in-memory and out-of-memory sections, a B-Tree would be a good method of organizing it.

I have a sneaking suspicion that these are homework questions, and that the instructor is assuming Turbo C as the compiler. The question simply wouldn't come up with a newer compiler, not if the PC is less than ten years old at any rate (most current systems can easily accomodate a 40MB data structure (if we're talking about 32-bit integers, just as an example), and probably do so on a regualr basis; any system with more than 64MiB of RAM should be able to, though it would probably need to page part of it out).

[Sokurenko]

alternative is malloc
you will locate it on heap instead of stack or calloc effect is same bot you haveto free it after and it can be dinamically changed during execution :)

[pooh1234qwerty]

ya right. it didnt give an error when i used calloc... so the reason why long int a[10000000] gave an error was my compiler.
well i needed a[10000000] to solve a prob that my father asked me. it was:-
a group of people need to pay tax in the following pattern:

in the first year  t[0] entered by user  then in the next s1 they need to pay 1unit more than the previous year. further, in the next s2 years they need to pay twice the amount paid last year. and thereafter they need to pay tax equal to the product of taxes paid in the last k years. You need to print out the tax paid in nth year.
so in this problem if n=10, then it gives very very large value. So we use modulo %100000007. But even after using all this... calloc and modulo, i wasn’t getting the correct result for n>s1+s2. My code is as follows:-
#include<stdio.h>
int main()
{
    int s,s1,s2,k,n,il,i,j,l,m;
    int a[3];
    long int *ptr;
    ptr=(long int*)calloc(n,sizeof(long int));
    scanf("%d",&s);
//il is for no. Of times the user wants to find t[n] for diff n
    for(il=0;il<s;il++)
    {
        scanf("%d",&ptr[0]);
        scanf("%d",&s1);
        scanf("%d",&s2);
        scanf("%d",&k);
        scanf("%d",&n);
        for(i=1;i<=s1;i++)
        ptr[i]=ptr[i-1]+1;
        for(j=(s1+1);j<(s1+s2);j++)
        ptr[j]=ptr[j-1]*2;
        for(l=(s1+s2);l<=n;l++)
        {
            ptr[l]=1;
            for(m=1;m<=k;m++)
            ptr[l]=ptr[l]*(ptr[l-m]);
        }
        a[il]=ptr[n-1]%100000007;
    }
    for(il=0;il<s;il++)
    printf("%d",a[il]);
    return 0;
}
This gave no error and gave correct result for n<s1+s2 only. Why??

[Schol-R-LEA]

I noticed a serious bug in the program: you are allocating ptr based on an uninitialized value for n, which means that the size of ptr could be nearly anything. You'll need to read in n first, then allocate ptr, and only after that should you read in the first element of ptr. This also means that you'll need to free() the buffer pointed to by ptr on each iteration of the outer loop.

Interestingly, I compiled and ran this (under Windows 7, MinGW GCC 4.4.1 with -Wall) and got dinged for not including <stdlib.h> (required for calloc()). Once I fixed that, I was able to get it to compile, but it would fail with a protection violation on this line:

scanf("%d",&ptr[0]);

I fixed the format string to

scanf("%ld", &ptr[0]);

and it read in correctly at that point.

Oh, and I would strongly recommend adding prompts for each input, so that it is clearer which value is getting set when. I know you know the program, but without some sort of clue, it would be easy to get lost if your entering several iterations.

    for(il=0; il<s; il++)
    {
        printf("n: ");
        scanf("%d",&n);

        ptr=(long int*)calloc(n, sizeof(long int));
        printf("t[0]: ");
        scanf("%ld", &ptr[0]);

        printf("s1: ");
        scanf("%d",&s1);

        printf("s2: ");
        scanf("%d",&s2);

        printf("k: ");
        scanf("%d",&k);

        /* and so on */

[pooh1234qwerty]

yes... my mistake.
bt still its nt working for n>=s1+s2. try out n=s1+s2.
or may be i m again doing sth wrong. well my modified code is:-

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int s,s1,s2,k,n,il,i,j,l,m;
    int a[3];
    long int *ptr;

    scanf("%d",&s);
    for(il=0;il<s;il++)
    {

        scanf("%d",&s1);
        scanf("%d",&s2);
        scanf("%d",&k);
        scanf("%d",&n);
        ptr=(long int*)calloc(n,sizeof(long int));
        scanf("%1d",&ptr[0]);
        for(i=1;i<=s1;i++)
        ptr[i]=ptr[i-1]+1;
        for(j=(s1+1);j<(s1+s2);j++)
        ptr[j]=ptr[j-1]*2;
        for(l=(s1+s2);l<=n;l++)
        {
            ptr[l]=1;
            for(m=1;m<=k;m++)
            ptr[l]=ptr[l]*(ptr[l-m]);
        }
        a[il]=ptr[n-1]%100000007;
        free(ptr);
    }
    for(il=0;il<s;il++)
    printf("%d",a[il]);
    return 0;
}   

my inputs were 1 2 2 4 6 1
the output should have been 432. bt its sth else.
also for 1 3 2 4 7 1
output should have been 1536. bt it is 18432.
i fail to understand why?
by the way why didnt it give me error msg although i had done such blunders like ptr... stdlib...earliar??

[Schol-R-LEA]

To address the last question first, it depends on which compiler you're using, and wether it is configured to catch all of these given issues. I have my compiler set to warn me about a lot of things which aren't, strictly speaking, errors in C, but which are nonetheless causes of bugs. Even with that, however, it didn't catch the problem with not having n initialized; I noticed it myself, when going through the code. As for the header issue, what it actually warned me of was that calloc() was not declared before use, and that the return value did not match the default; it took a bit of experience and familiarity with the standard library to recognize the cause of the problem.

Speaking of compiler differences: when I compile and run the code as given, I get a segfault. I tracked this down to the last of the for() loops, where you have the conditionals in the form

    for(l = (s1+s2); l<=n; l++)
    {
        ptr[l]=1;
        for(m=1; m < k; m++)
            ptr[l]=ptr[l]*(ptr[l-m]);
    }

The problem is that l (a very bad variable name, BTW - it can too easily be confused with 1 when reading the code) is being tested as less than or equal to n, which means that on the last loop, l equals n. This is a problem, because the indices of the array only go from 0 to n - 1. Thus, you are walking off the end of the array during the last iteration, something that should indeed cause a memory protection violation.

I find it worrying that this isn't happening for you. I repeat my earlier question: what compiler are you using? If it is Turbo C or Turbo C++, stop right there and get rid of it, if you have any choice in the matter. The compiler is more than 20 years old, and is for a system that lacked memory protection, among other things. Both the operating systems and the C language have moved on since then. Unless you have some overriding need to use that compiler (e.g., it's what you school is teaching with), you don't want to use something so badly out of date; pick up a free copy of Pelles C, or Code::Blocks, or even Visual C++ Express, any of which will give you the full power of modern 32-bit and 64-bit systems.

[pooh1234qwerty]

actually i dont knw which compiler it is... i just downloaded coz it was free... its named cfree version 4.0

[Schol-R-LEA]

OK, I just looked into CFree a bit, and found out that the default compiler for CFree Standard 4.0 is GCC for MinGW, version 2.95, a version which dates from around 2002 if I am not mistaken. That's a whole lot better than what I was worried about (ten years newer and after the C99 and C++98 standards), but still quite old.

Since CFree is a general-purpose C/C++ Integrated Development Environment that is not specific to any given compiler, you should be able to install and use a newer version of the MinGW port of GCC without any trouble, which would get you (almost) up to date with the latest version of GCC.

[pooh1234qwerty]

so the prob is with my compiler....i will download visual studio now. by the way i didnt understand what u said. variable l runs from s1+s2 to n which is less than 0 to n-1? that array is from 1 to n and i m running it from s1+s2(which is >1) to n. then how am i waking off the end of the array? i didnt get that point of urs.

[Sokurenko]

@pooh1234qwerty
dont use questions like that, use printf to make shure :) make some test array to test and make it smaller maybe and if it will work in smaller it will work in bigger.
You wrote something , you should understand what you wrote, assumptions is not very good thing in programming and it's not about compiler.
To make code more readable for you and other people name variables to something meaningfull like Schol sayed i dont want to read code where something is l then something does s1 + s2 what is that and no comment
to normal human s1 doesent mean anything
hope this will help you to debug your code :) if no understand comment every line explay what it is and print results out till you have something that you cant explayn and it doesent work

[Schol-R-LEA]

I think I see the problem here; you are making an understandable but incorrect assumption about how arrays work in C. In C, arrays do not start with the element one, but rather with element zero. Conversely, the last element of an array is not the size of the array, but the size of the array minus one. To put it another way, the elements of an array declared int a[4]; would be a[0], a[1], a[2], and a[3]. There is no a[4] in a four-element array in C; the 4 in the declaration is the size of the array, not the index of the last element.

Thus, the correct way to walk through an array is

int i;
int a[10];
for(i = 0; i < 10; i++)
{
    // do something here
}

There are good, if somewhat obscure, technical and mathematical reasons for zero-indexed arrays; this blog article covers one line of reasoning on the subject, and the Wikipedia article on Zero-Based Numbering gives an overview of a few more. Suffice it to say that, except for a few older languages, almost all programming languages use zero-indexed arrays, for better or for worse.

As for the compiler, you might find Visual C++ Express easier to use than CFree, I'm not sure. However, since CFree will work with the newest version of MinGW, the easier solution is to download and install MinGW, then set CFree to use the newer version of the compiler. There's no real need to stop using CFree, if that's what you are most comfortable with.

[pooh1234qwerty]

then what should i write instead of that last for loop?

[Schol-R-LEA]

Actually, let's start over with new variable names, just to make it clearer, and add some test prints to show what is happening at each stage. I did this and was able to get the program working, in fact:

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int iterations, initial_tax_years, increased_tax_years, product_tax, total_years;
    int i, j, k;
    long int* total_tax;
    long int *annual_tax;

    printf("How many iterations to test: ");
    scanf("%d",&iterations);
    total_tax = (long int) calloc(iterations, sizeof(long int));

    for(i = 0; i < iterations; i++)
    {
        printf("How many years for the first tax increase period: ");
        scanf("%d",&initial_tax_years);
        printf("How many years for the second tax increase period: ");
        scanf("%d",&increased_tax_years);
        printf("How many years for the final tax increase period: ");
        scanf("%d",&product_tax);
        printf("How many total years to review: ");
        scanf("%d",&total_years);
        annual_tax = (long int*)calloc(total_years, sizeof(long int));
        printf("How much was the initial tax payment: ");
        scanf("%ld", &annual_tax[0]);

        /* print out the initial state */
        printf("\n\nyear 0 == %d\n", annual_tax[0]);

        for(j = 1; j <= initial_tax_years; j++)
        {
            annual_tax[j] = annual_tax[j - 1] + 1;
            printf("year %d == %d\n", j, annual_tax[j]);
        }
            annual_tax[j] = annual_tax[j - 1] + 1;

        for(j = initial_tax_years + 1; j <= (initial_tax_years + increased_tax_years); j++)
        {
            annual_tax[j] = annual_tax[j - 1] * 2;
            printf("year %d == %d\n", j, annual_tax[j]);
        }

        for(j = (initial_tax_years + increased_tax_years + 1); j < total_years; j++)
        {
            annual_tax[j] = 1;

            for(k = 1; k <= product_tax; k++)
            {
                annual_tax[j] = annual_tax[j] * (annual_tax[j - k]);
            }

            printf("year %d == %d\n", j, annual_tax[j]);
        }

        total_tax[i] = annual_tax[total_years - 1] % 100000007;
        free(annual_tax);
    }

    for(i=0; i < iterations; i++)
        printf("total tax of first iteration == %d\n", total_tax[i]);
    return 0;
}

The major problems were actually with the offsets for the years, as it happens; some years were getting repeated, other skipped.

[pooh1234qwerty]

yes i got it. finally. thankyou sir. u r great.