C++ BigInt multiplication conceptual problem

Question

I'm building a small BigInt library in C++ for use in my programming language.

The structure is like the following:

short digits[ 1000 ];
int   len;

I have a function that converts a string into a bigint by splitting it up into single chars and putting them into digits.

The numbers in digits are all reversed, so the number 123 would look like the following:

digits[0]=3 digits[1]=3 digits[2]=1

I have already managed to code the adding function, which works perfectly.

It works somewhat like this:

overflow = 0
for i ++ until length of both numbers exceeded:
  add numberA[ i ] to numberB[ i ]
  add overflow to the result
  set overflow to 0
  if the result is bigger than 10:
    substract 10 from the result
    overflow = 1
  put the result into numberReturn[ i ]

(Overflow is in this case what happens when I add 1 to 9: Substract 10 from 10, add 1 to overflow, overflow gets added to the next digit)

So think of how two numbers are stored, like those:

   0 | 1 | 2
   ---------
A  2   -   -
B  0   0   1 

The above represents the digits of the bigints 2 (A) and 100 (B). - means uninitialized digits, they aren't accessed.

So adding the above number works fine: start at 0, add 2 + 0, go to 1, add 0, go to 2, add 1

But:

When I want to do multiplication with the above structure, my program ends up doing the following:

Start at 0, multiply 2 with 0 (eek), go to 1, ...

So it is obvious that, for multiplication, I have to get an order like this:

   0 | 1 | 2
   ---------
A  -   -   2
B  0   0   1 

Then, everything would be clear: Start at 0, multiply 0 with 0, go to 1, multiply 0 with 0, go to 2, multiply 1 with 2

• How can I manage to get digits into the correct form for multiplication?
• I don't want to do any array moving/flipping - I need performance!

Answer 1

1. Why are you using short to store digits in the [0..9] a char would suffice
2. You're thinking incorrectly about the multiplication. In the case of multiplication you need a double for loop that multiplies B with each digit in A and sums them up shifted with the correct power of ten.

EDIT: Since some anonymous downvoted this without a comment this is basically the multiplication algorithm:

bigint prod = 0
for i in A
    prod += B * A[i] * (10 ^ i)

The multiplication of B with A[i] is done by an extra for loop where you also keep track of the carry. The (10 ^ i) is achieved by offseting the destination indices since bigint is in base 10.

Answer 2

Andreas is right, that you have to multiply one number by each digit of the other and sum the results accordingly. It is better to multiply a longer number by digits of the shorter one I think. If You store decimal digits in Your array char would indeed suffice, but if you want performance, maybe you should consider bigger type. I don't know what Your platform is, but in case of x86 for example You can use 32 bit ints and hardware support for giving 64 bit result of 32 bit multiplication.

Answer 3

I'm building a small BigInt library in C++ for use in my programming language.

Why? There are some excellent existing bigint libraries out there (e.g., gmp, tommath) that you can just use without having to write your own from scratch. Making your own is a lot of work, and the result is unlikely to be as good in performance terms. (In particular, writing fast code to perform multiplies and divides is quite a lot trickier than it appears at first glance.)

Answer 4

Your example in the question is over-engineering at its best in my opinion. Your approach will end up even slower than normal long multiplication, because of the shear number of multiplications and additions involved. Don't limit yourself to working at one base digit at a time when you can multiply approximately 9 at a time!. Convert the base10 string to a hugeval, and then do operations on it. Don't do operations directly on the string. You will go crazy. Here is some code which demonstrates addition and multiplication. Change M to use a bigger type. You could also use std::vector, but then you miss out on some optimizations.

#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <iomanip>

#ifdef _DEBUG
#include <assert.h>
#define ASSERT(x) assert(x)
#else
#define ASSERT(x)
#endif

namespace Arithmetic
{
    const int M = 64;
    const int B = (M-1)*32;

    struct Flags
    {
        Flags() : C(false),Z(false),V(false),N(false){}
        void Clear()
        {
            C = false;
            Z = false;
            V = false;
            N = false;
        }
        bool C,Z,V,N;
    };

    static unsigned int hvAdd(unsigned int a, unsigned int b, Flags& f)
    {
        unsigned int c;
        f.Clear();
        //b = -(signed)b;
        c = a + b;

        f.N = (c >> 31UL) & 0x1;
        f.C = (c < a) && (c < b);
        f.Z = !c;
        f.V = (((signed)a < (signed)b) != f.N);

        return c;
    }

    static unsigned int hvSub(unsigned int a, unsigned int b, Flags& f)
    {
        unsigned int c;
        f.Clear();
        c = a - b;

        //f.N = ((signed)c < 0);
        f.N = (c >> 31UL) & 0x1;
        f.C = (c < a) && (c < b);
        f.Z = !c;
        f.V = (((signed)a < (signed)b) != f.N);

        return c;
    }


