bitwise multiplication with an array of ints

[Dman01]

Hi
The following code shows good enough how to multiply two long data

long x = 10, y = 3;
    long p = 0;

    while (y > 0)
    {
        if ((y & 01) != 0) p += x;

        x <<= 1;
        y >>= 1;
    }

    std::cout << "\nResult : " << p;

But I want to make huge integers containing more than 32bit
I use an array of unsigned integers, but somehow this doesnt work

Note that DIGITS are defined as 20

class Unfinitebits
{
    unsigned int m_DATA[DIGITS];

    // ... operator overloading and stuff

};
Unfinitebits& Unfinitebits::operator*=(unsigned int value)
{
#ifndef NO_BITWISE

    Unfinitebits p = 0;

    while (value > 0)
    {
        if ((value & 01) != 0) p += *this;

        *this <<= 1; // same as x above
        value >>= 1; // same as y above
    }

    return p;

#else

    // another method not yet implemented

#endif
}

Unfinitebits& Unfinitebits::operator+=(const Unfinitebits& rhs)
{
    unsigned int* iter = &m_DATA[DIGITS-1];
    const unsigned int* fiter = &rhs.m_DATA[DIGITS-1];

    unsigned int keep;

    for (int i = DIGITS-1;i > -1;i--)
    {
        keep = *fiter;

        unsigned int help = *iter * keep;

        if (help < *iter)
        {
            *iter = ~0; // Byte set of this integer is full
            keep = help;
        }
        else
        {
            *iter *= *fiter;
            break;
        }

        iter--;
        fiter--;
    }

    return *this;
}

Unfinitebits& Unfinitebits::operator<<=(unsigned int value)
{
    if (value == 0)
    return *this;

    unsigned int* iter = m_DATA;

    for (int i = 0;i < DIGITS;i++)
    *iter++ <<= value; // move all bits

    return *this;
}

Unfinitebits& Unfinitebits::operator>>=(unsigned int value)
{
    if (value == 0)
    return *this;

    unsigned int* iter = m_DATA;

    for (int i = 0;i < DIGITS;i++)
    *iter++ >>= value; // move all bits

    return *this;
}

bool Unfinitebits::operator>(unsigned int value)
{
    unsigned int* iter = m_DATA;

    for (int i = 0;i < DIGITS-1;i++)
    {
        if (i < DIGITS-1 && *iter) // if a bit above 32 is set than it has to be greater
        return true;

        iter++;
    }

    return *iter > value; // otherwise compare the last integer with value
}

bool Unfinitebits::operator&(unsigned int value)
{
    unsigned int* iter = m_DATA;

    for (int i = 0;i < DIGITS-2;i++)
    {
        if (!*iter++ & 0) return false; // make sure no byte is set , since value can only concern the last integer
    }

    return m_DATA[DIGITS-1] & value; // compare the last integer
}

Thats what Unfinitebits does, but I don't know why it doesn't work.
I don't want you poeple to do my homework (I do it in my free time though) but to give me hints how I can work with it properly.

I attached the whole project, there is only Unfinitebits implemented.

[mazzica1]

i didnot follow all the code back but i found that the assign is not true when you enter "10" as two digits it is stored in single digit??and if i enterd 10000000 also in single cell?

[Dman01]

I'm using a unsignet int array for storing those values.
I dunno if you mean it, but I just found out, my code doesnt work for multypling.

For example :

Unfinitebits s = 1;

    for (int i = 0; i < 32;i++)
    {
        s *= 2 ;
    }

The code for multypling unsigned ints to my class is simple

Unfinitebits& Unfinitebits::operator*=(unsigned int value)
{
    unsigned int* iter = &m_DATA[DIGITS-1]; // last unsigned int

    for (int i = DIGITS-1;i > -1;i--) // Array contains DIGITS (=20) elements of uint
    {
        unsigned int help = *iter * value;

        if (help < *iter) // help is overflowing, calculation above doesn't fit in help
        {
            printf("\nOverflow : %u * %u = %u", *iter,  value, *iter * value);
            *iter = help; // Byte set of this integer is full
            value = help;
        }
        else // the result will fit in uint 
        {
            *iter*=value;
            value = 0;
        }

        if (value == 0)
        break;

        iter--;
    }

    return *this;
}

The last loop would cause s to overflow, so s is set to zero.

I thought of storing the result in a bigger variable, but this doesn't help either.

unsigned int t = 0x001;
    unsigned long long r = 0;

    for (int i = 0; i < 31;i++)
    {
        t *= 2 ;
    }

    r = t * 2; // This should not overflow , since r is 64bit
    t = r >> 32; // Get the "overflowed" value

    std::cout << "\nResult : " << r << " and " << t; // Neither r is NON zero nor t contains important data : (

Don't get me wrong, I know how to handle binary operations with 32 uints, but when it comes to arrays of uints then I got stuck because I can't handle the overflow

I don't get it : (

EDIT :

To clear things up, the problem is that I don't get how to calculate with an array of ints as a whole bitset.
I can think of splitting the array into a bool array of 20*32 elements containing all bits and then do all calculations.
But then wouldn't this be a low solution and then how can I join an bitset of lets say 8 bool's into a single char ???

[vijayan121]

Karatsuba, perhaps?
http://en.wikipedia.org/wiki/Karatsuba_algorithm
http://mathforum.org/library/drmath/view/71637.html

C: http://ozark.hendrix.edu/~burch/proj/karat/karat.txt (read the copyright notice.)

[raptr_dflo]

