Use a vector of integers instead of a string for faster computation

[faheel]

Instead of having the number's magnitude stored in a string, it would be much more efficient, in terms of both time and space, to have it stored in a vector of unsigned 64-bit integers (std::vector<uint64_t>). That is, store a number's digits in base 2⁶⁴.

The following table lists how the number's magnitude will be represented in base 2⁶⁴:

Magnitude	Representation	Comment
0	{0}	0⋅(264)0
1	{1}	1⋅(264)0
2	{2}	2⋅(264)0
264 - 1	{18446744073709551615}	18446744073709551615⋅(264)0
264	{0, 1}	1⋅(264)1
264 + 1	{1, 1}	1⋅(264)0 + 1⋅(264)1
264 + 2	{2, 1}	2⋅(264)0 + 1⋅(264)1
265	{0, 2}	2⋅(264)1
550	{11670147153572883801, 4814824860968089}	11670147153572883801⋅(264)0 + 4814824860968089⋅(264)1
2128	{0, 0, 1}	1⋅(264)2
2192	{0, 0, 0, 1}	1⋅(264)3
2256	{0, 0, 0, 0, 1}	1⋅(264)4

The way how it could speed up performance is that, for example, when adding two BigInts, instead of adding their corresponding decimal digits together, their corresponding base 2⁶⁴ digits will be added, each digit in a single operation. Moreover, this addition (or any other arithmetic operation) of vectors can be vectorised by using SSE or AVX, which would further improve performance by a few folds.

Say, for instance, that you were adding two 5000 digit numbers. In base 10 they have 5000 digits, which means that it would take 5000 operations to add them together. Instead, if they were in base 2⁶⁴, they would have 260 digits, and would therefore require only 260 operations. Using AVX-512, vectors with up to 8 64-bit digits can be added together in a single operation. Which means that by using vectorized operations, two 5000 digit numbers could be added using just 33 operations.

[surajumang]

The idea of using numbers in base 2^64 seems interesting. But the representation you have used is quite opposite of what is used commonly i.e Leftmost digit is the most significant one and rightmost digit is the least significant. Is there any reason behind this choice?

[faheel]

@surajumang Since all arithmetic operations (except division) are done from right to left, it's simpler to store the right-most digit as the first digit in an array since it will be processed first. But this is just to make the code simpler. When written formally, the most significant digits are always written first, followed by less significant digits to the right.

[surajumang]

I would like to work on this but think it will require a complete overhaul of the existing codebase like redefining all the arithmetic operations. What do you say?

[faheel]

@surajumang Yes, it would require a complete rewrite of all the arithmetic operators and a few other methods.

I'll be creating a new branch and will implement some basic stuff like converting from base 10 to base 2⁶⁴. Once that's done, I'll notify you and you can contribute to that branch.

[faheel]

@SingleJourney English please! Google Translate isn't perfect :)

[OmriHab]

Could you let me know when you've added that branch?
I would like to help contribute to the math functions using the new representation and anything else.

[faheel]

@surajumang @OmriHab I've added the branch base-2-to-the-64. The changes made so far on this branch can be tracked by comparing the branch with master.

[OmriHab]

Can i recommend using uint64_t from cstdint, instead of unsigned long long?
unsigned long long is promised to be at least 64 bit but not certainly exactly 64.
I assume that could create some problems if you use calculations that assume base 2^64.

[OmriHab]

Alternatively unsigned long long can be used and just take into consideration that it isn't necessarily 64 bit.
E.g the maximum would be numeric_limits<unsigned long long>::max() instead of UINT_64_MAX

[surajumang]

if you are implementing any feature then probably you should create a issue and then implement that particular feature like first create issue Implement sum of BigInts in vectorized implementation and then sumbit PR for that particular issue. This way different people can work on it

[faheel]

@OmriHab Good suggestion! I'll change the type to uint64_t.