Programming Forums > Application Development > C++

Ooble · Apr 14th, 2008, 12:56 AM

Oh, c'mon, you wouldn't be doing it if you didn't enjoy it. :p

Sane · Apr 14th, 2008, 5:55 AM

You should only need three arrays.

Let the polynomials to be multiplied together be array A (of degree n) and array B (of degree m). The product of A x B will be array C (of degree n+m). Represent the polynomial such that the index of each coefficient represents the degree at that coefficient.

For example, {5, 1, 0, 3, 7} represents 7x^4 + 3x^3 + 1x + 5.

Note that the array's size is always one plus the degree of the polynomial.

Then the code should very clearly write itself:

Psuedocode Syntax (Toggle Plain Text)

for k : 0 .. n + m + 1
    C[k] = 0
 
for i : 0 .. n + 1
    for j : 0 .. m + 1
        C[i+j] += A[i] * B[j]

Then if you need to multiply more than two polynomials, keep repeating this process, shifting C to A each iteration.

I think that's by far the easiest way. Is this what your friend suggested?

mbd · Apr 14th, 2008, 2:16 PM

there is an stl function in the numeric header to multiply ranges (vectors) called inner_product

ShawnStovall · Apr 14th, 2008, 3:32 PM

Quote:

Originally Posted by Sane

You should only need three arrays.

Let the polynomials to be multiplied together be array A (of degree n) and array B (of degree m). The product of A x B will be array C (of degree n+m). Represent the polynomial such that the index of each coefficient represents the degree at that coefficient.

For example, {5, 1, 0, 3, 7} represents 7x^4 + 3x^3 + 1x + 5.

Note that the array's size is always one plus the degree of the polynomial.

Then the code should very clearly write itself:

Psuedocode Syntax (Toggle Plain Text)

for k : 0 .. n + m + 1
    C[k] = 0
 
for i : 0 .. n + 1
    for j : 0 .. m + 1
        C[i+j] += A[i] * B[j]

Then if you need to multiply more than two polynomials, keep repeating this process, shifting C to A each iteration.

I think that's by far the easiest way. Is this what your friend suggested?

Thanks, what happened is that I was looking for more programming ideas and I asked my friend who was doing his homework at the time, so he mentioned this. I asked him how to do it and he told me a COMPLETELY and UTERLY wrong way to do the math. Things didn't look right so after figuring out what I should do to solve the problem the wrong way I decided to look in my math book to see what was going on. And now I have to completely redesign my program. lol

Shows you what I get for listening to a kid who asks ME for help in math. =P

@ Ooble: You're right, I love programming!

misho · Apr 17th, 2008, 2:56 PM

What ShawnStovall said is probably the best way to go.

The only thing I would add is that if you're only multiplying binomials, you can make your life a little easier: make your program multiply an n-th polynomial by a binomial.
Then, say you want to do:
$(x+2)(2x+3)(3x+4)(4x+5)$
This is equivalent to:
$\{[(x+2)(2x+3)](3x+4)\}(4x+5)$
Notice that now, at every step, you're just multiplying a polynomial by a binomial, so if you were to call a function that multiplies a polynomial by a binomial a bunch of times, you would do what's needed.
As for what the function should do (here's some math, which I hope makes sense to you):
Any polynomial can be of written as:
$P_n(x) = \sum_{i=0}^{n}a_i x^i$
Any binomial as (at least based on your initial code):
$Q_1(x) = Ax+B$
Then:
$ P_i(x) \times Q_1(x) = \sum_{i=0}^{n}a_i x^i \times (Ax+B) \\ P_i(x) \times Q_1(x) = \sum_{i=0}^{n} A a_i x^{i+1} + \sum_{i=0}^{n} B a_i x^i \\ P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=0}^{n-1} A a_i x^{i+1} + \sum_{i=1}^{n} B a_i x^i + Ba_0 \\ P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=1}^{n} A a_{i-1} x^{i} + \sum_{i=1}^{n} B a_i x^i + Ba_0 \\ P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=1}^{n} ( A a_{i-1} + Ba_i ) x^{i} + Ba_0 $

