Thread: BigInt Linked List Long Division

  1. #1
    CS Student
    Join Date
    Mar 2004
    Posts
    4

    Exclamation BigInt Linked List Long Division

    This is what I have to do by Sunday:
    http://www.cs.ucf.edu/courses/cop350...ssignment4.doc

    Basically, the assignment is to read in two large numbers into linked lists of digits, and then divide the two to get a remainder and quotient.

    Currently I have code that reads the numbers from the file and into two linked lists of digits. Other than that my mind is just.. blank. I know I have to long divide, but I cannot seem to figure out how to do that in code.

    I've spent the last 3 days hacking away at this with no avail. I've sifted through every known code database trying to find an example, with again, no avail. I realize what needs to be done is subtraction from the front of the bigger number, however, coding this seems quite the challenge.

    If anyone would be willing to explain this to me in pseudo code, or really in any way at all, I would be very grateful.

    Here is my current file IO code with a function to print the lists:

    Code:
    #include <stdio.h>
    
    typedef struct node
    {
        int digit;
        struct node *next;
    } listnode;
    
    //function prototypes
    void printlist(listnode* list);
    
    int main(){
    
        char loc[64];
        int listAcnt = 0;
        int listBcnt = 0;
        char c;
        listnode* listA = NULL;
        listnode* listB = NULL;
        listnode* result = NULL;
        listnode* pCur = NULL;
        listnode* newnode = NULL;
        FILE *Fp;
    
        printf("Enter the name of the file containing the numbers\n");
    	scanf("%s", loc);
    	
    	Fp = fopen(loc, "r");		// Open the file
    	
        if(Fp==NULL) {                                  //check if not valid filename
            printf("Error: can't open file.\n");
            return -1;     //error so quit
          }
    	else {
    		c = fgetc(Fp); //read first char of listA
    		while(c != '\n' && c != EOF) {							// Read until new line or EOF
    			newnode = (listnode*)(malloc(sizeof(listnode))); // Make space for new digit
    			newnode->digit = c - '0';								// Convert char to int, ascii conversion, and store
    			newnode->next = NULL;									//Set next pointer to null to terminate list for now
    			if(listA == NULL) {	//
    				listA = newnode;
    				pCur = listA;
    			}
    			else {				// Otherwise, simply add it.
    				pCur->next = newnode;
    				pCur = pCur->next;
    			}
    			listAcnt++;				// iterate digit counter
    			c = fgetc(Fp);	// read in new char
    		}//end a while
    		
    		c = fgetc(Fp); //read first char of listB
    		while(c != '\n' && c != EOF) {							// While we're not at a new line or the end of the file.
    			newnode = (listnode*)(malloc(sizeof(listnode))); // Create new node
    			newnode->digit = c - '0';								// Add data, adjusting the ascii value to make it a real int
    			newnode->next = NULL;
    			if(listB == NULL) {	// if null add first node
    				listB = newnode;
    				pCur = listB;
    			}
    			else {				// add digit to list
    				pCur->next = newnode;
    				pCur = pCur->next;
    			}
    			listBcnt++;				//iterate digit counter
    			c = fgetc(Fp);	// read in new char
    		}//end b while
    
        }//end file read in code
    
        printf("Closing file...");
        fclose(Fp);
    
    //TEST
    printlist(listA);
    printlist(listB);
    
    while(1);
    
    return 0;
    }
    
    
    //This function prints any linked list of digits
    void printlist(listnode* list){
    
    listnode* pTrav = list;
    
        while(pTrav!=NULL){
            printf("%d", pTrav->digit);
            pTrav=pTrav->next;
        }
    
    printf("\n");
    
    return;
    }

  2. #2
    CS Student
    Join Date
    Mar 2004
    Posts
    4

    Note

    Please understand, I do not expect anyone to give me source code, or do this entire assignment for me. I am struggling with the long division part in that I cannot formulate how to implement the idea into code. I understand this is not a homework service, only a means of recieving help.

    Thank you,
    Abyss
    Last edited by abyssknight; 03-31-2004 at 05:09 PM.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    If you don't understand the operation in question, how do you expect to tell the computer how to do it? Even if you do manage it, how can you expect the code to be even remotely solid? Walk through the rules of long division. At each step, pretend that you cannot take any shortcuts, you have to move this digit here and this digit there, move to the next digit, etc... Once you fully understand what you're trying to do, you can more easily give the computer instructions on how to do it.

    >I cannot formulate how to implement the idea into code
    Then you should be reading books on basic math, not working on an implementation.*

    * I can see how that would be seen as a slight against you, but it wasn't intended as such. My meaning is only that you should be concentrating on solving the problem, not trying to write code.
    My best code is written with the delete key.

  4. #4
    CS Student
    Join Date
    Mar 2004
    Posts
    4
    I understand, I'm going to give it a few more shots again today. I've been working small long division problems, and it's become a matter of logistics with moving digits and subtracting linked lists of digits, because you can only go one way due to the nature of linked lists. Hopefully I can get it done today. Still, I'll welcome all the help I can get with this.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >because you can only go one way due to the nature of linked lists
    Due to the nature of linked lists you can't jump around without extra help, but it is possible to move both forward and backward (and up and down if you want to get fancy ) by adding more links.
    My best code is written with the delete key.

  6. #6
    CS Student
    Join Date
    Mar 2004
    Posts
    4

    mhm

    i know what you mean, doubly linked lists, but we haven't studied those yet, so I am assuming we should be able to do this without them.

    I'm working on writing an algorithm instead of code, and I am still getting stuck, but its getting me closer than trying to code it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 03:19 PM
  3. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  4. Adding directory/file names to a linked list
    By thoseion in forum C Programming
    Replies: 13
    Last Post: 12-08-2006, 01:13 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM