0

Basically, the assignment is to create a huge integer class by using a singly linked list, wherein each element of the linked list holds one digit of the number of the huge int. I only have to do addition and multiplication, and addition works. Multiplication *should* work, as far as I'm concerned, but I've spent the last several hours trying to figure out why it isn't working, and I've been unsuccessful. Here's the code...I know it's not as clean (or efficient) as it could be, so I apologize in advance if it's difficult to read.

linkedList.h:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
using namespace std;

struct Digit {
	int digit;
	Digit * next;
};

class linkedList {
public:
	linkedList();
	~linkedList();
	void add(int datum);
	void printList(Digit * d/*, int len*/);
	int returnLength();
	void setHead(int d);
	Digit * getHead();
	Digit * getLast();
	void deleteItem(); // Deletes first item in list
	//int isInList(int num); // If item is not in list, returns 0, else returns number of item
	//bool remove(int num);
	//void removeHelper(int num);
	//double returnItemPrice(int num);
	//double returnListPrice();
	bool isEmpty();
	linkedList & operator=(const linkedList & l);
	void reverseList();
	//bool operator==(const linkedList & other) const;
	//bool operator!=(const linkedList & other) const;

private:
	Digit * head;
	int length;
};

#endif

linkedList.cpp

#include <iostream>
#include "linkedlist.h"
using namespace std;

linkedList::linkedList() {
    head = NULL;
    length = 0;
}

linkedList::~linkedList() {
    while (head)
        deleteItem();
}

void linkedList::add(int datum) {
    Digit * p = new Digit;
    p->digit = datum;
    p->next = head;
    head = p;
    length++;
}

void linkedList::printList(Digit * d) {
    if (d->next) {
        printList(d->next);
    }
    cout << d->digit;
}

int linkedList::returnLength() {
    return length;
}

void linkedList::setHead(int d) {
    head->digit = d;
}

Digit * linkedList::getHead() {
    return head;
}

Digit * linkedList::getLast() {
    Digit * p = head;
    while (p->next) p = p->next;

    return p;
}

bool linkedList::isEmpty() {
    return (head == NULL);
}

linkedList & linkedList::operator=(const linkedList & l) {
    while (head)
        deleteItem();

    Digit * current = l.head;
    while (current) {
        add(current->digit);
        current = current->next;
    }
    return *this;
}

void linkedList::deleteItem() {
    Digit * temp = head->next;
    delete head;
    head = temp;
}

void linkedList::reverseList() {
	Digit * first = head, *next = NULL;
	while (first->next != NULL) {
		next = first->next;
		first->next = next->next;
		next->next = head;
		head = next;
	}
}

hugeInt.h:

#ifndef HUGEINT_H
#define HUGEINT_H

#include <iostream>
#include "linkedList.h"
using namespace std;

class HUGE_INT {
public:
	HUGE_INT();
	HUGE_INT(unsigned long int i);
	HUGE_INT(const HUGE_INT & h);
	~HUGE_INT();
	//  method to assign an arbitrary unsigned long int to the HUGE_INT (which the constructors may use)
	void assign(unsigned long int i);
	HUGE_INT add(HUGE_INT h);
	HUGE_INT mult(HUGE_INT h);
	int getNumDigits();
	HUGE_INT & operator=(const HUGE_INT & h);
	void printNum();
private:
	linkedList * number;
	HUGE_INT multHelper(HUGE_INT & thisBetterWork, linkedList * h, Digit * big, Digit * small);
	int numDigits;
};

#endif

hugeInt.cpp:

#include <iostream>
#include "hugeInt.h"
using namespace std;

HUGE_INT::HUGE_INT() {
	//number->setHead(0);
	number = new linkedList;
	numDigits = 0;
}

HUGE_INT::HUGE_INT(unsigned long int i) {
    number = new linkedList;
	this->assign(i);
}

HUGE_INT::HUGE_INT(const HUGE_INT & h) {
	// call assignment operator
	*this = h;
}

HUGE_INT::~HUGE_INT() {
	number->~linkedList();
}

HUGE_INT HUGE_INT::add(HUGE_INT h) {
    HUGE_INT p;
    if (number->isEmpty()) {
        cout << "number is empty" << endl;
        //number->add(0);
    }
    int carry = 0, temp = 0;
    Digit * a = number->getHead();
    Digit * b = h.number->getHead();
    while (a && b) {
        temp = carry + a->digit + b->digit;
        carry = temp / 10;
        p.number->add(temp % 10);
        a = a->next;
        b = b->next;
    }

    if (a && !b) {
        while (a) {
            temp = a->digit + carry;
            carry = temp / 10;
            p.number->add(temp % 10);
            a = a->next;
        }
    }
    else if (!a && b) {
        while (b) {
            temp = b->digit + carry;
            carry = temp / 10;
            p.number->add(temp % 10);
            b = b->next;
        }
    }
    if (carry > 0) {
        p.number->add(carry);
    }
    cout << endl;

    p.number->reverseList();
    this->number = p.number;
    return p;
}

