This library is for educational purposes only!
c++ implementation of arbitrary size and precision numbers and arithmetics with them.
Large int is represented as an array of polynomial (a0 + a1 * x + a2 * x^2 + a3 * x^3 + ...) coefficients, where x is a base of a number. Coefficients are stored in reverse order (from LSD to MSD), as it is more efficient to push in the end of an array.
The sign is stored separately in bool variable, where "-" is true and "+" is false. Negative integers are stored in 2's complement form (see https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html).
EXAMPLE
Base is defined via template parameter - for simplicity lets use uint8_t - base 2^8 = 256.
Decimal | Sign | Coefficients |
---|---|---|
0 | + | 0 |
1 | + | 1 |
-1 | - | 255 |
256 | + | 0, 1 |
-256 | - | 0, 255 |
Large float is represented as mantissa and exponent: M * B^E where M - mantissa, B - base and E - exponent.
EXAMPLE
Also lets take base 2^8
Decimal | Mantissa | Exponent |
---|---|---|
0.0 | 0 | 0 |
1.0 | 1 | 0 |
-1.0 | -1 | 0 |
256.0 | 1 | 1 |
0.5 | 128 | -1 |
-0.5 | -128 | -1 |
0.75 | 192 | -1 |
-0.5 | -128 | -1 |
NOTES
Some finite decimal fractions cannot be represented in base of 2s power. For example, a number 0.1 is represented as infinite periodic fraction that is being rounded when converting to decimal representation in string.
- Addition. Just like addition on paper - coefficient by coefficient. Adding negative numbers works automatically because they are stored in 2's complement form.
- Subtraction. The same as addition.
- Multiplication. Summing up each term just like on paper - coefficient by coefficient.
- Division. See https://en.wikipedia.org/wiki/Division_algorithm#Integer_division_(unsigned)_with_remainder
- Addition. Firstly we adjust exponents of 2 numbers to be equal and then perform integer addition with mantissa.
- Subtraction. The same as addition.
- Multiplication. Multiply mantissas and add exponents. Remove overflowing coefficients.
- Division. See https://en.wikipedia.org/wiki/Division_algorithm#Newton%E2%80%93Raphson_division