algorithm for polynomial multiplication

[smsam]

can anyone please suggest me an algorithm to multiple two polynomials in linked lists.

[SlickHawk]

We need more information than that. What do you mean, "in linked lists"? Does each node contain information about a different degree in the polynomial? Are you guaranteed the variable is always the same, or can it be arbitrary?

Let me give you something that might help you, though.

Imagine you want to multiply (2x^3 + 3x + 1) and (4x^4 - 5). In this situation, I see no reason to use linked lists, since I think vectors work much better. I'll assume for simplicity that we need only deal with x's. If it's multiple variables, linked lists might work better. Assume that x^N's coefficient is placed in v[N], where v is our vector. So the vector for the first polynomial would be {1, 3, 0, 2}, and the second would be {-5, 0, 0, 0, 4}.

Anyway, I'll right this in straight C++ to make it easier. I won't compile it, though, so watch for syntax errors.

#include <vector>

typedef std::vector<int> Poly;

Poly MultiplyPolys(const Poly & a, const Poly & b)
{
	//the max degree of the result poly is the sum of the degrees
	//of the inputs (two quadratics always equal a quartic)
	//the degree is equal to the number of elements minus 1, then
	//you add 1 to the result to convert it from the final degree to
	//the final size. -2 + 1 = -1
	//the second parameter initializes all the elements to 0
	Poly ret(a.size() + b.size() - 1, 0);

	for(int i = 0; i < a.size(); ++i)
	{
		for(int j = 0; j < b.size(); ++j)
		{
			ret[i + j] += a[i] * b[j];
		}
	}

	return ret;

}

[Peter_APIIT]

Is this the fast Fourier transform algorithm ?

Thanks.

[Yves M]

No, it's the basic multiplication where you just multiply each term in turn