Pweebs

Untitled

Nov 9th, 2019
141
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