How to Multiply two HUGE Binary Numbers

[shamieh]

I'm really confused on how to multiply huge binary numbers.. So I'm storing both of my binary numbers as vectors<int> . Per the assignment we can not use any kind of bigInteger datatype or any kind of datatype that could convert this huge binary number to decimal so I'm screwed there. I can't convert it to decimal then do the multiplication then throw it back into binary because no data type will hold this huge binary number. So then I tried the basic approach and I noticed that every time i have more digits I have to shift over.. but I feel like I would have to create x amount of vectors to store each multiplication for example if I had 1011 * 0111 I would have to have vector_1 to hold 1011 * 1, then I would have to have another vector : vector_2 to hold 1 * 1011 but shifted to the left one by a 0, then I would have to have another vector_3: to hold the next 1 shifted over two zeros of course - and finally another vector full of all zeros (if i really wanted to put them in a vector). Then I would need to add all of these vectors up. The Problem is I cant just create vectors on the fly as I need them so i'm extremely confused on how to solve this problem.

[helios]

The Problem is I cant just create vectors on the fly as I need them

Why not?

Strictly speaking, you only need one extra vector for intermediate results.
a = 1011
b = 1101
c = 0

d = 1011 * 1
c += d (1011)

d = 1011 * 0
c += d (1011)

d = 1011 * 100
c += d (1011 + 101100 = 110111)

d = 1011 * 1000
c += d (110111 + 1011000 = 10001111)

c == a * b

[dhayden]

Just do it the same way you would do it by hand. Multiply the m'th and n'th digits, adding the value to the (m+n)'th digit of the result (assuming that the least significant digit is numbered 0). When you're done, some digits of the result will be larger than 1. Go through the result from least significant digit to most, carrying the values to the next higher digit as needed.

[Duthomhas]

You need to think about how to multiply stuff by hand. For example:

      234
    x  79
    ?????

This breaks down into two smaller problems:

      234           234
    x   9         x  70
     ????    +    ????0

You need a function that multiplies a big number by a single 'big digit' (an int) and adds the result into a target big number.

Then you can use it to multiply two big numbers:

typedef vector<int> big_number;

void big_multiply_by_int_and_add( 
  const big_number& a,  // source
  int b,                // source
  big_number& d,       // destination
  int offset_into_d )       // offset into destination
{
  // PSEUDOCODE!
  d += (a * b) shifted 'offset_into_d' big digits into d;
}

Once you have that, you can write a function that multiplies any two big numbers:

big_number big_multiply( const big_number& a, const big_number& b )
{
  big_number d = 0;
  int offset_into_d = 0;
  for each digit in b (starting with the least-significant big digit)
  {
    big_multiply_by_int_and_add( a, digit_from_b, d, offset_into_d++ );
  }
  return d;
}

The tricky part is in the first function, making sure to multiply and handle carries correctly: an int * int --> long long int!

For example:

long long int mult_int( int a, int b )
{
  return (unsigned long long int)a * (long long int)b;
}

That gives you two 'digits' worth of information:

long long int x = mult_int( a, b );
int xhigh = x >> (sizeof int * 8);
int xlow = (unsigned long long int)x & (unsigned int)(-1);

Remember, for normal (power of ten) digits:

    3*9=27    →    high=2, low=7 

It works the same way for big digits. (The only difference is that there are UINT_MAX symbols per 'big digit' instead of the ten symbols for our normal digits.)



Before I go, a couple of other things to observe:

(1)
You should be using an unsigned int for your big digits:

typedef vector<unsigned int> big_number;

This saves you a whole lot of grief. You should adjust the examples above so that everything is unsigned.

For negative numbers, you only need an extra value somewhere to indicate that it is negative.

I personally find it useful to make a separate class:

struct big_number
{
  vector <unsigned> digits;
  bool is_signed;
  ...
};

But you can easily just have an extra digit in there somewhere that is 0 or 1 for positive and negative. The trick is to remember that it is not part of the number proper and exclude it from the multiplication and addition routines except to note the signedness of the numbers.

(2)
The order in which you store digits is also important. I personally prefer to store least-significant digits first in the vector; I find it makes indexing stuff a whole lot more natural.

    1234

gets stored as:

    { 4, 3, 2, 1 }

Ultimately, however, it is up to you how you wish to store it -- just as long as you are consistent.


Hope this helps.

[shamieh]

I'm trying to implement this pseudo code:

Psuedo Code

multiply(x,y)
z = 0
for i = size(y) - 1 down to 0
  z = 2z
  if y[i] = 1: z = z + x
return z

The pseudo code is extremely vague.. Here is what I have so far. I'm getting the wrong number though. I got 0000010100 when i should of got 100001 For my inputs I had x = {1,0,1,1} and let y = {0,0,1,1}

vector<int> multiplyBinaryNumbers(vector<int> x, vector<int> y)
{
	//Product Vector?
	vector<int> z = { 0,0,0,0 };

	for (int i = y.size() - 1; i >= 0; i--)
	{
		//Why? Assume We have 1011 * 0011. Where x is 1011 and y is 0011
		//Then I'm saying ok 2 * 0 = 0... push that back into my z vector
		//Uhh?Am I doing this right
		z.push_back(2 * z[i]);

		//If y is odd
		if (y[i] % 2 != 0)
		{
			//Is this what they want?
			z.push_back(z[i] + x[i]);
		}
	}
	//Return product
	return z;
}

[Duthomhas]

The pseudocode is actually spot-on. The hard stuff is actually in the addition: z = z + x.

To multiply a binary value by two, stick a zero on the end:

    1→10 (1→2)
    101→1010 (5→10)
    etc.

Each time through the loop, you are asked to multiply z by 2: z = 2z.
Now you know how to fix line 11.


Line 13: y[i] should only be one of 0 or 1; testing for oddness is overkill. (Just check to see if it is nonzero.)


Line 17: No, what they want is for you to add x to z. I would write another function to help with that, like:

void add_to( vector<int>& r, const vector<int>& x )  // r = r + x
{
  // for each element in x, add it to the corresponding element in r; don't forget to carry!
  // example:
  //   1001
  //  + 101
  //  -----
  //   1110
}

Use it thus:

		{
			add_to(z, x);
		}

Line 4: There is an important caveat to the code: All numbers except zero must begin with a 1.

If you don't enforce this constraint, your user will try to multiply something like 1010 and 0011 and get an incorrect answer. The multiplicands must be 1010 and 11.

You can initialize z (line 4) either to a single zero (and make sure to add digits when necessary in add_to()),
or you can initialize it to x.size()+y.size() zeros -- as this will be large enough to hold the product of x and y.


Remember, the hardest part of your assignment is actually in the addition. You'll have to think carefully about that.

Good luck!