OK, I'm going to start from the beginning. Assume I know nothing. I understand that you want to manipulate really big numbers. What values are you storing into your m_DATA array of unsigned ints? Single decimal digits [0-9]? Or arbitrary unsigned 32-bit values? Either way, your assignment to unsigned int help at line 7 (in the first code segment above) is questionable. For instance, if value is bigger than 2G (half the largest value you can store in a 32-bit unsigned val, not that it would be that big, but it -could- be, and it illustrates the problem), then any value of *iter greater than 1 will cause help to overflow.

If you know you're storing "reasonable" values in m_DATA , and passing "reasonable" values for value (and you may want to document this clearly in your code), then you should be OK, but then think about what happens when you multiply two "reasonable" values together, and make sure the result you're storing is also "reasonable", with an appropriate (iterative) carry-operation to move the rest of the result into higher-order positions.

If you're using m_DATA to store consecutive sequences of 32 bits, then you can -never- guarantee that your individual multiplication will work. Instead, note that the product of two 16-bit unsigned values will always fit into a 32-bit unsigned value. Either create your storage array to hold unsigned short int values, and promote each value to 32-bits before applying an operation (which now won't overflow), and then handle the low-order and high-order 16-bits of the result ... or break your 32-bit values into low-order and high-order 16-bit pieces and handle the operations separately. E.g.:

// Adding two 32-bit unsigned values can result in a 33-bit unsigned value.
/*
 * My code is certainly more verbose than strictly necessary, but I've written it
 * this way so that it's completely obvious at each step what size the various
 * values are.  Feel free to consolidate it down to what's needed, provided you
 * don't accidentally break the functionality.
 */
void add (unsigned long int val1, unsigned long int val2,
          unsigned long int &result, unsigned long int &result_carry)
{
    // split inputs into low- and high-order 16-bit chunks
    unsigned short int val1_low  = val1 & 0xffff;
    unsigned short int val1_high = val1 >> 16;
    unsigned short int val2_low  = val2 & 0xffff;
    unsigned short int val2_high = val2 >> 16;

    unsigned long int temp;

    // add low-order chunks (up-cast at least one value to allow overflow)
    temp = (unsigned long int)val1_low + val2_low;
    unsigned short int result_low = temp & 0xffff;
    unsigned short int carry = temp >> 16;  // this will always be either 0 or 1

    // add high-order chunks, plus carry
    temp = (unsigned long int)val1_high + val2_high + carry;
    unsigned short int result_high = temp & 0xffff;
    carry = temp >> 16;

    // build return value
    result = ((unsigned long int)result_high << 16) | result_low;
    result_carry = carry;
}

// multiplying two 32-bit unsigned values can result in a 64-bit unsigned value
void mult (unsigned long int val1, unsigned long int val2,
           unsigned long int &result_low, unsigned long int &result_high)
{
    // val = a*HI + LO (where a = 65536)
    // (val1 * val2) = (a*HI1 + LO1) * (a*HI2 + LO2)
    // from here, derive what multiplications you need to perform, and how to
    //   assemble the resulting products into your result_* variables
}

[Dman01]

@ vijayan121
Thanks I never heard of that.
Thats going to help me, when I get used to this topic, in order to make my class faster.

@raptr_dflo
Hey thanks, that helps a lot.

I'm using the array as it is, no digits, that would be to easy I guess.
All uints in m_DATA together represents a 640bit long bitcode.
(So I guess, I can operate with 2^640 big numbers ? )
My goal is to get the biggest possible value with the smallest usage of memory.

With your help I've done this :

Unfinitebits& Unfinitebits::operator+=(unsigned int value)
{
    int i = 0;

    unsigned long int carry = 0;
    unsigned long int* iter = &m_DATA[DIGITS-1]; // The last element represents the last 32bits of the whole data(20*32 bits)

    do
    {
        add(*iter, (unsigned long int )value, *iter, carry);
        i++;
        iter--; // when carry is filled with the overflow we pass it to the second uint
    }while (carry != 0 && i < DIGITS); // when no overflow occurs (carry = 0) it means value fits in the uint

    printf("\nAdded with %d loops", i);

    return *this;
}

If you're using m_DATA to store consecutive sequences of 32 bits, then you can -never- guarantee that your individual multiplication will work.

This means I can just return a 1280bit(640*2) class, when multiplying with two 640bit classes plus an overflow occurs?

[raptr_dflo]

Your code adds the 32-bit value to each 32-bit word of your instance. I doubt that's what you intended. Instead, if the returned carry is non-zero, you need to add that to the next 32-bit word of your instance, and repeat (in case that carry-addition overflows) until you get a zero-carry back.

This means I can just return a 1280bit(640*2) class, when multiplying with two 640bit classes plus an overflow occurs?

That's one approach. Or, you can make your existing class more generic by including its length and allocating the amount of space you need:

class Unfinitebits
{
private:
    int numBits;
    int numWords;
    unsigned long int *m_data;

public:
    Unfinitebits(int howBig) :
        numBits(0), numWords(0), m_DATA(NULL)
    {
        int words = (howBig + 31 / 32);
        m_DATA = new unsigned long int [ words ];
        if (m_DATA) {
            numBits = howBig;
            numWords = words;
        }
    }

    ...
};

Then you can either have numBits tell you the maximum bit-length of the value you can store, or have it tell your the actual bit-length of the value currently stored (rather than searching for the highest set-bit). Or include a maxBits member so you can have both.

Then if you know the actual bit-length of two 640-bit values, you can immediately determine the bit-length of the product and allocate a new Unfinitebits instance of the correct length.

Keep in mind that if you subtract two values, you may need to recompute numBits from scratch. Or else ensure that any approximation is at least as big as the actual value stored.

[Dman01]

Thanks for your help, I can now use bitwise operations for multiplying.
A last issue is left regarding division, but I think I can get around it by myself.