Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 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;
- //const int POWER = 1;
- //const int BASE = 10;
- // 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
- }
- printBigInteger(stdout, A);
- printBigInteger(stdout, B);
- 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);
- long digitB = getDigit(clonedB->number);
- long prod = digitA * digitB + carry;
- carry = 0;
- if (prod > 0) {
- isNonZero = 1;
- }
- if (prod >= BASE) {
- carry = prod/BASE; // integer division drops fractional part
- prod -= BASE * carry;
- }
- //printList(stdout, prodTemp->number);
- prodTemp->sign = 1;
- printBigInteger(stdout, prodTemp);
- printf("above is prodTemp before prepend1\n");
- prepend(prodTemp->number, prod);
- //printList(stdout, prodTemp->number);
- printBigInteger(stdout, prodTemp);
- prodTemp->sign = 0;
- printf("above is prodTemp after prepend1\n");
- movePrev(clonedB->number);
- }
- if (carry > 0) {
- //printList(stdout, prodTemp->number);
- prodTemp->sign = 1;
- printBigInteger(stdout, prodTemp);
- printf("above is prodTemp before prepend2\n");
- prepend(prodTemp->number, carry);
- //printList(stdout, prodTemp->number);
- printBigInteger(stdout, prodTemp);
- prodTemp->sign = 0;
- printf("above is prodTemp after prepend2\n");
- isNonZero = 1;
- carry = 0;
- }
- 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");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement