————— the next day —————
— — — — — —
What does the vertical look like in the program? Let’s take 426709752318 + 95481253129 as an example to see the detailed steps of adding large integers:
The first step is to store the integers in reverse order. The one bit of the integer is stored at the index 0 and the highest bit is stored at the index -1 of the array length. The reverse order is more consistent with the way we access arrays from left to right.
The second step is to create a result array whose maximum length is the number of bits of a larger integer +1 for obvious reasons.
The third step is to traverse the two arrays, adding the elements by their respective indices from left to right, like a schoolboy doing vertical calculations.
In this example, the first addition is 8 of array A and 9 of array B, resulting in 7, carried 1. Populate 7 with the corresponding subscript of the Result array and carry 1 with the next position:
The second group adds the 2nd element (1) of A and the 2nd element (2) of B, resulting in 3, plus the previous round (1), and populates the corresponding index (4) of the Result array:
The third group adds the 3rd element of A (3) and the 3rd element of B (1), resulting in 4, and populates 4 with the corresponding index of the Result array:
The fourth group adds the fourth element of A (2) and the fourth element of B (3), resulting in 5. Fill 5 with the corresponding index of the Result array:
And so on…… Add all the elements of the array:
Step 4 reverse all the elements of the Result array, removing the first element from the Result array:
How do you optimize it?
We used to break up large integers by decimal bits. For example, if large integers are 50 bits long, we need to create a 51-bit array with each element of the array storing one bit.
Do we really need to break the original integers down to that much detail? Obviously not, just break it down to a point where it can be computed directly.
The value of the int type ranges from -2147483648 to 2147483647, and contains a maximum of 10 digits. To prevent overflow, we can add every 9 bits of the large integer as an element of the array. (This can also be split using long, but splitting by int scope is just an idea.)
So the footprint, the number of operations, is reduced by a factor of nine.
If you like this article, please long click the picture below to follow the subscription number programmer Xiao Grey and watch more exciting content
