C++

Forum

 
Using List to implement huge numbers

Damon (8)
Im trying to implement a way to use really big numbers to be able to add, substract and multiply them with the class I made. for example: 

1
2
3
4
5
6
7
8
 
huge a = "45646464646455464654656"
huge b = "456464564646544646"
huge c = a+b;
huge d = a-c;
huge e = a*c;
cout<< c<< endl;
cout<< d<< endl;
cout<< e<< endl;


Now I wanna be able to do that in the following code and I'm not sure how to start it. I know I have to use the list double to go through the numbers from the end and of course if I enter a number 464646468464 it has to return in lists of number like groups of 4 like 4646 46464 4646.

This is my current implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
 
template <typename TYPE> 
    class ListDouble {
        template <typename T> friend ostream& operator<<(ostream&, ListDouble<T>&);

        // ===== Class Node intern ====================
        class Node {
        public:
            TYPE value;
            Node *next, *previous;

            Node (TYPE v, Node * p = NULL, Node * s = NULL)
                { value= v; previous= p; next= s; }
        };
          // ===============================================
        Node *head, *queue;
        int size;

           public:
          // ===== Class Iterator intern ================

        class Iterator {
            Node*node;
            friend class ListDouble;   //Allows methods of list to read Node

        public:
            Iterator (Node* n = NULL)         // Constructor
                { node= n; }
            Iterator (Iterator &I)            // Copy constructor
                { node= I.node; }
            Iterator & operator++() {          // Operator ++ used as ++I
                if (node!= NULL) node= node->next;
                return *this;
            }
            Iterator & operator++(int) {       // Operator ++ used as I++
                Iterator temp = *this;
                if (node!= NULL) node= node->next;
                return temp;
               }

                    Iterator & operator--() {          // Operator -- used as --I
                if (node!= NULL) node= node->previous;
                return *this;
            }
            Iterator & operator--(int) {       // Operator -- used as I--
                Iterator temp = *this;
                if (node!= NULL) node= node->previous;
                return temp;
               }
                    Iterator & operator+(int n) const {
            Iterator it(node);
            if (n > 0)
                for (int i=0; i<n; i++) it++;
            else
                for (int i=0; i>n; i--) it--;
            return it;
        }

        Iterator & operator-(int n) const {
            return operator+(-n);
        }

            TYPE& operator*() {                // Operator * used as *I
                return node->value;          // Don't use if node = 0
            }
            bool operator==(Iterator &I) {    // Operator == between Iterator 
                return node == I.node ;
            }
            bool operator!=(Iterator &I) {    // Operator != between Iterator 
                return node != I.node ;
            }
            Iterator & operator=(Iterator &I) {
                node = I.node ;               // Assigns I1 = I2
                return *this;
            }
          };
          // ===============================================

        ListDouble() {
            head= NULL;
            queue = NULL;
            size= 0;
        }

        ~ListDouble() {
            while (head!= NULL) {
                Node*N = head;
                head = head->next;
                delete N;
            }
        }

        int getSize() {
            return size;
        }

        void insertHead(TYPE element) {
            if (head== NULL)
                head = queue = new Node(element, NULL, NULL);
            else
                head= head->previous= new Node(element, NULL, head);
            size++;
        }

        void insertQueue(TYPE element) {
            if (queue == NULL)
                head= queue = new Node(element, NULL, NULL);
            else
                queue = queue->next= new Node(element, queue, NULL);
            size++;
        }

        TYPE extractHead() {
            if (head== NULL) return -1;  // Error

            TYPE element = head->value;  // Keeps the value to extract.
            Node *temp = head;           // Keeps the node to destruct.
            head= head->next;         // The head is the next node.
            if (head== NULL)             // If there's no head the list is empty
                queue = NULL;            
            else                       // If theres a next node now he has no previous
                head->previous= NULL;  
            delete temp;                  // Destruct node.
            size--;                     // Adjust the size of the list.
            return element;               
        }

        TYPE extractQueue() {          
            if (queue == NULL) return -1;

            TYPE element = queue->value;
            Node *temp = queue;
            queue = queue->previous;
            if (queue == NULL)
                head= NULL;
            else
                queue->next= NULL;
            delete temp;
            size--;
            return element;
        }

        Iterator start() {    // Puts the iterator at the start of list
            return Iterator(head);
        }

        Iterator end() {       // Puts the iterator at the end of list
            return Iterator (NULL);
        }
      };
   


        template <typename T> ostream& operator<<(ostream& ostr, ListDouble<T> &L) {
        // Friend function of list that prints out.

        ListDouble<T>::Node *N = L.head;
        ostr << "HEAD -> ";
        while (N != NULL) {
            ostr << N->value;
            if (N == L.queue)
                ostr << " <- ";
            else
                ostr << " <-> ";
            N = N->next;
        }
        ostr << "QUEUE" << endl;
        return ostr;
     }

      //------------------------------------------------------------------------
      // Main program
      //------------------------------------------------------------------------
      int _tmain(int argc, _TCHAR* argv[])
      {
        ListDouble<int> L;
        L.insertHead(10);
        L.insertHead(20);
        L.insertQueue(30);
        L.insertQueue(40);
        L.insertHead(50);
        L.insertHead(60);
        L.insertQueue(70);
        L.insertQueue(80);

        cout << "With the friend function... \n";
        cout << L;

        cout << "With Iterators... \n";
        ListDouble<int>::Iterator I;
        for(I = L.start(); I != L.end(); ++I)
            cout << *I << " ";

        cout << endl;
        return 0;
     }