Assuming the math hasn't scared you too much, the code should be fairly easy to write. As Shawn said, the best way to go is have the vector index represent the power of the term ( 2 + 3x + 4x^2 + 5x^3 is stored as { 2, 3, 4, 5 } ).
I'm going to add a binomial struct:

 c++ Syntax (Toggle Plain Text) 
struct binomial //def: (Ax+B)
{
	double A;
	double B;
};
struct binomial //def: (Ax+B)
{
	double A;
	double B;
};

Then, the function is (this is just straight from the last line of math above):

 c++ Syntax (Toggle Plain Text) 
vector<double> multiply(vector<double> poly, binomial bi)
{
	int n = poly.size() - 1;
	vector<double> result (n + 2);
	result[0] = bi.B*poly[0];
	result[n + 1] = bi.A*poly[n];
	for(int i = 1; i <= n; i++) result[i] = bi.A*poly[i-1] + bi.B*poly[i];
	return result;
}
vector<double> multiply(vector<double> poly, binomial bi)
{
	int n = poly.size() - 1;
	vector<double> result (n + 2);
	result[0] = bi.B*poly[0];
	result[n + 1] = bi.A*poly[n];
	for(int i = 1; i <= n; i++) result[i] = bi.A*poly[i-1] + bi.B*poly[i];
	return result;
}

