BigInteger.c (as of 9:27 PM, 11/13)

// Jevin Olano
// jolano
// CSE 101
// November 9, 2019
// BigInteger.c

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include "BigInteger.h"
#include "List.h"

const int POWER = 9;
const int BASE = 1000000000;

// Constructors & Destructors ---------------------------

// newBigInteger()
// Returns a reference to a new BigInteger object in the zero state.
BigInteger newBigInteger() {
	BigInteger bi = malloc(sizeof(BigIntegerObj));
	bi->number = newList();
	bi->sign = 0;
	return bi;
}

// freeBigInteger()
// Frees heap memory associated with *pN, sets *pN to NULL.
void freeBigInteger(BigInteger *pN) {
	BigInteger N = *pN;
	makeZero(N);
	free(N);
	N = NULL;
}

// Access Functions -------------------------------------

// sign()
// Returns -1 if N is negative, 1 if N is positive, and 0 if N is in the zero state.
int sign(BigInteger N) {
	return N->sign;
}

// compare()
// Returns -1 if A<B, 1 if A>B, and 0 if A=B.
int compare(BigInteger A, BigInteger B) {
	if (A->sign == 0 && B->sign == 0) {
		return 0; // if both A & B are in the zero state
	}
	if (A->sign > B->sign) {
		return 1; // if A is positive and B is negative
	}
	if (A->sign < B->sign) {
		return -1; // if A is negative and B is positive
	}

	int lengthA = length(A->number);
	int lengthB = length(B->number);
	if (lengthA > lengthB && A->sign == 1) {
		return 1; // if both A & B are positive and A is longer than B
	}
	if (lengthA > lengthB && A->sign == -1) {
		return -1; // if both A & B are negative and A is longer than B
	}
	if (lengthB > lengthA && B->sign == 1) {
		return -1; // if both A & B are positive and B is longer than A
	}
	if (lengthB > lengthA && B->sign == -1) {
		return 1; // if both A & B are negative and B is longer than A
	}

	BigInteger clonedB = copy(B);

	// at this point, A & B must be the same sign
	moveFront(A->number);
	moveFront(clonedB->number);
	while (get(A->number) != -1) {
		int digitA = get(A->number);
		int digitB = get(clonedB->number);
		if (digitA > digitB && A->sign == 1) {
			return 1;
		}
		if (digitA < digitB && A->sign == 1) {
			return -1;
		}
		if (digitA > digitB && A->sign == -1) {
			return -1;
		}
		if (digitA < digitB && A->sign == -1) {
			return 1;
		}
		moveNext(A->number);
		moveNext(clonedB->number);
	}
	freeBigInteger(&clonedB);
	return 0;
}

// equals()
// Return true (1) if A and B are equal, false (0) otherwise.
int equals(BigInteger A, BigInteger B) {
	return compare(A, B) == 0 ? 1 : 0;
}

// Manipulation Procedures ------------------------------

// makeZero()
// Re-sets N to the zero state.
void makeZero(BigInteger N) {
	clear(N->number);
	N->sign = 0;
}

// negate()
// Reverses the sign of N: positive <--> negative. Does nothing if N is in the zero state.
void negate(BigInteger N) {
	N->sign *= -1;
}

// BigInteger Arithmetic Operations ---------------------

// private helper
long strToLong(char *s, long numChars) {
	char buffer[10];
	for (int i = 0; i < numChars; i++) {
		buffer[i] = s[i];
	}
	buffer[numChars] = '\0';
	return strtol(buffer, NULL, 10);
}

// stringToBigInteger()
// Returns a reference to a new BigInteger represented in base 10 by the string s.
// Pre: s is a non-empty string containing only base ten digits {0,1,2,3,4,5,6,7,8,9}
// and an optional sign {+, -} prefix.
BigInteger stringToBigInteger(char* s) {
	BigInteger bi = newBigInteger();

	// handles input = '0'
	if (strlen(s) == 1 && s[0] == '0') {
		return bi;
	}

	// p is basically a cursor
	char *p = s;

	// checks optional sign prefixes
	if (s[0] == '+') {
		bi->sign = 1;
		p++;
	} else if (s[0] == '-') {
		bi->sign = -1;
		p++;
	} else {
		bi->sign = 1;
	}

	// check for incomplete digit (incomplete chunk)
	int remainder = strlen(p) % POWER;
	if (remainder > 0) {
		append(bi->number, strToLong(p, remainder));
		p += remainder;
	}

	// add "full" digits
	int numDigitsLeft = strlen(p) / POWER;
	for (int i = 0; i < numDigitsLeft; i++) {
		append(bi->number, strToLong(p, POWER));
		p += POWER;
	}

	return bi;
}

