-
Notifications
You must be signed in to change notification settings - Fork 1
/
README.txt
141 lines (113 loc) · 6.44 KB
/
README.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
# Long Project LP1: Integer Arithmetic with Arbitrarily Large Numbers
# Authors:
* Rahul Nalawade (rsn170330)
* Dhwani Raval (dsr170230)
* Varun Parashar (vxp171830)
* Arpita Agrawal (aua170030)
* Simran Rawlani (sxr174130)
* Yash Madane (yxm172130)
# End Date:
* Sunday, September 23, 2018
__________________________________________________________________________________
# Project Description
In this project, develop a program that implements arithmetic with large
integers, of arbitrary size.
Code base:
Java library: Lists, stacks, queues, sets, maps, hashing, trees.
Do not use BigInteger, BigNum, or other libraries that implement arbitrary
precision arithmetic.
Your task is to implement the class Num that stores and performs arithmetic
operations on arbitrarily large integers. You must use the following data
structure for representing Num:
Array of long integers, where the digits are in the chosen base. In
particular, do not use strings to represent the numbers. Each entry of the
list stores exactly one long integer.
The base is defined to be 10 in the starter code, but you may modify it.
For base = 10, the number 30128 is represented by the list: {8,2,1,0,3}.
For base = 100, the number 30128 is represented by the list: {28,1,3}.
Implement all methods in the starter code.
Some of them are -
Num(String s):
Constructor for Num class; takes a string s as parameter, with a number in
decimal, and creates the Num object representing that number in the chosen
base. Note that, the string s is in base 10, even if the chosen base is
not 10. The string s can have arbitrary length.
Num(long x):
Constructor for Num class.
String toString():
convert the Num class object into its equivalent string (in decimal).
There should be no leading zeroes in the string.
Num add(Num a, Num b):
sum of two numbers a+b stored as Num.
Num subtract(Num a, Num b):
a-b
Num product(Num a, Num b):
product of two numbers a*b.
Num power(Num x, long n):
given an Num x, and n, returns the Num corresponding to x^n (x to the power
n). Assume that n is a nonnegative number. Use divide-and-conquer to
implement power using O(log n) calls to product and add.
printList():
Print the base + ":" + elements of the list, separated by spaces.
Num divide(Num a, Num b):
Integer division a/b. Use divide-and-conquer or division algorithm.
Return null if b = 0.
Num mod(Num a, Num b):
remainder you get when a is divided by b (a % b). Assume that a is
non-negative, and b > 0. Return null if b = 0.
Num squareRoot(Num a):
return the square root of a (truncated). Use binary search. Assume that a
is non-negative. Return null if b < 0.
__________________________________________________________________________________
# Results:
For Base = 10^9
+--------------------------------------------------------------------------------+
| Test Case | Time (mSec) | Memory (used/avail) |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 0 | 4 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 1 | 279 | 321 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 2 | 5 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 3 | 2 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 4 | 2078 | 505 MB / 2047 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 5 | 9511 | 39 MB / 2047 MB |
|--------------------------------------------------------------------------------|
| $ java -Xss512m -Xms2g rsn170330.TestLP1 6 | 12357 | 33 MB / 2047 MB |
+--------------------------------------------------------------------------------+
+--------------------------------------------------------------------------------+
| Test | Base = 10^6 | Base = 10^4 |
| Case |-----------------------------------------------------------------------|
| | Time (mSec) | Memory (used/avail) | Time (mSec) | Memory (used/avail) |
|--------------------------------------------------------------------------------|
| 0 | 3 | 10 MB / 1963 MB | 3 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| 1 | 463 | 41 MB / 1963 MB | 649 | 407 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| 2 | 5 | 20 MB / 1963 MB | 6 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| 3 | 2 | 10 MB / 1963 MB | 2 | 10 MB / 1963 MB |
|--------------------------------------------------------------------------------|
| 4 | 3108 | 231 MB / 2047 MB | 4625 | 177 MB / 2047 MB |
|--------------------------------------------------------------------------------|
| 5 | 18354 | 589 MB / 2047 MB | 33283 | 424 MB / 2047 MB |
|--------------------------------------------------------------------------------|
| 6 | 23450 | 94 MB / 2045 MB | 39672 | 231 MB / 2047 MB |
+--------------------------------------------------------------------------------+
NOTE:
- Time and Memory might change, as you run the test the program on a different
system, but they could be comparable to the above values.
Existing Processor: Intel® Core™ i5-8250U CPU @ 1.60GHz × 8
Memory: 7.5 GiB
__________________________________________________________________________________
# How to Run:
1. Extract the rsn170330.zip
2. Compile:
$javac rsn170330/*.java
3. Run:
$java -Xss512m -Xms2g rsn170330.TestLP1 <value>
where value can be an Integer = {0, 1, 2, ..., 6}
__________________________________________________________________________________