-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathPES1201700186.txt
50 lines (25 loc) · 7.53 KB
/
PES1201700186.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
APSSSE MINI PROJECT REPORT
DEV BHARTRA
PES1201700186
INTRODUCTION
The problem statement was to create a library in the C programming language that aided in performing various mathematical operations on big numbers, called intals. Intal stands for integers, of arbitrary length. These big numbers are those that may not fit inside normal data types, and can be several hundreds of digits long. For the scope of this project, we have worked with intals of upto 1000 digits. An intal, as defined in the given problem statement, was a nonnegative integer of arbitrary length. The intal is stored as a null-terminated string of ASCII characters. Intals are stored in the big-endian style. Normal C integers contain negative numbers, but intals are non negative. C integers are limited by a maximum memory capacity of 2 or 4 bytes, bolding numbers from -32,768 to 32,767 or -2,147,483,648 to 2,147,483,647. Intals do not have similar restrictions, as they are fundamentally stored as a string of numbers. Intals help in working with large numbers across various problems in the modern world.
Approaching the Functions:
1. Intal Add: I convert the intals, which have been input as strings, to integer arrays. I then traverse these newly made integer arrays, number by number, simultaneously, and add them, while storing the carry and keeping track of that in a separate variable as well.
2. Intal Compare: Here I convert the input strings to integer arrays as well. Then, I begin traversing these arrays, from right to left (right side storing the MSB value). I compare each value, and as soon as one one value becomes larger than the other, I break out of the loop, after setting an appropriate flag. In the case where both numbers are equal, the flag is set to 0.
3. Intal Diff: I have once again converted both my char arrays to integer arrays, with the help of the same helper functions as above. The concept is the same as addition, with carry being replaced by a borrow term. To make sure the difference is absolute, before subtraction, I find the number which is greater, with the help of the comparison function, and then subtract the smaller number from the bigger.
4. Intal Multiply: Return 0 if either of the elements are 0. Then I proceed with the multiplication logic. Multiplication is also carried out number by number (the ascii values have been converted to ints). The essential ‘algorithm’ here is the same as what we have used in high school multiplication by hand.
5. Intal Mod: There is a divisor and a dividend. Two loops are run, the internal one runs till the divisor is smaller than the dividend. I keep increasing it’s value to twice its value. Once that breaks, I subtract the dividend from the increased divisor value, and set this difference as my new dividend. This continues till my modified dividend is greater than the initial divisor. I keep track of the number of times the dividend changed, and if this count is even, the remainder is the current dividend, otherwise, it’s the difference of the initial divisor and the current dividend.
6. Intal Pow: The approach I have applied for this divides the problem into subproblems of size y/2 and calls the subproblems, recursively. The base condition is for the power to 0, which is 1. Depending on whether the index to be raised is even or odd, the function is called recursively. This implementation is faster than the brute force method of calculating the power term, with repeated multiplication.
7. Intal GCD: A simple implementation of the Euclidean formula for GCD has been applied to this function, as suggested in the problem statement. This applies recursion as well, but is better than brute force. A special case, when both the numbers are 0, although undefined, has been handled to return 0.
8. Intal Fibonacci: The function to calculate the nth fibonacci number implements the same logic we apply when calculating the number by hand. The nth fibonacci number is the sum of the n-1th and the n-2nd number. The recurrence relation is of the form: Fn = Fn-1 + Fn-2. My implementation doesn’t use recursion, but applies a space optimised dynamic programming approach. Instead of storing all numbers until we get to n, I keep track of only the n-1th and the n-2md number, nad keep switching them out if they are not needed.
9. Intal Factorial: I have made use of a helper function by the name of product( ) for this function, which gives me the product of two numbers that it gets, this function is repeatedly called in a loop until I have arrived at the number n.
10. Intal BinCoeff: This problem involves the overlapping subproblems property. Hence I have taken a dynamic programming approach to this problem. A temporary array is built in the bottom up manner. An optimisation has also been made in terms of space, so that the function uses at max O(k) space. Pascal's identity, C(n,k) = C(n-1,k) + C(n-1,k-1) has been applied.
11. Intal Max: I have used the intuitive approach to find the maximum value in an array for this function. I assume the first element to be the maximum in a given array. As I traverse the array, on encountering a larger number, I store the larger number as the maximum and continue till I have reached the end of the array. The number stored as maximum will be my greatest or Max element. I have used intal compare to find the larger of two numbers for the above purpose.
12. Intal Min: The core logic is the same as that for max. Intal compare is used. A single pass through the array has to be made, as is the case with Max as well. The 1st element is assumed to be the Minimum from the array, until a small value is encountered.
13. Intal Search: I have applied a brute force method of searching the intal in the given array for this function. Each element is compared with the key element, with the help of intal compare. Upon finding the element, the flag is set to 1 and returned.
14. Intal Sort: For the purpose of sorting this array of intals, I have applied the quick sort algorithm. It follows the principle of divide and conquer, and thus is faster than a brute force search. It is an O(log n) algorithm, as the problem statement requires.
15. Intal BinSearch: The algorithm of binary search has been implemented for this function. It makes O(log n) comparisons at worst. The sorted array is split in half everytime the search element isn’t found in a given portion of the array.
16. Intal Coin-Row: Again, the use of Dynamic programming comes in handy for this question. The recurrence for this problem is as follows: F(n) = max{Coins[n] + F[n − 2], F[n − 1]} for n > 1, F(0) = 0, F(1) = Coins[1].
The last element of the DP Table contains the answer to the problem.
Future Scope:
The amount of places where large numbers like intals come into use is uncountable in the modern world. Many fields of science use big numbers such as these multiple times a day. They can benefit from using libraries such as this one. Extra functionality can be added by defining even more functions than the ones covered in this project. The support for negative numbers can be added as well, as well as decimal floating point numbers. These can enable a fully functional and useful library that can help with the storage and manipulation of numbers that are too large to be stored in normal data structures. If no restrictions were imposed, I would try to implement this library in the language of Python, as it is the choice of many data scientists, who work with such large numbers on a day to day basis. It would be of great use in the language of Python, which is already enriched with many similar libraries, which ease the processing of large data.