// copy()
// Returns a reference to a new BigInteger object in the same state as N.
BigInteger copy(BigInteger N) {
	BigInteger copyInt = newBigInteger();
	copyInt->sign = N->sign;
	copyInt->number = copyList(N->number);
	return copyInt;
}

// longerNumLength
// helper method
int longerNumLength(BigInteger A, BigInteger B) {
	int lengthA = length(A->number);
	int lengthB = length(B->number);
	return (lengthA > lengthB) ? lengthA : lengthB;
}

// getDigit
// helper method
long getDigit(List L) {
	long digit = get(L);
	return (digit != -1) ? digit : 0;
}

// add()
// Places the sum of A and B in the existing BigInteger S, overwriting its current state: S = A + B
void add(BigInteger S, BigInteger A, BigInteger B) {
	BigInteger sumInt = sum(A, B);
	makeZero(S);
	S->sign = sumInt->sign;
	S->number = copyList(sumInt->number);
	freeBigInteger(&sumInt);
}

void removeLeadingZeroes(BigInteger bi) {
	if (isEmpty(bi->number)) {
		return;
	}
	moveFront(bi->number);
	while(get(bi->number) != -1) {
		if (get(bi->number) != 0) {
			return;
		}
		delete(bi->number);
		if (isEmpty(bi->number)) {
			return;
		}
		moveFront(bi->number);
	}
}

// sum()
// Returns a reference to a new BigInteger object representing A + B.
BigInteger sum(BigInteger A, BigInteger B) {
	if (A->sign == 0 && B->sign == 0) {
		return newBigInteger();
	}
	if (A->sign == 0) {
		return copy(B);
	}
	if (B->sign == 0) {
		return copy(A);
	}

	if (A->sign == 1 && B->sign == -1) {
		negate(B);
		BigInteger temp = diff(A, B);
		negate(B);
		return temp;
	}

	if (A->sign == -1 && B->sign == 1) {
		negate(A);
		BigInteger temp = diff(B, A);
		negate(A);
		return temp;
	}

	BigInteger sumInt = newBigInteger();

	BigInteger clonedB = copy(B);

	moveBack(A->number);
	moveBack(clonedB->number);

	int longerNumLen = longerNumLength(A, clonedB);

	int carry = 0;

	for (int i = 0; i < longerNumLen; i++) {
		long digitA = getDigit(A->number);
		long digitB = getDigit(clonedB->number);
		long sum = digitA + digitB + carry;
		carry = 0;
		if (sum >= BASE) {
			sum -= BASE;
			carry = 1;
		}
		prepend(sumInt->number, sum);
		movePrev(A->number);
		movePrev(clonedB->number);
	}

	if (carry == 1) {
		prepend(sumInt->number, 1);
	}

	sumInt->sign = A->sign; // or B->sign since they're the same
	freeBigInteger(&clonedB);
	removeLeadingZeroes(sumInt);
	return sumInt;
}

// copyNegate()
// helper method
BigInteger copyNegate(BigInteger A) {
	BigInteger negativeA = copy(A);
	negate(negativeA);
	return negativeA;
}

// subtract()
// Places the difference of A and B in the existing BigInteger D, overwriting its current state: D = A - B
void subtract(BigInteger D, BigInteger A, BigInteger B) {
	BigInteger diffInt = diff(A, B);
	makeZero(D);
	D->sign = diffInt->sign;
	D->number = copyList(diffInt->number);
	freeBigInteger(&diffInt);
}