giblit (3750)
Umm...Why not make a vector of ints? So instead of base 10 it could be say base 2^32 or use the decimal base like how we write out numbers and separate when we hit the max for that

say for example an int has a max value of 4294967296 (unsigned long)
so basically if the number is greater than 999999999 it will go to the next array element then I would suggest flipping it so it is readable or you can just flip that when outputting to make it easier to modify.

So then if we have a value of 12345678901
4294967296

It would be displayed as

1
2
 
[0] = 12
[1] = 345678901



Damon (8)
Sadly my teacher wants us to make it this way :S his example is if you calculate the value of

50! = 30 414 093 201 713 378 043 612 608 166 064 768 844 377 641 568 960 542 000 000 000 000

it would be :

Head -> 30 414 -> 093 201 -> 713 378 -> 043 612 -> 608 166-> 064 768 -> 844 377 -> 641 568 -> 960 512-> 000 000 - > 000 000-> Null
Last edited on
closed account (D80DSL3A)
What are you specifically having trouble with? Have you written any function prototypes for an implementation yet?

I've done a bigInteger exercise using a hand written double list as an exercise myself. Perhaps a good place to start is construction of a bigInt from std::string. You then test to make sure the digits are getting stored in the list correctly.
From my project:
bigInt_dList( const std::string& numStr );// string
Next, you might try defining an operator + for adding 2 bigInts
bigInt_dList operator+( const bigInt_dList& bgX )const;
Just use the same method you would if doing the addition on paper. Add the least significant (group of) digits, find the carry and assign the remainder to a node in the resulting list. Continue this until you've gone through both lists.
Damon (8)
I'm having trouble with what to use to make my operator +. This subject is very abstract for me and I just can't seem to figure how it works which values to use or what to use for my operators. I was able to do this without the list. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
BigInt BigInt:: operator+(const BigInt& x) const
{
	// z = *this +  x
	BigInt z( len > x.len? len:x.len );// z will have len = greatest of the 2	

	if( this->isPositive )
	{
		if( x.isPositive )
		{
			z.addMags( *this, x );
			z.isPositive = true;
		}
		else// x is negative
		{
			if( this->isLowerMagnitude(x) )
			{
				z.subtractMags( x, *this );
				z.isPositive = false;
			}
			else
			{
				z.subtractMags( *this, x );
				z.isPositive = true;
			}
		}
	}
	else// this is negative
	{
		if( x.isPositive )
		{
			if( this->isLowerMagnitude(x) )
			{
				z.subtractMags( x, *this );
				z.isPositive = true;
			}
			else
			{
				z.subtractMags( *this, x );
				z.isPositive = false;
			}
		}
		else// x is negative
		{
			z.addMags( *this, x );
			z.isPositive = false;
		}
	}
	z.findCorrectLength();
	return z;
}// end of +


