# BigInt Linked List Long Division

• 03-31-2004
abyssknight
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; }```
• 03-31-2004
abyssknight
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
• 04-01-2004
Prelude
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.
• 04-01-2004
abyssknight
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.
• 04-01-2004
Prelude
>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.
• 04-01-2004
abyssknight
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.