Notes App. E:
Addendum to Essentials of Data Structures, Appendix E

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Adding Large Integers (E-2)
• Dividing Large Integers (E-4)

Adding Long Integers

F&T does not address "long integers" as do other Data Structures texts. The following code is modeled after a Pascal code found in the 2nd Edition of Tenenbaum and Augenstein, Data Structures Using Pascal, pp 228-30. (Note this has not been tested!)

NOTE: The data structure in which the integers are stored is an circular simply linked list with a header node whose value is -1. This structure makes it easier to insert another node "at the end."

     node * addint(node * p, node * q)
     {   const int modulus = 100000;
         const modulusminus1 = 99999;
	 node * s, pp, qq, r;
	 int carry, number, total;
	 // initialization
	 pp = p->next; // points to first numeric node
	 qq = q->next; // i.e., skipe header nodes
	 s = new node;
	 s->info = -1; // sets up header node for
	 s->next = s;  // sum list s
	 carry = 0;
	 // begin major loop as long as BOTH p and q have
	 // numeric nodes
	 while ((pp->info != -1) && (qq->info != -1)
	 {   total = pp->info + qq->info + carry;
	     number = total%modulus;
	     insafter(s,number); // code moded after list code
	     carry = total/modulus;
	     s = s->next;   // advance pointers
	     pp = pp->next; // for all three
	     qq = qq->next; // lists
	 }
	 // when you have "run out of number" in either p or q,
	 // first determine which list still has information
	 // in it.
	 if (pp->info != -1)
	    r = pp; // p has more information
	 else
	    r = qq; // q has more information
	 // new major loop to transfer logner number to s
	 while (r->info != -1)
	 {   total = r->info+carry;
	     number = total%modulus;
	     insafter(s,number); // code moded after list code
	     carry = total/modulus;
	     s = s->next;   // advance pointers
	     r = r->next;
	 }
	 if (carry == 1)
	 {   insafter(s,carry);
	     s = s->next;
	 }
	 addint = s->next;
    }

Dividing Long Integers

     #include
     int main()
       {int modulus,divisor,number,i,limit,remainder,quotient;
	cout << "0.";
	modulus = 10;
	divisor = 7;
	number = 10;
	limit = 100;
	for(i=1;i < limit;i++)
	{   remainder = number%divisor;
	    quotient = number/divisor;
	    cout << quotient;
	    number = remainder*modulus;
	}
	cout << endl;
	return 0;
        }

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998, 1999 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 7 April 1999.