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 l开发者_StackOverflow中文版arger than b.

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

---

Basically what you want to do is implement a div/mod b in base a, and then do that repeatedly on the source number, building up the target number. When b < a, the classical long division algorithm is both the simplest and most efficient way of doing this, since you'll always be dealing with single digits. When b > a, its a bit trickier; you can use the classic long division, or implicitly first convert the number to base a^k where a^k >= b and fits in an int (a trivial conversion), and then use the single digit long division method to convert to b.

Of course, if a == b^k or a^k == b (one base is an integer power of the other) its quite trivial, as you don't need division at all. A lot depends whether 'a' and 'b' are actual constants that won't change, or whether they are variables.

template<int A, int B> int divmod(std::vector<int> &a) {
    // a is a vector of digits in base A
    // divide a by B in place, returning the remainder
    // implementation left as an exercise for the reader
}

template<int A, int B> std::vector<int> cvtBase(std::vector<int> a) {
    // a is a vector of digits in base A
    // convert it to a vector of digits in base B
    // vectors are in little endian order (least significant digit first)
    std::vector<int> b;
    do {
        b.push_back(divmod<A,B>(a));
    } while (!isZero(a));
    return b;
}

---

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.