Qfyilyi

I was asked to translate this pseudo code into a C program:

rep := 0

while A not empty:

    B := 

    for x in A, y in A:

        if x != y: append absolute_value(x - y) to B

    A := B

    rep := rep + 1

and I end up with this:

int iterateIt(int a_count, int* a) {

    unsigned long long i, j, k;

    unsigned long long count = a_count;



    for( i = 1 ; i < a_count ; i++ )

        count *= count-1;



    int *b = (int *) malloc(count * sizeof(int));

    count = 0;

    k = 0;

    for( i = 0 ; i < a_count ; i++ ){

        for( j = i ; j < a_count ; j++ ){

            if(a[i] != a[j]){

                b[k] = abs(a[i] - a[j]);

                k++;

            }

        }

    }



    if( k > 0){

        return 1 + iterateIt(k, b);

    }

    free(b);

    return 1;

}

I used recursion to return the number of iteration of the algorithm. Practically I take the difference between any two different objects of A and put the absolute value in B, on which I recur.
For simple input I get the correct result but I don't understand why for input like:
16 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768
or 4 1 352 9483 50000
(the first number is the number of element of A)

I get a segmentation fault error.

Thank you for your help

I think your count is wrong. Your second iteration is already humongous.

#include <stdio.h>

#include <stdlib.h>



size_t total_allocated = 0;



int iterateIt(int a_count, int* a) {

    unsigned long long i, j, k;

    unsigned long long count = a_count;



    for( i = 1 ; i < a_count ; i++ )

        count *= count-1;



    size_t size = count * sizeof(int);

    printf("Allocating %llu ints: %llu bytesn", count, (unsigned long long)size);

    total_allocated += size;

    printf("Total allocated: %llu bytesn", (unsigned long long)total_allocated);

    int *b = (int *) malloc(count * sizeof(int));

    count = 0;

    k = 0;

    for( i = 0 ; i < a_count ; i++ ){

        for( j = i ; j < a_count ; j++ ){

            if(a[i] != a[j]){

                b[k] = abs(a[i] - a[j]);

                k++;

            }

        }

    }



    if( k > 0){

        return 1 + iterateIt(k, b);

    }

    free(b);

    return 1;

}



int main (void)

{

    iterateIt(4, (int[4]){1,352,9483,50000});

    return 0;

}

Result:

Allocating 17292 ints: 69168 bytes

Total allocated: 69168 bytes

Allocating 12550317587327992670 ints: 13307782201892867448 bytes

Total allocated: 13307782201892936616 bytes

First consider this line:

return 1 + iterateIt(k, b);

The b array never gets freed on this return but if k is zero, it does. Let's rewrite this code to clean it up a bit:

#include <stdio.h>

#include <stdlib.h>



unsigned iterateIt(size_t a_count, int *a) {



    unsigned rep = 1;



    int *b = calloc(a_count * a_count, sizeof(int));



    size_t k = 0;



    for (size_t i = 0; i < a_count; i++) {

        for (size_t j = i + 1; j < a_count; j++) {

            if (a[i] != a[j]) {

                b[k++] = abs(a[i] - a[j]);

            }

        }

    }



    if (k > 0) {

        rep += iterateIt(k, b);

    }



    free(b);



    return rep;

}



int main() {



    int x = {1, 324, 54};



    printf("%un", iterateIt(sizeof(x) / sizeof(int), x));



    return 0;

}

Watching the value of a_count, the program tries to allocate too much memory and fails.

UPDATE

Since the two halves of the matrix end up identical, I fixed the above code to do what the OP did, just process 1/2 the matrix, i.e. j starts at i + 1 since the two halves end up identical. I also ignore the diagonal as it's always zeros. Then the code completes for the three numbers in my example code but blows up again when I increase the array to four values.

I believe the recursive nature of the OP's solution is elegant and a non-issue but just to confirm, here's an iterative solution that fails to perform and not due to lack of stack memory:

unsigned iterateIt(size_t a_count, int *a) {



    unsigned rep = 1;



    bool first_time = true;



    while (true) {



        int *b = calloc((a_count * a_count) / 2, sizeof(int));



        if (b == NULL) {

            perror("calloc failed!");

            exit(1);

        }



        size_t b_count = 0;



        for (size_t i = 0; i < a_count; i++) {

            for (size_t j = i + 1; j < a_count; j++) {

                if (a[i] != a[j]) {

                    b[b_count ++] = abs(a[i] - a[j]);

                }

            }

        }



        if (b_count == 0) {

            free(b);

            break;

        }



        if (first_time) {

            first_time = false;

        } else {

            free(a);

        }



        a = b;

        a_count = b_count;



        rep++;

    }



    return rep;

}