// diff()
// Returns a reference to a new BigInteger object representing A - B.
BigInteger diff(BigInteger A, BigInteger B) {
	if (A->sign == 0 && B->sign == 0) {
		return newBigInteger();
	}
	if (A->sign == 0) {
		return copyNegate(B);
	}
	if (B->sign == 0) {
		return copy(A);
	}
	if (A->sign != B->sign) {
		return sum(A, copyNegate(B));
	}

	BigInteger diffInt = newBigInteger();
	diffInt->sign = equals(A, B) == 1 ? 0 : A->sign;
	BigInteger clonedB = copy(B);

	moveBack(A->number);
	moveBack(clonedB->number);

	int longerNumLen = longerNumLength(A, clonedB);

	int borrow = 0;

	for (int i = 0; i < longerNumLen; i++) {
		long digitA = getDigit(A->number);
		long digitB = getDigit(clonedB->number);
		long diff = digitA - digitB - borrow;
		borrow = 0;
		if (diff < 0) {
			diff += BASE;
			borrow = 1;
		}
		prepend(diffInt->number, diff);
		movePrev(A->number);
		movePrev(clonedB->number);
	}

	if (borrow == 1) {
		moveFront(diffInt->number);
		set(diffInt->number, get(diffInt->number) - BASE);
		negate(diffInt);
	}

	freeBigInteger(&clonedB);
	removeLeadingZeroes(diffInt);
	return diffInt;
}

// multiply()
// Places the product of A and B in the existing BigInteger P, overwriting its current state: P = A * B
void multiply(BigInteger P, BigInteger A, BigInteger B) {
	BigInteger prodInt = prod(A, B);
	makeZero(P);
	P->sign = prodInt->sign;
	P->number = copyList(prodInt->number);
	freeBigInteger(&prodInt);
}

// prod()
// Returns a reference to a new BigInteger object representing A * B.
BigInteger prod(BigInteger A, BigInteger B) {
	if (A->sign == 0 || B->sign == 0) {
		return newBigInteger(); // zero state
	}

	BigInteger prodInt = newBigInteger();

	int carry = 0;
	int zeroes = 0;
	BigInteger prodTemp = newBigInteger();

	BigInteger clonedB = copy(B);

	moveBack(A->number);

	// A = "bottom" number in traditional multiplication
	// B = "top" number in traditional multiplication

	while (A->number->cursor != NULL) {
		moveBack(clonedB->number);
		makeZero(prodTemp);
		int isNonZero = 0;
		while (clonedB->number->cursor != NULL) {
			long digitA = getDigit(A->number);
		printf("digitA is = %ld\n", digitA);
			long digitB = getDigit(clonedB->number);
		printf("digitB is = %ld\n", digitB);
			long prod = digitA * digitB + carry;
		printf("prod is = %ld\n", prod);
			carry = 0;
			if (prod > 0) {
				isNonZero = 1;
			}
			if (prod >= BASE) {
				carry = prod/BASE; // integer division drops fractional part
			printf("carry is = %d\n", carry);
				prod -= BASE * carry;
			}
			prepend(prodTemp->number, prod);
			movePrev(clonedB->number);
		}

		if (carry > 0) {
			prepend(prodTemp->number, carry);
			isNonZero = 1;
		}

		for (int i = 0; i < zeroes; i++) {
			append(prodTemp->number, 0);
		}

		if (isNonZero == 1) {
			prodTemp->sign = 1;
		}

		add(prodInt, prodInt, prodTemp);
		zeroes++;
		movePrev(A->number);
	}

	freeBigInteger(&prodTemp);
	freeBigInteger(&clonedB);

	prodInt->sign = (A->sign == B->sign) ? 1 : -1;
	removeLeadingZeroes(prodInt);
	return prodInt;
}

// Other Operations -------------------------------------

// printBigInteger()
// Prints a base 10 string representation of N to filestream out.
void printBigInteger(FILE* out, BigInteger N) {
	if (N->sign == 0) {
		fprintf(out, "0\n");
		return;
	}
	if (N->sign == -1) {
		fprintf(out, "-");
	}
	moveFront(N->number);
	// skip leading zeroes
	while (get(N->number) == 0) {
		moveNext(N->number);
	}
	while (get(N->number) != -1) {
		fprintf(out, "%ld", get(N->number));
		moveNext(N->number);
	}
	fprintf(out, "\n");
}