    struct HugeVal
    {
        HugeVal()
        {
            std::fill(part, part + M, 0);
        }
        HugeVal(const HugeVal& h)
        {
            std::copy(h.part, h.part + M, part);
        }
        HugeVal(const std::string& str)
        {
            Flags f;
            unsigned int tmp = 0;

            std::fill(part, part + M, 0);

            for(unsigned int i=0; i < str.length(); ++i){
                unsigned int digit = (unsigned int)str[i] - 48UL;
                unsigned int carry_last = 0;
                unsigned int carry_next = 0;
                for(int i=0; i<M; ++i){
                    tmp = part[i]; //the value *before* the carry add
                    part[i] = hvAdd(part[i], carry_last, f);
                    carry_last = 0;
                    if(f.C)
                        ++carry_last;
                    for(int j=1; j<10; ++j){
                        part[i] = hvAdd(part[i], tmp, f);
                        if(f.C)
                            ++carry_last;
                    }
                }
                part[0] = hvAdd(part[0], digit, f);
                int index = 1;
                while(f.C && index < M){
                    part[index] = hvAdd(part[index], 1, f);
                    ++index;
                }
            }
        }
        /*
        HugeVal operator= (const HugeVal& h)
        {
            *this = HugeVal(h);
        }
        */
        HugeVal operator+ (const HugeVal& h) const
        {
            HugeVal tmp;
            Flags f;
            int index = 0;
            unsigned int carry_last = 0;
            for(int j=0; j<M; ++j){
                if(carry_last){
                    tmp.part[j] = hvAdd(tmp.part[j], carry_last, f);
                    carry_last = 0;
                }
                tmp.part[j] = hvAdd(tmp.part[j], part[j], f);
                if(f.C)
                    ++carry_last;
                tmp.part[j] = hvAdd(tmp.part[j], h.part[j], f);
                if(f.C)
                    ++carry_last;
            }
            return tmp;
        }
        HugeVal operator* (const HugeVal& h) const
        {
            HugeVal tmp;

            for(int j=0; j<M; ++j){
                unsigned int carry_next = 0;
                for(int i=0;i<M; ++i){

                    Flags f;

                    unsigned int accum1 = 0;
                    unsigned int accum2 = 0;
                    unsigned int accum3 = 0;
                    unsigned int accum4 = 0;

                    /* Split into 16-bit values */
                    unsigned int j_LO = part[j]&0xFFFF;
                    unsigned int j_HI = part[j]>>16;
                    unsigned int i_LO = h.part[i]&0xFFFF;
                    unsigned int i_HI = h.part[i]>>16;

                    size_t index = i+j;
                    size_t index2 = index+1;

                    /* These multiplications are safe now. Can't overflow */
                    accum1 = j_LO * i_LO;
                    accum2 = j_LO * i_HI;
                    accum3 = j_HI * i_LO;
                    accum4 = j_HI * i_HI;


                    if(carry_next){ //carry from last iteration
                        accum1 = hvAdd(accum1, carry_next, f); //add to LSB
                        carry_next = 0;
                        if(f.C) //LSB produced carry
                            ++carry_next;
                    }

                    /* Add the lower 16-bit parts of accum2 and accum3 to accum1 */
                    accum1 = hvAdd(accum1, (accum2 << 16), f);
                    if(f.C)
                        ++carry_next;
                    accum1 = hvAdd(accum1, (accum3 << 16), f);
                    if(f.C)
                        ++carry_next;



                    if(carry_next){ //carry from LSB
                        accum4 = hvAdd(accum4, carry_next, f); //add to MSB
                        carry_next = 0;
                        ASSERT(f.C == false);
                    }

                    /* Add the higher 16-bit parts of accum2 and accum3 to accum4 */
                    /* Can't overflow */
                    accum4 = hvAdd(accum4, (accum2 >> 16), f);
                    ASSERT(f.C == false);
                    accum4 = hvAdd(accum4, (accum3 >> 16), f);
                    ASSERT(f.C == false);
                    if(index < M){
                        tmp.part[index] = hvAdd(tmp.part[index], accum1, f);
                        if(f.C)
                            ++carry_next;
                    }
                    carry_next += accum4;
                }
            }
            return tmp;
        }
        void Print() const
        {
            for(int i=(M-1); i>=0; --i){

                printf("%.8X", part[i]);
            }
            printf("\n");
        }
        unsigned int part[M];
    };

}


int main(int argc, char* argv[])
{

    std::string a1("273847238974823947823941");
    std::string a2("324230432432895745949");

    Arithmetic::HugeVal a = a1;
    Arithmetic::HugeVal b = a2;

    Arithmetic::HugeVal d = a + b;
    Arithmetic::HugeVal e = a * b;

    a.Print();
    b.Print();
    d.Print();
    e.Print();
    system("pause");
}