Using Vectors for Manual Multiplication

[bickelz]

Ok, so I'm trying to solve Project Euler 16 where you have to calculate 2^1000. SO I made a program that would solve multiplying a number b a single digit factor through manual multiplication in a vector, just to test things out.

The problem is when I take things out of main and try to make a separate function, the original number is never multiplied.

I'm passing by reference but I'm stumped at this point, to be honest.

Here's my code with functions...

/*Using vectors manually to multiply a number to a positive power.*/

#include <iostream>
#include <vector>
using namespace std;

void print_vector(const vector<int>& v);
void multiply(vector<int>& v, const int mult);


int main() {
	vector<int> numbers;
	numbers.push_back(2);
	 
	multiply(numbers, 6);   //6 is arbitrary
	
	print_vector(numbers);

	return 0;
}


void multiply(vector<int>& v, const int mult) {
	vector<int>::iterator iter;
	
	int product, left_spaces;
	
	for (iter = v.end(); iter != v.begin(); iter--) {
		product = *iter * mult;
		
		
		if (product > 9) {
			
			while (true) {
				*iter = product % 10;	//put ones digit into current iterator location
				
				if (iter != v.begin()) {	//if we're not at the beginning of the number
					iter = iter - 1;		//move iterator one location to the left
					left_spaces += 1;		//keep track of how many spaces we move left
					product = (*iter * mult) + ((product - (product % 10)) / 10); //add current iterator value and 10th place digit of product
					
					if (product <= 9) {	//if the new product is less than or equal to 9, put product into current iter and break out of loop
						*iter = product;
						break;
					}
					else			//if product is > 9, go through the loop again
						continue;
				}
				
				else {		//if iter = v.begin and the product is >9 then we need to push_front the tens digit of the product
					v.insert(v.begin(), ( (product - (product % 10) ) / 10) );
					break;
				}
			}
		}
		
		
		
		else {
			*iter = product;
		}
		
		iter = iter + left_spaces;		//return iterator to where it was before
		left_spaces = 0;				//zero out left spaces
	}
	
}

void print_vector(const vector<int>& v) {
	vector<int>::const_iterator citer;
	
	for (citer = v.begin(); citer != v.end(); citer++) {
		cout << *citer;
	}
	
	cout << endl;
}

Here is the other code, not using functions but even if I use an extra for loop to multiply by the same factor several times, it still does the same thing.

/*Using vectors manually to multiply a number by two (or any single digit factor).*/

#include <iostream>
#include <vector>
using namespace std;

void print_vector(const vector<int>& v);

int main() {
	vector<int> v;
	vector<int>::iterator iter;
	
	int product, left_spaces;
	const int mult = 6;   //multiply number by 6
	
	//initialize vector to 361 using one space for each number in the int
	v.push_back(3);
	v.push_back(6);
	v.push_back(1);
	
	for (iter = v.end(); iter != v.begin(); iter--) {
		product = *iter * mult;
		
		
		if (product > 9) {
			
			while (true) {
				*iter = product % 10;	//put ones digit into current iterator location
				
				if (iter != v.begin()) {	//if we're not at the beginning of the number
					iter = iter - 1;		//move iterator one location to the left
					left_spaces += 1;		//keep track of how many spaces we move left
					product = (*iter * mult) + ((product - (product % 10)) / 10); //add current iterator value and 10th place digit of product
					
					if (product <= 9) {	//if the new product is less than or equal to 9, put product into current iter and break out of loop
						*iter = product;
						break;
					}
					else			//if product is > 9, go through the loop again
						continue;
				}
				
				else {		//if iter = v.begin and the product is >9 then we need to push_front the tens digit of the product
					v.insert(v.begin(), ( (product - (product % 10) ) / 10) );
					break;
				}
			}
		}
		
		
		
		else {
			*iter = product;
		}

		iter = iter + left_spaces;		//return iterator to where it was before
		left_spaces = 0;				//zero out left spaces
	}
	
	print_vector(v);
	
	return 0;
}

void print_vector(const vector<int>& v) {
	vector<int>::const_iterator citer;
	
	for (citer = v.begin(); citer != v.end(); citer++) {
		cout << *citer;
	}
	
	cout << endl;
}

[D80DSL3A]

I think you want a reverse::iterator in your multiply function.
The logic in multiply seems unnecessarily complicated. I don't understand the left_spaces variable.

