BigInt

This is a discussion on BigInt within the C Programming forums, part of the General Programming Boards category; I am doing the classic bigint problem adding and subtracting long integers via a linked list. I am having problems ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    36

    Exclamation BigInt

    I am doing the classic bigint problem adding and subtracting long integers via a linked list. I am having problems getting each digit individually into a linked list. Because the list goes from L>R and we add/subtract from R>L, I have to reverse them, which works fine. But now my program crashes and I can't figure out why nor can I figure out how to get each digit individually into a separate node of the list. I know that I need a loop somewhere inside my function (right?) but I just can't figure out the syntax at all. Can someone please point me in the right direction?

    Code:
    #include <stdio.h>
    #include <string.h>
    
    struct integer
    {
        int digit;
        struct integer *next;
    };
    
    FILE* fin;
    FILE* fout;
    
    struct integer* read_integer(char* stringInt);
    void print(struct integer *p);
    struct integer* add(struct integer *p, struct integer *q);
    struct integer* subtract(struct integer *p, struct integer *q);
    int compare(struct integer *p, struct integer *q);
    
    int main()
    {
        char string1[200], string2[200];
        char temp1, temp2;
        
        int i, j, k;
        int length1, length2;
        int num_operations;
        int operation;
        
        struct integer* list1 = NULL;
        struct integer* list2 = NULL;
    //    struct integer* p;
    //    struct integer* q;
        
        //Open the input file
        fin = fopen("bigint.txt", "r");
        if (fin == NULL)
            printf("File failed to open for reading.\n");
    
        //Open the output file        
        fout = fopen("out.txt", "w");
        if (fout == NULL)
            printf("File failed to open for writing.\n");
        
        //The first line will contain a single positive integer representing the 
        //number of operations to carry out    
        fscanf(fin, "%d ", &num_operations);
        
        //Run the following loop for each line of numbers in the input file,
        //indicated by the num_operations variable
        for (i = 0; i < num_operations; i++)
        {
            //First number on the line tells which operation to perform
            fscanf(fin, "%d ", &operation);
            
            //Read in the number for the first string in the list
            fscanf(fin, "%s ", &string1);
            printf("This is string1: %s\n", string1); //Debug
            
            //Read in the number for the second string in the list
            fscanf(fin, "%s", &string2);
            printf("This is string2: %s\n", string2); //Debug
            
            length1 = strlen(string1) - 1; //Length of the first string
            length2 = strlen(string2) - 1; //Length of the second string
            
            //First big int in reverse
            for(j = 0; j < strlen(string1)/2; j++)
            {
                temp1 = string1[j];
                string1[j] = string1[length1];
                string1[length1--] = temp1;
            }
            printf("\nThis is string1 in reverse: %s\n", string1); //Debug
            
            //Second big in in reverse
            for(k = 0; k < strlen(string2)/2; k++)
            {
                temp2 = string2[k];
                string2[k] = string2[length2];
                string2[length2--] = temp2;
            }
            printf("This is string2 in reverse: %s\n\n", string2); //Debug 
            
            //Send the reversed strings to the read function. This will put them
            //in a linked list
            list1 = read_integer(string1);
            list2 = read_integer(string2);
            
            if(operation == 1) //add
            {
                printf("\nWe are adding these\n"); //Debug
                add(list1, list2);
            }
            else if (operation == 2) //subtract
            {
                printf("\nWe are subtracting these\n"); //Debug
                subtract(list1, list2);
            }
        }
        
        fclose(fin);
        fclose(fout);
        system("PAUSE");
        return 0;   
    }
    
    // Preconditions: the first parameter is a string that only contains digits, 
    // doesn't start with 0, and is 200 or fewer characters long.
    // Postconditions: The function will read the digits of the large integer 
    // character by character, convert them into integers and place them in
    // nodes of a linked list. The pointer to the head of the list is returned.
    struct integer* read_integer(char* stringInt)
    {
        int i = 0;
        int length;    
        length = strlen(stringInt);
        
        struct integer *bigint;
        struct integer* localString = (struct integer *) malloc(length*sizeof(struct integer));
        struct integer* help_ptr = NULL;
    
        for(i = 0; i < length; i++)
        {
            bigint[i].digit = stringInt[i] - '0';
            bigint->next = help_ptr;
            help_ptr = (struct integer*)&bigint[i].digit;
            printf("%d", bigint[i].digit); //Debug
        }          
        return bigint;
    }
    
    //Preconditions: p is a pointer to a big integer, stored in reverse order, 
    //least to most significant digit, with no leading zeros.
    //Postconditions: The big integer pointed to by p is printed out.
    void print(struct integer *p)
    {
        
    }
    
    //Preconditions: p and q are pointers to big integers, stored in reverse order, 
    //least to most significant digit, with no leading zeros.
    //Postconditions: A new big integer is created that stores the sum of the 
    // integers pointed to by p and q and a pointer to it is returned.
    struct integer* add(struct integer *p, struct integer *q)
    {
        
    }
    
    //Preconditions: p and q are pointers to big integers, stored in reverse order, 
    // least to most significant digit, with no leading zeros.
    //Postconditions: A new big integer is created that stores the absolute value 
    // of the difference between the two and a pointer to this is returned.
    struct integer* subtract(struct integer *p, struct integer *q)
    {
        
    }
    
    //Preconditions: Both parameters of the function are pointers to struct integer.
    //Postconditions: The function compares the digits of two numbers and returns:
    // -1 if the first number is smaller than the second,
    // 0 if the first number is equal to the second number,
    // 1 if the first number is greater than the second.
    int compare(struct integer *p, struct integer *q)
    {
        
    }

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    Why are you using a linked list and not just an array?! Are you afraid that you don't have a large enough block of memory!?
    Devoted my life to programming...

  3. #3
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    By array i mean a vector of course...
    Devoted my life to programming...

  4. #4
    Registered User
    Join Date
    Jun 2010
    Posts
    36
    The assignment requires the use of a linked list

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,639
    Um, sorry, but the glaring obvious question is why in the heck are you are not efficiently utilizing the binary representation of the integer? I mean, really - linked lists?!
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  6. #6
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    I believe linked lists are a mistake because an data type is presumed to be a continues block of memory.
    Devoted my life to programming...

  7. #7
    Registered User
    Join Date
    Jun 2010
    Posts
    36
    ok u all are going wayyyy over my head here. can we keep it to simple terms please?

  8. #8
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    Sure. When using an array, all of its elements are one next to the other. Linked list on the other hand has its elements scattered all over RAM. That's what i meant.
    Devoted my life to programming...

  9. #9
    Registered User
    Join Date
    Jun 2010
    Posts
    36
    Oh ok. I understand and yes this is true. However it is the requirements of the assignment.

  10. #10
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    If you're using an int to store one decimal digit only, there'll be a lot of RAM waste. Does your teacher really want you to store every digit separately?! Does he want a number that keeps adapting its size everytime it gets bigger or smaller?!

    No!! A data type like BigNum must remain in one size after it's created! Another issue is: How will you represent negative numbers?
    Devoted my life to programming...

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by lostandconfused
    But now my program crashes and I can't figure out why nor can I figure out how to get each digit individually into a separate node of the list. I know that I need a loop somewhere inside my function (right?) but I just can't figure out the syntax at all.
    To help figure out where the crash occurs, you can set breakpoints and step through with your debugger. The crash may well be due to something you did much earlier on, but at least it can give you a starting point to work with.

    As for the syntax: you seemed to have managed the for loops quite well, so I am not sure why you consider this a problem.

    Quote Originally Posted by lostandconfused
    can we keep it to simple terms please?
    If I read him correctly, Sebastiani's point is basically that you should be storing more than just a (base ten) digit in an int. Of course, if your instructor's requirement is that you are supposed to store exactly one digit in each node of the linked list, then so be it. You could save some space by having an unsigned char member instead, but you do not need to worry too much about that.

    Quote Originally Posted by Sipher
    I believe linked lists are a mistake because an data type is presumed to be a continues block of memory.
    Linked lists might not be a terribly good choice here, but your reasoning sounds rather flawed. What exactly are you trying to say?

    Quote Originally Posted by Sipher
    A data type like BigNum must remain in one size after it's created!
    Eh, that is not true, at least not in the way that you seem to be intending.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    An int type is like a char[4] array ( basically ). I believe all numerical types must follow the same "rule".

    Scratch the second, i got it wrong...
    Devoted my life to programming...

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by Sipher
    An int type is like a char[4] array ( basically ). I believe all numerical types must follow the same "rule".
    Sorry, I do not see the relationship through that example. What is this rule that you refer to?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    1,616
    The rule of Continuality!! ( I wish i got the word right )
    Devoted my life to programming...

  15. #15
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Quote Originally Posted by Sipher
    The rule of Continuality!
    So what is that rule about? Forget it, I am fairly certain that it does not apply. The nodes of a linked list can be accessed in a continuous fashion. Sure, they might not be stored contiguously, but that does not disqualify a linked list from being used to store the digits of an arbitrary precision integer, and thus implement a bigint data type.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BigInt division and modulus
    By User Name: in forum C++ Programming
    Replies: 4
    Last Post: 09-11-2010, 03:54 PM
  2. Help with structures and classes
    By jdcollins in forum C++ Programming
    Replies: 1
    Last Post: 11-14-2009, 04:07 PM
  3. HugeInt (BigInt) optimization
    By LuckY in forum C++ Programming
    Replies: 2
    Last Post: 11-16-2004, 10:44 AM
  4. BigInt Linked List Long Division
    By abyssknight in forum C Programming
    Replies: 5
    Last Post: 04-01-2004, 06:02 PM
  5. bigInt help
    By noob2c in forum C++ Programming
    Replies: 14
    Last Post: 10-10-2003, 08:18 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21