Large numbers multiplication in C++

Question

I am looking for a fast large numbers multiplication algorithm in C++. I have tried something like this but I think I am creating too many string objects.

string sum(string v1, string v2)
{
    string r;
    int temp = 0, i, n, m;
    int size1 = v1.size(), size2 = v2.size();
    n = min(size1, size2);
    m = max(size1, size2);
    if ((v1 == "0" || v1 == "") && (v2 == "0" || v2 == "")) return "0";
    r.resize(m, '0');
    for (i = 0; i < n; i++)
    {
        temp += v1[size1 - 1 - i] + v2[size2 - 1 - i] - 96;
        r[m - 1 - i] = temp % 10 + 48;
        temp /= 10;
    }
    while (i < size1)
    {
        temp += v1[size1 - 1 - i] - 48;
        r[m - 1 - i] = (char)(temp % 10 + 48);
        temp /= 10;
        ++i;
    }
    while (i < size2)
    {
        temp += v2[size2 - 1 - i] - 48;
        r[m - 1 - i] = (char)(temp % 10 + 48);
        temp /= 10;
        ++i;
    }
    if (temp != 0) 
        r = (char)(temp + 48) + r;
    return r;
}

string multSmall(string v1, int m)
{
    string ret = "0";
    while(m)
    {
        if (m & 1) ret = sum(ret, v1);
        m >>= 1;
        if (m) v1 = sum(v1, v1);
    }
    return ret;
}

string multAll(string v1, string v2)
{
    string ret = "0", z = "", pom;
    int i, size;
    if (v1.size() < v2.size())
        std::swap(v1, v2);
    size = v2.size();
    for (i = 0; i < size; i++)
    {
        pom = multSmall(v1, v2[size - 1 - i] - 48);
        pom.append(z);
        ret = sum(ret, pom);
        z.resize(i + 1, '0');
    }
    return ret;
}

I DON'T want do use any external libraries. How should I do it? Maybe I should use char arrays instead of strings? But I am not sure if reallocating memory for an array would be faster than creating string object.

Take a look at this: http://stackoverflow.com/a/1218185/4342498 — NathanOliver, Feb 12 '15 at 19:43
possible duplicate of [Arbitrary-precision arithmetic Explanation](http://stackoverflow.com/questions/1218149/arbitrary-precision-arithmetic-explanation) — Jim Lewis, Feb 12 '15 at 19:51
Your desire to do "fast large number multiplication" and your implementation of storing large numbers as ascii-encoded decimal strings are fundamentally at odds with each other. If you really want fast, then you'll want to implement your numbers as an array of full word-sized integers (whether that's 32-bits or 64-bits). If you want to store as ascii strings, then you'll need to compromise on the "fast" bit... — twalberg, Feb 12 '15 at 20:38

score 0 · Accepted Answer · answered Feb 12 '15 at 20:31

Fast large number multiplication is a big project. A very big project depending upon just how large of numbers you want to multiply.

Probably the simplest important thing, however, is that you want to get as much mileage out of your CPU's native instructions as possible. Addition of 64-bit numbers is 8 times more powerful than addition of 8-bit numbers, and over 19 times more powerful than addition of decimal digits. But your computer can probably add 64-bit numbers just as quickly as it can add 8-bit numbers, and a lot faster than any code you write to do addition of decimal digits.

Multiplication is much more dramatic; an instruction that multiplies two 64-bit numbers to produce a 128-bit result is doing around 64 times more work than an instruction that multiplies two 8-bit numbers to produce a 16-bit result -- but your CPU can probably do them at the same speed, or maybe the latter is twice as fast as the former.

So, you really want to orient your data structures and base case algorithms around the idea of using these more powerful instructions as much as you can.

If you need to, you can think of it as doing arithmetic in base 2^64. (or maybe base 2^32, if you can't or don't want to use 64-bit arithmetic)

Large numbers multiplication in C++

1 Answers1