In .NET development, sometimes because of the knowledge content of some marginal subjects, such as statistics, finance, astronomy and other calculations, encryption and decryption algorithms will involve large number operations. Even if the largest numerical type in .net is stored, it will overflow. Number, one of my ideas is to use numeric types when calculating, and store (temporarily) and output as strings. Then when storing, BOX[n] n arrays are needed to temporarily store the results of a small step in the calculation.
'As an example
=================== Algorithm understanding diagram =======================
'97*97*97*97*97 = 8587340257 box(1) = 587340257 box(2)=8
'97*97*97*97*97*97 = 832972004929 box(1) = 972004929 box(2)=832
'97*97*97*97*97*97*97 = 80798284478113 box(1) = 284478113 box(2)=80798
'97*97*97*97*97*97*97*97 = 7837433594376961 box(1) = 594376961 box(2)=7837433
'97^ 9 = 760231058654565217 box(1) = 654565217 box(2)=760231058
'97^ 10 = 73742412689492826049 box(1) = 492826049 box(2)=742412689 box(3)=73
… … … … … …
Note that the larger the box in the table below, the higher the corresponding number. When using the above algorithm, remember to ① first define the number of digits of a BOX, for example, the above is 9 digits (according to needs and actual conditions),
②Due to calculation habits, many people will first calculate the number of box(n+1) digits when counting from the bottom position {box(0 -> n)}, and then add the carry number generated by box(n) (such as the first Calculate box(1) to box(2)=0 to generate a carry number of 8 box(2)+carry number = 8) for processing, such as the above addition processing ③ It is best to start from the high position, you will save a lot of trouble, The number of boxes is unknown. It doesn't matter. Use a dynamic array. When it is full (the number of carries generated by the highest subscript box), add another one. When there is a modulo operation, if the modulus is not large, you can also use the above idea to calculate the modulus in pieces and then link. The box is a temporary result, and the box is redistributed (it must be re-truncated from the high position). For example, if it is modulo 123456789123456789, set a box with eight digits. box(1)=89 box(2)=91234567 box(3)=12345678. Each box takes the modulus respectively. Reunion (traditional is 123456789123456789 ÷ 333=370741108478849 modulus is 72) Then the redistributed box should be box(1) =478849 box(2) =370741180 but not box(1) =370741180 box(2) = 478849 Why? ∵ Start taking the modulus from the high position. If box(n) does not change after being modulo once, the result of taking the modulus again does not change and the result is box(n) = box(n). The program will enter an infinite loop.
Another situation involving large number operations is to take the modulo of A raised to the nth power (A ^n mod V). If the mod number is not large, it can be done (it ends after n A mod) ((A mod V)* A mod V) * A mod V... This algorithm does not necessarily need to be implemented recursively, a simple loop can be used, with up to two levels of nested loops.
Final advice: When adding, subtracting, multiplying or dividing a large number, do not easily factorize the dividend (addition/subtraction/multiplication/division). This algorithm will be very inefficient.
(The article was written in a hurry, there may be typos, please forgive me)
Source: same BLOG