#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0

    How to store big values in C


    Hello,

    the inv_count variable in the functions will be storing a very big number:9999999999. As such, I decided to use unsigned long long data type. Unfortunately, there is an error:


    main.c:45:20: error: conflicting types for 'mergeSort'
    main.c:34:46: note: previous implicit declaration of 'mergeSort' was here
    main.c:52:20: error: conflicting types for 'mergesort'
    main.c:48:12: note: previous implicit declaration of 'mergesort' was here
    main.c:74:21: error: conflicting types for 'merge'
    main.c:68:18: note: previous implicit declaration of 'merge' was here




    Code:
    
    int main(){
    //arr already declared and contained the integers
    //call the mergeSort
     printf(" inversions are: %llu \n", mergeSort(arr, count));
     return 0;
    }
    
    
    unsigned long long mergeSort(int arr[], int array_size)
    {
        int *temp = (int *)malloc(sizeof(int)*array_size);
        return mergesort(arr, temp, 0, array_size - 1);
    }
      
    
    unsigned long long mergesort(int arr[], int temp[], int left, int right) 
    {
    int mid;
    unsigned long long inv_count = 0ULL;
      if (right > left)
      {
        /* Divide the array into two parts and call _mergeSortAndCountInv()
           for each of the parts */
        mid = (right + left)/2;
      
        /* Inversion count will be sum of inversions in left-part, right-part
          and number of inversions in merging */
        inv_count  = mergesort(arr, temp, left, mid);
        inv_count += mergesort(arr, temp, mid+1, right);
      
        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid+1, right);
      }
      return inv_count;
    
    }
        
    unsigned long long  merge(int arr[],  int temp[], int left, int mid, int right)
    {
      int i, j, k;
      unsigned long long  inv_count = 0ULL;
      
      i = left; /* i is index for left subarray*/
      j = mid;  /* i is index for right subarray*/
      k = left; /* i is index for resultant merged subarray*/
      while ((i <= mid - 1) && (j <= right))
      {
        if (arr[i] <= arr[j])
        {
          temp[k++] = arr[i++];
        }
        else
        {
          temp[k++] = arr[j++];
      
         /*this is tricky -- see above explanation/diagram for merge()*/
          //inv_count = inv_count + (mid - i);
          inv_count =  inv_count+ (mid - i);
        }
      }
      
      /* Copy the remaining elements of left subarray
       (if there are any) to temp*/
      while (i <= mid - 1)
        temp[k++] = arr[i++];
      
      /* Copy the remaining elements of right subarray
       (if there are any) to temp*/
      while (j <= right)
        temp[k++] = arr[j++];
      
      /*Copy back the merged elements to original array*/
      for (i=left; i <= right; i++)
        arr[i] = temp[i];
      
      return inv_count;
    }
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2009
    Posts
    45
    Rep Power
    8
    You need to provide prototypes of mergesort and mergeSort functions before main function.
    Code:
    unsigned long long mergeSort(int arr[], int array_size);
    unsigned long long mergesort(int arr[], int temp[], int left, int right);
    Differing functions names only by lower- or upper-case of letters is not a good practice - easy to confuse.
    mergeSort
    mergesort
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0
    Originally Posted by DRK82
    You need to provide prototypes of mergesort and mergeSort functions before main function.
    Code:
    unsigned long long mergeSort(int arr[], int array_size);
    unsigned long long mergesort(int arr[], int temp[], int left, int right);
    Differing functions names only by lower- or upper-case of letters is not a good practice - easy to confuse.
    mergeSort
    mergesort
    So, are you suggesting that the reason for this error is that the computer was confusing mergeSort with mergesort? I accept if you say humans but the computer?
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2009
    Posts
    45
    Rep Power
    8
    Originally Posted by help_desk
    So, are you suggesting that the reason for this error is that the computer was confusing mergeSort with mergesort? I accept if you say humans but the computer?
    Look again at my post. It's divided into 2 parts.

    First part is a solution to your noobie problem (in addition: merge function also needs a prototype).

    Second part is an advice which I gave you. I can see that you have very little experience in programming as you don't know what a function prototype is or where to provide it.
    Last edited by DRK82; July 3rd, 2013 at 05:00 AM.
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,174
    Rep Power
    2222
    Originally Posted by help_desk
    So, are you suggesting that the reason for this error is that the computer was confusing mergeSort with mergesort? I accept if you say humans but the computer?
    No, the compiler was confused because you neglected to tell it anything about those two functions! That is what the prototypes are for, as you have been told.

    Like the experienced programmers here, the compiler cannot read your mind! You have to provide it with the information that it needs.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    3
    Rep Power
    0
    As it's not been said before:

    If you don't want to use prototypes, you can also declare the functions before the main method.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0
    Hello guys,

    Well, even after adding the prototypes, I still get the overflow. here is my code with the prototypes..

    Code:
    //header files added here..
    unsigned long long sortAlgo(int arr[], int array_size);
    unsigned long long mergesort(int arr[], int temp[], int left, int right);
    unsigned long long  merge(int arr[],  int temp[], int left, int mid, int right);
    
    
    
    #define MAX_VALUE 100000
    int main()
    {
       FILE *fp;
        char buff[255]; // You're not storing the whole file, just one line at a time
        int buffInt[MAX_VALUE];
        int i = 0;
        int count;
    
        fp = fopen("input.txt", "r");
        if( fp == NULL )
            perror("File failed to open");
        else
        {
            while ( i <=100000 && fgets(buff, 255, fp) != NULL )
            {
                buffInt[i] = atoi(buff); //important line..
                i++;
             //printf("%s", buff);
            }
            fclose(fp);
            count = i;
            printf("%d\n", count);
            printf("\n");
            for (i=0; i<count; i++)
                printf("%d:%d\n", i+1,buffInt[i]);
        }      
          
     printf(" Number of inversions are %d \n", sortAlgo(buffInt, count));
    
    return 0;
     
    }
    
    
    unsigned long long sortAlgo(int arr[], int array_size)
    {
        int *temp = (int *)malloc(sizeof(int)*array_size);
        return mergesort(arr, temp, 0, array_size - 1);
    }
      
    
    unsigned long long mergesort(int arr[], int temp[], int left, int right) 
    {
    int mid;
    unsigned long long inv_count = 0ULL;
      if (right > left)
      {
        /* Divide the array into two parts and call _mergeSortAndCountInv()
           for each of the parts */
        mid = (right + left)/2;
      
        /* Inversion count will be sum of inversions in left-part, right-part
          and number of inversions in merging */
        inv_count  = mergesort(arr, temp, left, mid);
        inv_count += mergesort(arr, temp, mid+1, right);
      
        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid+1, right);
      }
      return inv_count;
    
    }
        
    unsigned long long  merge(int arr[],  int temp[], int left, int mid, int right)
    {
      int i, j, k;
      unsigned long long  inv_count = 0ULL;
      
      i = left; /* i is index for left subarray*/
      j = mid;  /* i is index for right subarray*/
      k = left; /* i is index for resultant merged subarray*/
      while ((i <= mid - 1) && (j <= right))
      {
        if (arr[i] <= arr[j])
        {
          temp[k++] = arr[i++];
        }
        else
        {
          temp[k++] = arr[j++];
      
         /*this is tricky -- see above explanation/diagram for merge()*/
          //inv_count = inv_count + (mid - i);
          inv_count =  inv_count+ (mid - i);
        }
      }
      
      /* Copy the remaining elements of left subarray
       (if there are any) to temp*/
      while (i <= mid - 1)
        temp[k++] = arr[i++];
      
      /* Copy the remaining elements of right subarray
       (if there are any) to temp*/
      while (j <= right)
        temp[k++] = arr[j++];
      
      /*Copy back the merged elements to original array*/
      for (i=left; i <= right; i++)
        arr[i] = temp[i];
      
      return inv_count;
    }
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0
    Originally Posted by help_desk
    Hello guys,

    Well, even after adding the prototypes, I still get the overflow. here is my code with the prototypes..

    Code:
    //header files added here..
    unsigned long long sortAlgo(int arr[], int array_size);
    unsigned long long mergesort(int arr[], int temp[], int left, int right);
    unsigned long long  merge(int arr[],  int temp[], int left, int mid, int right);
    
    
    
    #define MAX_VALUE 100000
    int main()
    {
       FILE *fp;
        char buff[255]; // You're not storing the whole file, just one line at a time
        int buffInt[MAX_VALUE];
        int i = 0;
        int count;
    
        fp = fopen("input.txt", "r");
        if( fp == NULL )
            perror("File failed to open");
        else
        {
            while ( i <=100000 && fgets(buff, 255, fp) != NULL )
            {
                buffInt[i] = atoi(buff); //important line..
                i++;
             //printf("%s", buff);
            }
            fclose(fp);
            count = i;
            printf("%d\n", count);
            printf("\n");
            for (i=0; i<count; i++)
                printf("%d:%d\n", i+1,buffInt[i]);
        }      
          
     printf(" Number of inversions are %d \n", sortAlgo(buffInt, count));
    
    return 0;
     
    }
    
    
    unsigned long long sortAlgo(int arr[], int array_size)
    {
        int *temp = (int *)malloc(sizeof(int)*array_size);
        return mergesort(arr, temp, 0, array_size - 1);
    }
      
    
    unsigned long long mergesort(int arr[], int temp[], int left, int right) 
    {
    int mid;
    unsigned long long inv_count = 0ULL;
      if (right > left)
      {
        /* Divide the array into two parts and call _mergeSortAndCountInv()
           for each of the parts */
        mid = (right + left)/2;
      
        /* Inversion count will be sum of inversions in left-part, right-part
          and number of inversions in merging */
        inv_count  = mergesort(arr, temp, left, mid);
        inv_count += mergesort(arr, temp, mid+1, right);
      
        /*Merge the two parts*/
        inv_count += merge(arr, temp, left, mid+1, right);
      }
      return inv_count;
    
    }
        
    unsigned long long  merge(int arr[],  int temp[], int left, int mid, int right)
    {
      int i, j, k;
      unsigned long long  inv_count = 0ULL;
      
      i = left; /* i is index for left subarray*/
      j = mid;  /* i is index for right subarray*/
      k = left; /* i is index for resultant merged subarray*/
      while ((i <= mid - 1) && (j <= right))
      {
        if (arr[i] <= arr[j])
        {
          temp[k++] = arr[i++];
        }
        else
        {
          temp[k++] = arr[j++];
      
         /*this is tricky -- see above explanation/diagram for merge()*/
          //inv_count = inv_count + (mid - i);
          inv_count =  inv_count+ (mid - i);
        }
      }
      
      /* Copy the remaining elements of left subarray
       (if there are any) to temp*/
      while (i <= mid - 1)
        temp[k++] = arr[i++];
      
      /* Copy the remaining elements of right subarray
       (if there are any) to temp*/
      while (j <= right)
        temp[k++] = arr[j++];
      
      /*Copy back the merged elements to original array*/
      for (i=left; i <= right; i++)
        arr[i] = temp[i];
      
      return inv_count;
    }

    THANKS ALOT GUYS. I FIGURED OUT IN THE END WHAT THE PROBLEM WAS ALL ALONG. I REALLY APPRECIATE YOUR TIME AND BELIEVE ME, IT WASN'T IN VAIN.
  16. #9
  17. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,174
    Rep Power
    2222
    Why are you running a broken program?
    C:TEST\help_desk>gcc -Wall ms2.c
    ms2.c: In function `main':
    ms2.c:39: warning: int format, different type arg (arg 2)

    C:TEST\help_desk>
    Warnings tell you that there's something wrong with your program. Never ignore warnings!

    In this case:
    printf(" Number of inversions are %d \n", sortAlgo(buffInt, count));
    "%d" is for int, whereas sortAlgo returns long long int. Use the right format specifier. Refer to the documentation for printf for more information.

    And why aren't you posting a complete program as you did elsewhere? And what OS and compiler are you using?
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    14
    Rep Power
    0
    Originally Posted by dwise1_aol
    Why are you running a broken program?

    Warnings tell you that there's something wrong with your program. Never ignore warnings!

    In this case:
    printf(" Number of inversions are %d \n", sortAlgo(buffInt, count));
    "%d" is for int, whereas sortAlgo returns long long int. Use the right format specifier. Refer to the documentation for printf for more information.

    And why aren't you posting a complete program as you did elsewhere? And what OS and compiler are you using?
    Hello, I got it resolved now. I said that in my last post. It was a minor mistake that has held me down for the past 3 hours. The one you rightly pointed out : "%d" instead of "%llu"
    Anyways, I got it resolved now. Thanks alot for your time specifically. God bless you.

IMN logo majestic logo threadwatch logo seochat tools logo