I don't know how to implement any of this in my class :s sorry I just can't get my head around this
closed account (D80DSL3A)
Yes. That method is based on using dynamically allocated arrays. Line 4 allocates an array large enough to contain the resulting bigInt.

I know this because I wrote that code. Did you find it via the link in this post
http://www.cplusplus.com/forum/lounge/32041/2/#msg175798
in a thread for a bigNum challenge in the lounge from a couple of years ago?

Anyways, a list based solution would be somewhat different. Instead of allocating all of the memory required at once up front, nodes would be allocated one by one during the addition process to build up the number in a list. Take a look at the addMags() function for ideas. That's where the addition is actually carried out.
Last edited on
Damon (8)
Yea, I searched for an example without the list and actually the website is

http://home.comcast.net/~mlyn7576/bignum-challenge/fun2code.cpp

I have tried adapting it to my code, but no luck so far. I'll keep trying hopefully I can get something done. It's just not easy to figure it out.
closed account (D80DSL3A)
I had no idea that code existed elsewhere! It's hard trying to understand how someone else code works. It's often easier to write your own code than to try to understand and adapt code written for a different purpose.
For instance, all that code in operator+ is for dealing with bigInts that may be positive or negative. If your working with positive bigInts only then it's simpler.

Have you gotten a constructor to work yet? Making a list from a given string representation of a bigInt would be the 1st task. You can't add them if you can't create them first.
Last edited on
Damon (8)
Honestly. I have tried and it's just not working for me. This subject is really abstract for me I honestly can't get myself to even start it simply as you say.
Duthomhas (13152)
Store your number as a list of digits, least significant first.

"1234" stored as { 4, 3, 2, 1 }

To add two numbers, remember how it works in gradeschool:

   { 4, 3, 2, 1 }
 + { 8, 7, 6, 5 }
 ----------------
   { 2, _, _, _ }  ( 4+8 +0=12 --> 2, carry=1 )
   { 2, 1, _, _ }  ( 3+7 +1=11 --> 1, carry=1 )
   { 2, 1, 9, _ }  ( 6+2 +1=9  --> 9, carry=0 )
   { 2, 1, 9, 6 }  ( 1+5 +0=6  --> 6, carry=0 )

Notice that it is possible to need to add a digit at the end due to carry.

[edit] That's 1234 + 5678 = 6912 [/edit]

Subtraction works similarly.

When you get that far, then you can worry about multiplication.

Hope this helps.
Last edited on
Damon (8)
I wasn't able to do it and the due date to give it in was yesterday. Sorry thanks for the help sadly I still don't know how to do it.
Duthomhas (13152)
You should do it anyway.
Even if your professor won't accept it late.
The point is for you to learn, otherwise you are just throwing money down the crapper.
Damon (8)
I'm not even able to start the code like I have a really hard time understanding how List works or Itterators
Duthomhas (13152)
Then you are behind in your class and you need to go talk with your professor.

A "list" is any ordered collection of (homogeneous in C++) objects. The std::list is a linked list of said objects instead of something as simple as an array.

The simplest way to describe an iterator is that it acts like a pointer over an array, except, of course, that the underlying sequence need not be a simple array -- it can be a linked list, a rope, a deque, a tree -- whatever it may be.

Good luck!
Topic archived. No new replies allowed.