HUGE_INT HUGE_INT::multHelper(HUGE_INT & thisBetterWork, linkedList * h, Digit * big, Digit * small) {
   // HUGE_INT total;
    HUGE_INT temp;
 

    int carry = 0;
    int temp2 = 0;
    int multiplier = 1;
    int save = multiplier;

    while (big) {
        carry = 0;
        save = multiplier * 10; // save off multiplier
        multiplier /= 10;
        while (multiplier) { // adjusts for shift in multiplication problems where
            temp.number->add(0); // more than one line is needed by adding zeroes
            multiplier /= 10; // to the end of the number
        }
        multiplier = save; // put saved off value back in multiplier

        while (small) {
            temp2 = (big->digit * small->digit + carry); // temp2 is product of all digits plus carry
            carry = temp2 / 10; // carry is digit in ten's place if not zero
            temp.number->add(temp2 % 10); // add digit in one's place to temp
            small = small->next;
        }

        if (carry > 0) {
            temp.number->add(carry);
        }

        cout << "Current total is ";
        temp.number->reverseList();
        temp.printNum();
        cout << endl << endl << endl;
        HUGE_INT total = thisBetterWork.add(temp); // adds total for current line to total for whole problem
        //temp3 = total;
        //if (temp3.number->isEmpty()) cout << "temp 3 is empty" << endl;
        cout << "Absolute total is ";
        thisBetterWork.printNum();
        cout << endl << endl << endl;
        big = big->next;
        small = h->getHead();
        temp.~HUGE_INT();
    }
      thisBetterWork.printNum();
      return thisBetterWork;
}
HUGE_INT HUGE_INT::mult(HUGE_INT h) {

	HUGE_INT total;

	Digit * p = number->getHead();
	Digit * q = h.number->getHead();

	if (h.getNumDigits() > getNumDigits()) {
	    return multHelper(total, h.number, p, q);
	}
    else {
        return multHelper(total,number, q, p);
    }
	return total;
}

int HUGE_INT::getNumDigits() {
	return number->returnLength();
}

void HUGE_INT::assign(unsigned long int i) {
	unsigned long int temp = i;
	while (temp) {
		number->add(temp % 10); // adds last digit to list
		temp /= 10; // Strips temp of last digit
	}
	number->reverseList();
}

HUGE_INT & HUGE_INT::operator=(const HUGE_INT & h) {
	 number = h.number;
	 return *this;
	// should work after = operator is done in linkedList class
}

void HUGE_INT::printNum() {
	Digit * d = number->getHead();
	number->printList(d);
}

main.cpp:

#include <iostream>
#include "hugeInt.h"
using namespace std;

int reverse_num(int sourcenum) {
	int temp = sourcenum;
	int sum = 0;
	while (temp) {
		sum *= 10; // sum = sum * 10
		sum += temp % 10; // sum = sum + the remainder of temp / 10
		temp /= 10; // temp = temp / 10
	}
	return sum;
}

int main() {
   
    HUGE_INT a(25);
    cout << "a is ";
    a.printNum();
    cout << endl;

    HUGE_INT b(301);
    cout << "b is ";
    b.printNum();

    cout << "\n\nTrying to multiply..." << endl;
    HUGE_INT c = a.mult(b);
    cout << "Succeeded." << endl;
    cout << "a * b is ";
    c.printNum();

    return 0;
}

Well, I should say I know what the problem is (I think), I just don't know how to fix it. The problem is in the multHelper() function in hugeInt.cpp. The HUGE_INT that should hold the total product just resets every time, and doesn't even hold a value outside of the while loop. If someone could tell me what I'm doing wrong, I would greatly appreciate it. Thanks

EDIT: I also added a main.cpp in case anyone wants to test it

Edited by SumPersonGuy: n/a

2
Contributors
1
Reply
2
Views
5 Years
Discussion Span
Last Post by tungnk1993
0

First off all, your code for linked list is quite complicated so i didnt read all. But there are some tips:
- Reverse both numbers ( i think you have done it)
- Multiply manually by hand, step by step, find the algorithm. Pay attention to carrys
- Get it work using arrays first ( so you can ensure that the logic is right)
- Implement using linked list
- Worst come to worst, search and read code by others

Good luck :)

Edited by tungnk1993: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.