# 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.
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.
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