Large integer base / base conversion from 10 ^ x to 2 ^ x

Question

Introduction

I study computer math by writing and refining my own BigInt library. So far, my first incarnation stores each digit of the base number 10 in successive elements of the vector. It can be multiplied and added with arbitrary precision. I want to speed it up using all the space available to me in the standard C ++ data type by converting to a 2 ^ x base.

Information

I am reading 1000 or more digits from stdin in base 10 and I want to convert them to base 2 ^ x so that I can easily store them in an array or vector of one of the standard C ++ data types, probably an unsigned int. I have only one idea how to do a basic transformation, re-division with the remainder method. Below is the C ++ code describing this method:

vector<int> digits; while(num!=0) { int mod = num%base; num = num/base; digits.push_back(mod); } 

Puzzles

Some of the things that I have lost are whether division with remainder is the correct way to convert bases to large integers. I tried to see how the GMP library does it. gmp / mpn / generic / set_str.c is the corresponding c source file where the “magic” happens, but I'm not sure what happens there. Matt McCutchen BigInt seems to use re-division with the remainder method. If I use this method, I basically need to write two versions of my BigInt class, one for working in Base10, and the other for Base2 ^ x.

Conclusion

• We offer recommendations on the right steps to convert a huge number from a string into an array of 32-bit words.
• Help me find out how GMP converts a string into an array of 32-bit words, without wading through many levels of abstraction.

Examples Using 4-bit Word Size

The number we want to keep (obviously on a small size): 123456789

unsigned chars have a range of 0-255, if we want to split our number and store it in a vector, we can do this in one of three ways:

• As base 10, our vector is as follows: [1,2,3,4,5,6,7,8,9]
  • This is what my vector looked like in my first implementation.
• As the base 100, our vector is as follows: [1,23,45,67,89]
  • It is easy to convert from base 10 to base 100, it has ciel elements (numbers in base10 / 2).
• As a base 256, our vector is as follows: [7,91,205,21]

Obviously, the third solution is the most optimal for the internal representation and what I'm trying to get to.

Answer 1

After multiplying and adding functions that work for your bigint library, converting a string to bigint is simplicity. Start with the result of converting zero. For each digit you are processing (from left to right), multiply the previous result by 10 and add the value of the new digit (using the multiply and add bigint functions).

Answer 2

In general, to convert one database to another (from the most significant digit to the smaller), the algorithm looks as follows:

 output = 0 foreach digit in digits: output = output * base + digit 

In reverse, this means the following:

 output = 0 multiplier = 1 foreach digit in digits: output = output + multiplier * digit multiplier = multiplier * base 

You can use your bigint library recursively using this math to figure out how to store numbers. By this, I mean that you need to implement BigInt * BigInt and BigInt + BigInt, so that you can convert the databases. This is not the most efficient way, but it is much faster than division.

Answer 3

One thing not mentioned in the FryGuy post is that in this method arithmetic should be performed in the base in which you convert to , while the base that is used as the multiplier is the same as the base of your original number; a base that you no longer want, or a base that you are converting from .

There are two formulas for converting radix to integers. (1) uses base B, which we will convert to (destination base), as a repeating divisor associated with arithmetic performed in base b, where b is the basic transformation of , (2) on the other hand, uses base b as a factor on the numbers that we convert that are in the same base b and performs arithmetic in base B.

(1) the formula uses B as a parameter and performs arithmetic in base b

(2) the formula uses b as a parameter and performs arithmetic in base B

it's not ok volume 2 4.4 radius conversion