SHARE
TWEET

Untitled

Pweebs Nov 9th, 2019 102 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Jevin Olano
  2. // jolano
  3. // CSE 101
  4. // November 9, 2019
  5. // BigInteger.c
  6.  
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <assert.h>
  10. #include <math.h>
  11. #include "BigInteger.h"
  12.  
  13. const int POWER = 9;
  14. const int BASE = 1000000000;
  15.  
  16. // Constructors & Destructors ---------------------------
  17.  
  18. // newBigInteger()
  19. // Returns a reference to a new BigInteger object in the zero state.
  20. BigInteger newBigInteger() {
  21.     BigInteger bi = malloc(BigIntegerObj);
  22.     bi->number = newList();
  23.     bi->sign = 0;
  24.     return bi;
  25. }
  26.  
  27. // freeBigInteger()
  28. // Frees heap memory associated with *pN, sets *pN to NULL.
  29. void freeBigInteger(BigInteger* pN) {
  30.     BigInteger N = *pN;
  31.     makeZero(N);
  32.     free(N);
  33.     N = NULL;
  34. }
  35.  
  36. // Access Functions -------------------------------------
  37.  
  38. // sign()
  39. // Returns -1 if N is negative, 1 if N is positive, and 0 if N is in the zero state.
  40. int sign(BigInteger N) {
  41.     return N->sign;
  42. }
  43.  
  44. // compare()
  45. // Returns -1 if A<B, 1 if A>B, and 0 if A=B.
  46. int compare(BigInteger A, BigInteger B) {
  47.     if (A->sign == 0 && B->sign == 0) {
  48.         return 0; // if both A & B are in the zero state
  49.     }
  50.     if (A->sign > B->sign) {
  51.         return 1; // if A is positive and B is negative
  52.     }
  53.     if (A->sign < B->sign) {
  54.         return -1; // if A is negative and B is positive
  55.     }
  56.  
  57.     int lengthA = length(A->number);
  58.     int lengthB = length(B->number);
  59.     if (lengthA > lengthB && A->sign == 1) {
  60.         return 1; // if both A & B are positive and A is longer than B
  61.     }
  62.     if (lengthA > lengthB && A->sign == -1) {
  63.         return -1; // if both A & B are negative and A is longer than B
  64.     }
  65.     if (lengthB > lengthA && B->sign == 1) {
  66.         return -1; // if both A & B are positive and B is longer than A
  67.     }
  68.     if (lengthB > lengthA && B-sign == -1) {
  69.         return 1; // if both A & B are negative and B is longer than A
  70.     }
  71.  
  72.     // at this point, A & B must be the same sign
  73.     moveFront(A->number);
  74.     moveFront(B->number);
  75.     while (get(A->number) != NULL) {
  76.         int digitA = get(A->number);
  77.         int digitB = get(B->number);
  78.         if (digitA > digitB && A->sign == 1) {
  79.             return 1;
  80.         }
  81.         if (digitA < digitB && A->sign == 1) {
  82.             return -1;
  83.         }
  84.         if (digitA > digitB && A->sign == -1) {
  85.             return -1;
  86.         }
  87.         if (digitA < digitB && A->sign == -1) {
  88.             return 1;
  89.         }
  90.         moveNext(A->number);
  91.         moveNext(B->number);
  92.     }
  93.     return 0;
  94. }
  95.  
  96. // equals()
  97. // Return true (1) if A and B are equal, false (0) otherwise.
  98. int equals(BigInteger A, BigInteger B) {
  99.     return compare(A, B) == 0 ? 1 : 0;
  100. }
  101.  
  102. // Manipulation Procedures ------------------------------
  103.  
  104. // makeZero()
  105. // Re-sets N to the zero state.
  106. void makeZero(BigInteger N) {
  107.     clear(N->number);
  108.     N->sign = 0;
  109. }
  110.  
  111. // negate()
  112. // Reverses the sign of N: positive <--> negative. Does nothing if N is in the zero state.
  113. void negate(BigInteger N) {
  114.     N->sign *= -1;
  115. }
  116.  
  117. // BigInteger Arithmetic Operations ---------------------
  118.  
  119. // stringToBigInteger()
  120. // Returns a reference to a new BigInteger represented in base 10 by the string s.
  121. // Pre: s is a non-empty string containing only base ten digits {0,1,2,3,4,5,6,7,8,9}
  122. // and an optional sign {+, -} prefix.
  123. BigInteger stringToBigInteger(char* s) {
  124.     BigInteger bi = newBigInteger();
  125.  
  126.     // handles input = '0'
  127.     if (strlen(s) == 1 && s[0] == '0') {
  128.         return bi;
  129.     }
  130.  
  131.     // p is basically a cursor
  132.     char *p = s;
  133.  
  134.     // checks optional sign prefixes
  135.     if (s[0] == '+') {
  136.         bi->sign = 1;
  137.         p++;
  138.     } else if (s[0] == '-') {
  139.         bi->sign = -1;
  140.         p++;
  141.     }
  142.  
  143.     // check for incomplete digit (incomplete chunk)
  144.     int remainder = strlen(p) % POWER;
  145.     if (remainder > 0) {
  146.         append(bi->number, strToLong(p, remainder));
  147.         p += remainder;
  148.     }
  149.  
  150.     // add "full" digits
  151.     int numDigitsLeft = strlen(p) / POWER;
  152.     for (int i = 0; i < numDigitsLeft; i++) {
  153.         append(bi->number, strToLong(p, POWER));
  154.         p += POWER;
  155.     }
  156.  
  157.     return bi;
  158. }
  159.  
  160. // private helper
  161. long strToLong(char *s, long numChars) {
  162.     char buffer[10];
  163.     buffer[0] = '\0';
  164.     strncat(buffer, s, numChars);
  165.     return strtol(s, NULL, 10);
  166. }
  167.  
  168. // copy()
  169. // Returns a reference to a new BigInteger object in the same state as N.
  170. BigInteger copy(BigInteger N) {
  171.     BigInteger copyInt = newBigInteger();
  172.     copyInt->sign = N->sign;
  173.     copyInt->number = copyList(N->number);
  174.     return copyInt;
  175. }
  176.  
  177. // add()
  178. // Places the sum of A and B in the existing BigInteger S, overwriting its current state: S = A + B
  179. void add(BigInteger S, BigInteger A, BigInteger B) {
  180.     int freeBeforeAssigning = (S == A || S == B) ? 1 : 0;
  181.     BigInteger sumInt = sum(A, B);
  182.     if (freeBeforeAssigning) {
  183.         freeBigInteger(&S);
  184.     }
  185.     S = sumInt;
  186. }
  187.  
  188. // sum()
  189. // Returns a reference to a new BigInteger object representing A + B.
  190. BigInteger sum(BigInteger A, BigInteger B) {
  191.     if (A->sign == 0 && B->sign == 0) {
  192.         return newBigInteger();
  193.     }
  194.     if (A->sign == 0) {
  195.         return copy(B);
  196.     }
  197.     if (B->sign == 0) {
  198.         return copy(A);
  199.     }
  200.  
  201.     if (A->sign == 1 && B-sign == -1) {
  202.         return diff(A, B);
  203.     }
  204.  
  205.     if (A->sign == -1 && B-sign == 1) {
  206.         return diff(B, A);
  207.     }
  208.  
  209.     BigInteger sumInt = newBigInteger();
  210.  
  211.     // TODO: the actual arithmetic here
  212.  
  213.     sumInt->sign = A->sign; // or B->sign since they're the same
  214.     return sumInt;
  215. }
  216.  
  217. // subtract()
  218. // Places the difference of A and B in the existing BigInteger D, overwriting its current state: D = A - B
  219. void subtract(BigInteger D, BigInteger A, BigInteger B) {
  220.     int freeBeforeAssigning = (D == A || D == B) ? 1 : 0;
  221.     BigInteger diffInt = diff(A, B);
  222.     if (freeBeforeAssigning) {
  223.         freeBigInteger(&D);
  224.     }
  225.     D = diffInt;
  226. }
  227.  
  228. // diff()
  229. // Returns a reference to a new BigInteger object representing A - B.
  230. BigInteger diff(BigInteger A, BigInteger B) {
  231.     if (A->sign == 0 && B->sign == 0) {
  232.         return newBigInteger();
  233.     }
  234.     if (A->sign == 0) {
  235.         BigInteger negativeB = copy(B);
  236.         negate(negativeB);
  237.         return negativeB;
  238.     }
  239.     if (B->sign == 0) {
  240.         return copy(A);
  241.     }
  242. }
  243.  
  244. // multiply()
  245. // Places the product of A and B in the existing BigInteger P, overwriting its current state: P = A * B
  246. void multiply(BigInteger P, BigInteger A, BigInteger B) {
  247.     int freeBeforeAssigning = (P == A || P == B) ? 1 : 0;
  248.     BigInteger prodInt = prod(A, B);
  249.     if (freeBeforeAssigning) {
  250.         freeBigInteger(&P);
  251.     }
  252.     P = prodInt;
  253. }
  254.  
  255. // prod()
  256. // Returns a reference to a new BigInteger object representing A * B.
  257. BigInteger prod(BigInteger A, BigInteger B) {
  258.     if (A->sign == 0 || B->sign == 0) {
  259.         return newBigInteger();
  260.     }
  261. }
  262.  
  263. // Other Operations -------------------------------------
  264.  
  265. // printBigInteger()
  266. // Prints a base 10 string representation of N to filestream out.
  267. void printBigInteger(FILE* out, BigInteger N) {
  268.  
  269. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top