BigInt Library for C and C++ language.

Description:

Always face problem with big values in C or C++, well from now onwards, you don't have to because here is a BigInt Library for your problem.

What is BigInt?

BigInt is a inbuilt library provided by java to handle very large values efficiently and effectively.So I have tried to implement same functionality in C because it doesn't support any such thing.

Why we need BigInt?

This data type allows us to safely perform arithmetic operations on large integers without implementing our own methods or functions. In many Real world problems, we have to deal with very large values that can't be fit inside the range available, so that's where it helps a lot and saves precious time of a programmers.

Features:

Store as big number as you want.
can perform multiplication division, addition, subtraction on very big numbers.
Allows to calculate factorial of any value.
calculate as big power of a number as you want.

How this Idea came:

Many a times while solving problems, we need to deal with large values which can't fit in the 64-bit variable as well.
We can't get the exact answer sometimes just because it does'nt fit in the range, so we need to find the answer under some modulo.
To ease the task of programmers of implementing their own classes every time.

Why BigInt instead of inbuilt data types:

allows performing arithmetic operation on as big number as user want.
No need to worry about overflows.
No need to worry about modulo.
Useful when exact answer is required instead of under modulo.

Design And Specification:

First Problem was that how to allow as big number as user want. To resolve this issue, I have first implemented the dynamic string class which can store as big number as user wants. It stores the number in the form of string.

Created 2 files :

"string.h"
"BigInt.h"

Note: Here I will be only explaning about BigInt class and its feature, if you want to know more about string class, you can check that Here

Working of BigInt Class:

Working:

clone the 2 repositories first to your local pc by writing following commands in git Bash

git clone "https://github.com/Abhishek-1208/BigInt-Library-for-C-and-Cpp"
git clone "https://github.com/Abhishek-1208/string-file-for-C.git".

Now Run following Commands

gcc -c string.c BigInt.c
ar -cvr libBigInt.a string.o BigInt.o

Now you're done with the setup part.

Note: Don't forget to include BigInt file in your program by writing #include "BigInt.h".

commands to compile your program:

gcc file_name.c -o file_name.exe -L .lBigInt
./file_name.exe to run your program.

Initialization:

You can initialize a variable of BigInt type by writing "struct BigInt *var_name = _assign("");"
You can also initialize a variable with some pre defined value by passing it to function as follow: "struct BigInt *var_name = __assign(struct BigInt *var2);"

Now Since We're done with the initialization part, lets see the different functionalities and operations on BigInt.

Functions used internally to check for valid input and crop the garbage part:

1. To check whether given input is a number or not:

   Syntax:           is_num(var1); 

   Task:             checks whether given input is a number or not. 
 
   return type:      int. returns 0 if input is not a number otherwise 1. 

   Algorithm Used:   Simple check. 

   Time Complexity:  O(n) , where n = digits in var1 

   Space Complexity: O(1)

2. To crop the extra part if user entered. For eg: -00123 will be croped to -123 and 0028 will be croped down to 28.

   Syntax:           crop(var1);

   Task:             crop the unnecessary part.

   return type:      void

   Algorithm Used:   Simple implementation

   Time Complexity:  O(n) , where n = digits in var1

   Space Complexity: O(1)

Some Standard Functions:

To take Input from user:

   Syntax:      struct BigInt *var_name = _input();

   return Type: struct BigInt*

   Exception:   throws error if input is not a number

To Print Values:

   Syntax:     _print(struct BigInt *inp)   : print the value without putting end of line after the number.

   Syntax:     _println(struct BigInt *inp) : print the value and move the cursor to next line.

   return type: void for both.

Arithmetic Operations:

##### Addition:       add(var1, var2);        equivalent to var1 + var2

##### Subtraction:    subtract(var1, var2);   equivalent to var1 - var2

##### Multiplication: multiply(var1, var2);   equivalent to var1 * var2

##### Division:       divide(var1, var2);     equivalent to var1 / var2

##### Modular:        modulo(var1, var2);     equivalent to var1 % var2

1. Addition:

   Syntax:           add(var1, var2);

   Task:             Perform var1 + var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n + m) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(max(n, m)) , To store the final value and return.

