CODEWITHSUNDEEP
carrays
Joseph Wagner
Joseph Wagner

Reputation: 323

Filling a large array instantly - C

Programming in C (not c++, etc..);

The program is supposed to take two different numbers (1 to 1000) as input and tries to find their highest like multiple on a scale from 1 to 1.1 billion. This is a class assignment and the example gives the numbers 2 and 3. The highest like number the two inputs can reach before going over 1100000000 is 1099999998.

The way I've tried to handle this is by taking the two inputs, allocating two arrays and giving them different sizes based on the quotient of 1.1 billion and the numbers.

The next step was to fill each array index with the product of one of the numbers and the iteration. This is where I'm having trouble. If I choose a very large number such as 999, the program seems to handle filling an array with values. If I choose a small number such as 3, the size of the array is too big and the program crashes.

#include<stdio.h>
#include <math.h>
#include<malloc.h>

void fillArray(long int dNum1, long int dNum2, long int num1, long int num2) {
long int* firstSet = malloc(dNum1 * sizeof(int));
long int* secondSet = malloc(dNum2 * sizeof(int));
long int bigNumber;

int i, j;

for (i = 0; i < dNum1; i++){
    firstSet[i] = num1 * i;
    printf("first set %d \n", firstSet[i]);
}

for (j = 0; j < dNum2; j++){
    secondSet[j] = num2 * j;
    printf("second set %d \n", secondSet[j]);
}

free(firstSet);
free(secondSet);
}


void main(){

long int firstNum, secondNum, divisionNum1, divisionNum2;

printf("Enter first jump number \(1 to 1000\): ");
scanf("%i", &firstNum);

printf("Enter second jump number \(1 to 1000\): ");
scanf("%i", &secondNum);

divisionNum1 = 1100000000 / firstNum;
divisionNum2 = 1100000000 / secondNum;

fillArray(divisionNum1, divisionNum2, firstNum, secondNum);

}

How does one fill an array with a potential size of 1.1 billion with a for loop without crashing the program?

Upvotes: 1

Views: 577

Answers (1)

M.M
M.M

Reputation: 141628

If you are on an LP64 system then the problem likely comes from only allocating elements of size sizeof(int) bytes (4) but then expecting the array to contain enough 8-byte elements.

If you are using a 32-bit compiler where int and long int are both 32-bit, then a likely cause of the problem would come from:

malloc(dNum2 * sizeof(int));

If the multiplication overflows SIZE_MAX (which is 4 gigabytes on the 32-bit system) then it will actually wrap around to zero and allocate a small amount; and then your loop will run off the end of the allocated space.

To detect this situation, and also fix the type mismatch bug by using sizeof in the recommended way, and detect allocation failure:

if ( dnum1 >= SIZE_MAX / sizeof *firstSet 
  || dnum2 >= SIZE_MAX / sizeof *secondSet )
{
    fprintf(stderr, "Allocation too big.\n");
    exit(EXIT_FAILURE);
}

long int* firstSet = malloc(dNum1 * sizeof *firstSet);
long int* secondSet = malloc(dNum2 * sizeof *secondSet);

if ( !firstSet || !secondSet )
{
    fprintf(stderr, "Not enough system memory available.\n");
    exit(EXIT_FAILURE);
}

Finally, even if this all succeeds then another possible cause of a crash is due to lazy allocation: many operating systems will return a valid pointer but not actually allocate memory yet. Then when you go to use the memory they will allocate some virtual memory. If there is not enough virtual memory then the OS kills the process.

Upvotes: 3

Related Questions