How to convert large integers to base 2^32?

Question

First off, I'm doing this for myself so please don't suggest "use GMP / xint / bignum" (if it even applies).

I'm looking for a way to convert large integers (say, OVER 9000 digits) into a int32 array of 2³² representations. The numbers will start out as base 10 strings.

For example, if I wanted to convert string a = "4294967300" (in base 10), which is just over INT_MAX, to the new base 2³² array, it would be int32_t b[] = {1,5}. If int32_t b[] = {3,2485738}, the base 10 number would be 3 * 2^32 + 2485738. Obviously the numbers I'll be working with are beyond the range of even int64 so I can't exactly turn the string into an integer and mod my way to success.

I have a function that does subtraction in base 10. Right now I'm thinking I'll just do subtraction(char* number, "2^32") and count how many times before I get a negative number, but that will probably take a long time for larger numbers.

Can someone suggest a different method of conversion? Thanks.

EDIT
Sorry in case you didn't see the tag, I'm working in C++

Answer 1

Assuming your bignum class already has multiplication and addition, it's fairly simple:

 bignum str_to_big(char* str) {
     bignum result(0);
     while (*str) {
         result *= 10;
         result += (*str - '0');
         str = str + 1;
     }
     return result;
 }

Converting the other way is the same concept, but requires division and modulo

std::string big_to_str(bignum num) {
    std::string result;
    do {
        result.push_back(num%10);
        num /= 10;
    } while(num > 0);
    std::reverse(result.begin(), result.end());
    return result;
}

Both of these are for unsigned only.

Answer 2

To convert from base 10 strings to your numbering system, starting with zero continue adding and multiplying each base 10 digit by 10. Every time you have a carry add a new digit to your base 2^32 array.

Answer 3

The simplest (not the most efficient) way to do this is to write two functions, one to multiply a large number by an int, and one to add an int to a large number. If you ignore the complexities introduced by signed numbers, the code looks something like this:

(EDITED to use vector for clarity and to add code for actual question)

void mulbig(vector<uint32_t> &bignum, uint16_t multiplicand)
{
    uint32_t carry=0;
    for( unsigned i=0; i<bignum.size(); i++ ) {
        uint64_t r=((uint64_t)bignum[i] * multiplicand) + carry;
        bignum[i]=(uint32_t)(r&0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}

void addbig(vector<uint32_t> &bignum, uint16_t addend)
{
    uint32_t carry=addend;
    for( unsigned i=0; carry && i<bignum.size(); i++ ) {
        uint64_t r=(uint64_t)bignum[i]  + carry;
        bignum[i]=(uint32_t)(r&0xffffffff);
        carry=(uint32_t)(r>>32);
    }
    if( carry )
        bignum.push_back(carry);
}

Then, implementing atobignum() using those functions is trivial:

void atobignum(const char *str,vector<uint32_t> &bignum)
{
    bignum.clear();
    bignum.push_back(0);
    while( *str ) {
        mulbig(bignum,10);
        addbig(bignum,*str-'0');
        ++str;
    }
}

Answer 4

I think Docjar: gnu/java/math/MPN.java might contain what you're looking for, specifically the code for public static int set_str (int dest[], byte[] str, int str_len, int base).

Answer 5

Start by converting the number to binary. Starting from the right, each group of 32 bits is a single base2^32 digit.