2. Subtraction:

   Syntax:           subtract(var1, var2);

   Task:             Perform var1 - var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n + m) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(max(n, m)) , To store the final value and return.

3. Multiplication:

   Syntax:           multiply(var1, var2);

   Task:             Perform var1 * var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n * m) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(n + m) , To store the final value and return.

4. Division:

   Syntax:           divide(var1, var2);

   Task:             Perform var1 / var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Throws error if either of var1 or var2 is not an integer or if var2 is 0.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n * m) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(max(n, m)) , To store the final value and return.

5. Modular:

   Syntax:           modulo(var1, var2);

   Task:             Perform var1 % var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Throws error if either of var1 or var2 is not an integer or if var2 is 0.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n * m) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(max(n, m)) , To store the final value and return.

6. power:

   Syntax:           power(var1, var2);

   Task:             Perform var1 ^ var2 and return the result of it.

   return type:      BigInt type.

   Exception:        Works for var2 >= 0.

   Algorithm Used:   Binary Exponentiation.

   Time Complexity:  O(log2(var2))

   Space Complexity: O(1)

Relational Operations:

Note: return value of all these 6 relations function will be either 1 or 0. 1 for true(condition is true) and 0 for false(condition is false).

1. less than:

   Syntax:           less_than(var1, var2);

   Task:             Perform var1 < var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

2. less than or equal to:

   Syntax:           less_than_equal(var1, var2);

   Task:             Perform var1 <= var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

3. greater than:

   Syntax:           greater_than(var1, var2);

   Task:             Perform var1 > var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

4. greater than or equal to:

   Syntax:           greater_than_equal(var1, var2);

   Task:             Perform var1 >= var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

5. Equality:

   Syntax:           are_equal(var1, var2);

   Task:             Perform var1 == var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

6. Not Equal:

   Syntax:           are_not_equal(var1, var2);

   Task:             Perform var1 != var2 and return the result of it.

   return type:      int.

   Exception:        Throws error if either of var1 or var2 is not an integer.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(max(n, m)) , where n = digits in var1, m = digits in var2.

   Space Complexity: O(1) , To store the final value and return.

Utility Functions:

1. itob(int number):

   Syntax:           itob(number);

   Task:             converts integer data type to BigInt data type
   return type:      BigInt data type pointer .

   Exception:        No exception.

   Algorithm Used:   School Mathematics.

   Time Complexity:  O(n) , where n = digits in number.

   Space Complexity: O(1) , To store the final value and return.

2. swap(struct BigInt inp1, struct BigInt inp2):

   Syntax:           swap(&var1, &var2);

   Task:             swaps the passed 2 BigInt data type variables value
   return type:      void .

   Exception:        No exception.

   Algorithm Used:   brute force.

   Time Complexity:  O(1)

   Space Complexity: O(1) , To store the final value and return.

3. _change(struct BigInt **inp, char *number):

   Syntax:           _change(&var, "123");

   Task:             changes the value of first paramter to second parameter. i.e var = 123.
   return type:      void .

   Exception:        Throws error if number is not representing an integer.

   Algorithm Used:   brute force.

   Time Complexity:  O(n) , where n = digits in number.

   Space Complexity: O(1) , To store the final value and return.

4. __change(struct BigInt **inp, struct BigInt *number):

   Syntax:           __change(&var, value);

   Task:             changes the value of first paramter to second parameter. i.e var = value.
   return type:      void .

   Exception:        No exception.

   Algorithm Used:   brute force.

   Time Complexity:  O(n) , where n = digits in number.

   Space Complexity: O(1) , To store the final value and return.

5. absolute(struct BigInt *number):

   Syntax:           absolute(number);

   Task:             returns the absolute value of number
   return type:      BigInt data type pointer .

   Exception:        No exception.

   Algorithm Used:   brute force.

   Time Complexity:  O(1).

   Space Complexity: O(1) , To store the final value and return.

mr-mxyztplk / bigint-library-for-c-and-cpp Goto Github PK

bigint-library-for-c-and-cpp's Introduction