The rest should be fairly obvious, I imagine. Just run that function a lot of times, and initialize your first polynomial to the first binomial you want to add. Note that this is pretty bad in terms of memory usage, but you can play with it to make it better (you know, if you ever feel like multiplying a few million binomials or something, it's good to know your code can handle it).

ShawnStovall · Apr 19th, 2008, 8:47 PM

Thanks! I've been busy the past few days and have not had the chance to work on it again, this should really help.

Apr 14th, 2008, 12:56 AM	#11
Ooble I eat cake for breakfast. Join Date: Jul 2004 Location: In my box. Posts: 4,434 Rep Power: 9	Re: Multi-dimensional vectors Oh, c'mon, you wouldn't be doing it if you didn't enjoy it. :p __________________ Me :: You :: Them

Apr 14th, 2008, 5:55 AM	#12
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,886 Rep Power: 5	Re: Multi-dimensional vectors You should only need three arrays. Let the polynomials to be multiplied together be array A (of degree n) and array B (of degree m). The product of A x B will be array C (of degree n+m). Represent the polynomial such that the index of each coefficient represents the degree at that coefficient. For example, `{5, 1, 0, 3, 7}` represents `7x^4 + 3x^3 + 1x + 5`. Note that the array's size is always one plus the degree of the polynomial. Then the code should very clearly write itself: Psuedocode Syntax (Toggle Plain Text) for k : 0 .. n + m + 1 C[k] = 0 for i : 0 .. n + 1 for j : 0 .. m + 1 C[i+j] += A[i] * B[j] for k : 0 .. n + m + 1 C[k] = 0 for i : 0 .. n + 1 for j : 0 .. m + 1 C[i+j] += A[i] * B[j] Then if you need to multiply more than two polynomials, keep repeating this process, shifting C to A each iteration. I think that's by far the easiest way. Is this what your friend suggested? __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data Last edited by Sane; Apr 14th, 2008 at 6:07 AM.

Apr 14th, 2008, 2:16 PM	#13
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	Re: Multi-dimensional vectors there is an stl function in the numeric header to multiply ranges (vectors) called inner_product

Apr 17th, 2008, 2:56 PM	#15
misho Newbie Join Date: Apr 2008 Posts: 10 Rep Power: 0	Re: Multi-dimensional vectors What ShawnStovall said is probably the best way to go. The only thing I would add is that if you're only multiplying binomials, you can make your life a little easier: make your program multiply an n-th polynomial by a binomial. Then, say you want to do: $(x+2)(2x+3)(3x+4)(4x+5)$ This is equivalent to: $\{[(x+2)(2x+3)](3x+4)\}(4x+5)$ Notice that now, at every step, you're just multiplying a polynomial by a binomial, so if you were to call a function that multiplies a polynomial by a binomial a bunch of times, you would do what's needed. As for what the function should do (here's some math, which I hope makes sense to you): Any polynomial can be of written as: $P_n(x) = \sum_{i=0}^{n}a_i x^i$ Any binomial as (at least based on your initial code): $Q_1(x) = Ax+B$ Then: $<br /> P_i(x) \times Q_1(x) = \sum_{i=0}^{n}a_i x^i \times (Ax+B) \\<br /> P_i(x) \times Q_1(x) = \sum_{i=0}^{n} A a_i x^{i+1} + \sum_{i=0}^{n} B a_i x^i \\<br /> P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=0}^{n-1} A a_i x^{i+1} + \sum_{i=1}^{n} B a_i x^i + Ba_0 \\<br /> P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=1}^{n} A a_{i-1} x^{i} + \sum_{i=1}^{n} B a_i x^i + Ba_0 \\<br /> P_i(x) \times Q_1(x) = A a_n x^{n+1} + \sum_{i=1}^{n} ( A a_{i-1} + Ba_i ) x^{i} + Ba_0 <br />$ Assuming the math hasn't scared you too much, the code should be fairly easy to write. As Shawn said, the best way to go is have the vector index represent the power of the term ( 2 + 3x + 4x^2 + 5x^3 is stored as { 2, 3, 4, 5 } ). I'm going to add a binomial struct: c++ Syntax (Toggle Plain Text) struct binomial //def: (Ax+B) { double A; double B; }; struct binomial //def: (Ax+B) { double A; double B; }; Then, the function is (this is just straight from the last line of math above): c++ Syntax (Toggle Plain Text) vector<double> multiply(vector<double> poly, binomial bi) { int n = poly.size() - 1; vector<double> result (n + 2); result[0] = bi.Bpoly[0]; result[n + 1] = bi.Apoly[n]; for(int i = 1; i <= n; i++) result[i] = bi.Apoly[i-1] + bi.Bpoly[i]; return result; } vector<double> multiply(vector<double> poly, binomial bi) { int n = poly.size() - 1; vector<double> result (n + 2); result[0] = bi.Bpoly[0]; result[n + 1] = bi.Apoly[n]; for(int i = 1; i <= n; i++) result[i] = bi.Apoly[i-1] + bi.Bpoly[i]; return result; } The rest should be fairly obvious, I imagine. Just run that function a lot of times, and initialize your first polynomial to the first binomial you want to add. Note that this is pretty bad in terms of memory usage, but you can play with it to make it better (you know, if you ever feel like multiplying a few million binomials or something, it's good to know your code can handle it).

Apr 19th, 2008, 8:47 PM	#16
ShawnStovall Call me Chuck Join Date: Aug 2007 Location: USA, MI Posts: 37 Rep Power: 0	Re: Multi-dimensional vectors Thanks! I've been busy the past few days and have not had the chance to work on it again, this should really help. __________________ sqrt(-1) <3 3.14 98% of the teenage population will try, does or has tried smoking pot. If you're one of the 2% who hasn't, copy & paste this into your signature

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
reading from file, and vectors question	jasonfrost	C++	3	Oct 3rd, 2007 9:02 AM
How do I read .mbm (Multi BitMap) files?	moondog	Other Programming Languages	19	Aug 16th, 2007 8:59 PM
multi dimensional array error	veiga2	C++	2	Nov 16th, 2006 3:05 AM
Arrays or Vectors?	can342man	C++	2	Apr 20th, 2006 3:57 PM
Passing vectors as arguments	Soulstorm	C++	6	Mar 18th, 2006 4:49 PM

Programming Forums > Application Development > C++

Multi-dimensional vectors