I am writing for my needs a small library for working with long numbers. He wrote both addition and multiplication by the Karatsuba method. It is correct, but I keep the data in the uint vector in 1000 * 1000 * 1000 number system, that is, 9 decimal digits per element of the vector: {123456789, 987654321, 456789123} But I see that in Java and C # there are already ready BigInteger classes, and methods there are such bitCount and a constructor accepting a binary number. That is, numbers are stored in binary form, and not in decimal? I can not understand why to store in binary form? Will it be faster? I simply cannot find information about this, everywhere I read about long arithmetic, numbers for long arithmetic are presented in decimal form. Now if you store in binary form, then how to translate a number of 500 characters into a decimal string? First translate into decimal form, and then into a string? I would be grateful if you give a link which describes the long arithmetic presented in binary form.
- Did you watch the source code BigInteger (java)? - Mikhail Vaysman
- I watched, but could not understand. I saw that there is not a 1000 * 1000 * 1000 storage system, but 2 ^ 32, but further to understand what I could not do - van9petryk
1 answer
"Long" numbers are stored inside not "in binary" or "decimal" form . Numbers in the internal representation are not at all numbers in any number system. The number system appears only when translating a number into a string representation.
Okay, how are the numbers stored? In .NET you can see in the sources that they are stored as a list of Int32 numbers, that is, a list of 32-bit numbers.
In addition, each 32-bit number acts as a single digit, so that we can assume that the representation in the number system on the basis of 2 ³² is used internally.
Why not use decimal digits one digit at a time? The fact is that at the same time storage will be less efficient: for a 32-bit number all its possible values are used, and at least one byte is used to represent one decimal digit (which could store up to 256 different values).
Further, operations with native 32-bit words are much more efficient than operations with 10-digit digits. When calculating in a 10-ary system, to calculate the sum, separation of the discharge result from the transfer requires dividing by 10. And when calculating with 32-bit words, the result is by itself, because the processor automatically adds 32-bit result and transfer, division is not necessary at all.
The same applies to multiplication.
And a large decimal string is translated into a “long” number in the same way as a small decimal string into an int or long .
