Search code examples
c++radix

Converting vector of digits from base to base

How can I convert a vector<int> in base a to vector<int> in base b without the use of a library like gmp?
The contain the digits of the numbers. a and b are less than 1024. a can be smaller or larger than b.
I thought about using the standard base conversion algorithm but the numbers won't fit even in long long.

Solution

  • I thought about using the standard base conversion algorithm but the numbers won't fit even in long long.

    This is the correct (as in: “clean”) approach. Since the numbers won’t fit in a native number type, and you don’t want to use existing libraries, you essentially need to implement your own number type, or at least the necessary operations (addition, division, modulus) that you need for the conversion algorithm.

    The easiest (though not the most efficient) way is to implement the classical long division algorithm.