You can just roll straight through, forming a product and carrying as you go.

I gave it a try myself. Perhaps my code will be useful for comparison.

#include <iostream>
#include<vector>

using namespace std;

void print_vector(const vector<int>& v) {
	vector<int>::const_iterator citer;

	for (citer = v.begin(); citer != v.end(); citer++) {
		cout << *citer;
	}

	cout << endl;
}

void multiply(vector<int>& v, const int mult)
{
    int product=0, carry=0;
    vector<int>::reverse_iterator rit = v.rbegin();
    while( rit != v.rend() )
    {
        product = (*rit)*mult + carry;
        carry = product/10;
        *rit = product%10;
        ++rit;
    }

    if( carry > 0 )// push_front the carry
    {
        v.insert( v.begin(), carry );
    }
}

int main()
{
    vector<int> numbers;
	numbers.push_back(2);

    // buildup 2^1000 in numbers
    for( int i=0; i< 999; ++i)
        multiply(numbers, 2);

    // problem 16 is to find the sum of the digits of 2^1000
    int digitSum = 0;
    vector<int>::const_iterator citer;
	for (citer = numbers.begin(); citer != numbers.end(); citer++)
		digitSum += *citer;

    cout << "sum = " << digitSum << endl;

   return 0;
}

Output:

sum = correct answer for problem 16

EDIT: A std::list would be better for this due to the expensive insert operations. std::list allows push_back for initializing as big-endian, and push_front for the carries.

[cire]

EDIT: A std::list would be better for this due to the expensive insert operations. std::list allows push_back for initializing as big-endian, and push_front for the carries.

Always using position 0 as the 1's digit would be a more efficient solution. I don't see how endianness is relevant.

[ne555]

> A std::list would be better for this due to the expensive insert operations.
> std::list allows push_back for initializing as big-endian, and push_front for the carries.
No. If you pretend to do `push_front()' in a vector consider reversing the logic and do a `push_back()' instead.
Besides, you can have a good guess on the final size, so you wouldn't need reallocation.

[bickelz]

Well, you got the right answer so I'll mark this as solved. Reverse iterators make things a little easier.

>The logic in multiply seems unnecessarily complicated. I don't understand the left_spaces variable.

What I was trying to accomplish was that when you add the carry over to the next space, that number might exceed 9 and you'll need to keep carrying over but you would have to reset the iterator to its position in the for loop.

So instead of putting the carry at the front of the vector, I was trying to do the addition for each place in the vector.

Anyways, much obliged!

[D80DSL3A]

You're welcome.

Reverse iterators make things a little easier.

I think you could use the forward iterator but then you must start at v.end()-1.
v.end() is invalid, so your for loop line 28 may not work.
You would also want to include v.begin(), which your for loop would stop at.

I think the only way you will get a carry > 8 (9*9 = 81 is max 1-digit case) is if mult >=10 (ie greater than the base you are representing in).

In this case, I think the result will still be OK except for the last carry.
I tried modifying multiply to allow for a multi-digit final carry, changing:

if( carry > 0 )// push_front the carry
    {
        v.insert( v.begin(), carry );
    }

to:

while( carry > 0 )// push_front the carry
    {
        v.insert( v.begin(), carry%10 );
        carry /= 10;
    }

I tested this against finding 2^1000 = (32)^200 with:

vector<int> numbers;
	numbers.push_back(1);

    for( int i=1; i<= 200; ++i)
        multiply(numbers, 32);

I still get the correct answer.

EDIT: max carry=9, not 8 for 1-digit case. I forgot that carry would be summed so max case is 9*9 + 9 = 90

Testing theory re. use of forward iterator in multiply:

void multiply2(vector<int>& v, const int mult)
{
    vector<int>::iterator it = v.end()-1;
    int product= (*it)*mult;// 1st term explicitly
    int carry = product/10;
    *it = product%10;

    while( it != v.begin() )
    {
        --it;// so v.begin will be included
        product = (*it)*mult + carry;
        carry = product/10;
        *it = product%10;

    }

    while( carry > 0 )// push_front the carry
    {
        v.insert( v.begin(), carry%10 );
        carry /= 10;
    }
}

This works too.

@ne555 and cire. I would store the digits in the opposite order too and use push_back for the carries, but bickels had it setup as low digit last. I was just trying to make it work that way.