Hi,
i am writing a program to manipulate polynomials. however, i am having problems with my root function. this function is meant to find the real roots of a polynomial using newton-raphson formula. please help me.

#include<iostream>
#include <sstream>
using namespace std;
//A class to handle a list node
class Lnode{
public:
	Lnode();
	Lnode(int);
int data;
Lnode *next;//This is the pointer to the next node
};

Lnode::Lnode(){
	data = 0;
	next = NULL;
}
Lnode::Lnode(int d){
	data = d;
	next = NULL;
}
//Basic Linked List ADT around the Lnode class
class LList{
public:
	LList();
	LList(int);
	int getSize();
	void set(int, int);
	void print();
	void printP();
	void add(LList);
	void sub(LList);
	void mult(LList);
	double eval(double);
	double pdash(double);
	double pdashdash(double);
	double root(int);

	
	
private:
	void addToF(int);//adding a number to the front of the list. 
	Lnode *head, *tail;//a list has two pointers, head and tail.
	//both are pointing to the already defined List node.
	int size;
};
//Constructor Definition
LList::LList(){
	size = 0;
	head = tail = NULL;//initially, there is nothing. none of them exist.
}
LList::LList(int n){
	head=tail=NULL;
	size = n;
	for(int i=size; i>0; i--)
		addToF(0);
}
int LList::getSize(){
	return size;//to know the size of the list
}
void LList::addToF(int d){
Lnode *nnode = new Lnode(d);//pointer to the list node
	   nnode -> next=head;
		head = nnode;
		if(tail==NULL)
			tail=head;//head and tail are pointing to the same no.
		
}


void LList::print(){
	Lnode *current = head;

	while( current!= NULL)
	{
		cout<<current->data<<"  ";
		current = current->next;
	}

}
void LList::printP(){
	Lnode *current = head;
	int degree = size-1;
	ostringstream buff;
	while( current!= NULL)
	{
		buff<<current->data<<"x^"<<degree<<" "<<"+";
		current = current->next;
		degree--;
	}
	std::string output = buff.str();
	output[output.length()-1]='\0';
	cout<<output;

}


void LList::set(int c, int val)
{
	
	int i = size-1;
	Lnode *current=head;
	while(current != NULL)
	{
		if(i==(c))
		{
			current->data = val;
			break;
		}
		else
		{
			current = current->next;
			i--;
		}
	}
}

void LList::add(LList L){
	Lnode *ptr1;
	Lnode *ptr2;
	ptr1 = head;
	ptr2 = L.head;
	while(ptr1 != NULL && ptr2 != NULL)
	{
	ptr1->data = ptr1->data+ptr2->data;
	ptr1 = ptr1->next;
	ptr2 = ptr2->next;
	}
	
}
void LList::sub(LList L){
	Lnode *ptr1;
	Lnode *ptr2;
	ptr1 = head;
	ptr2 = L.head;
	while(ptr1 != NULL && ptr2 != NULL)
	{
	ptr1->data = ptr1->data-ptr2->data;
	ptr1 = ptr1->next;
	ptr2 = ptr2->next;
	}
}
void LList::mult(LList L){
	Lnode *ptr1;
	Lnode *ptr2;
	ptr1 = head;
	ptr2 = L.head;
	while(ptr1 != NULL && ptr2 != NULL)
	{
	ptr1->data = ptr1->data*ptr2->data;
	ptr1 = ptr1->next;
	ptr2 = ptr2->next;
	}
	

}

double LList::eval(double x){
	double sum = 0;
	Lnode *temp = head;
	for(int i=size-1; i>=0; i--)
	{
		sum = sum*x + temp->data;
		temp = temp->next;
	}
	return sum;
	
}
double LList::pdash(double x){
	const double h=1.0e-3;
	return (eval(x+h)- eval(x-h))/(2*h);
	
}
double LList::pdashdash(double x){
	const double h=1.0e-3;
	return (eval(x+h)-(2*eval(x)) + eval(x-h))/(h*h);
}

double LList::root(int x){
return(x - (eval(x)/(pdash(x))));
}
	


//Driver Main Program
int main(){

	LList a(3);
	a.set(2, 1);
	a.set(1, -7);
	a.set(0, -120);
	cout<<"First Polynomial is:"<<" ";
	a.printP();
	cout<<endl;
	cout<<endl;
	cout<<"Evaluation of First Polynomial is:"<<" ";
	cout<<a.eval(2.0)<<endl;
	cout<<endl;
	cout<<"Derivative of First Polynomial is:"<<" ";
	cout<<a.pdash(2.0)<<endl;
	cout<<endl;
	cout<<"Second Derivative of First Polynomial is:"<<" ";
	cout<<a.pdashdash(2.0)<<endl;
	cout<<endl;
	cout<<a.root(-1)<<endl;
	cout<<a.root(10)<<endl;
	

		
}

thanks in advance

Your pdash function makes NO sense.

a.set(2, 1);
a.set(1, -7);
a.set(0, -120);

[tex] x^2 -7x -120[/tex]

You need to find the actual derivative of this

Which is:

[tex]
2x - 7
[/tex]

Where is this in your code?

and why do you need to find the second derivative?

hi,
thanks for replying. the second derivative is a different function on its own. it has nothing to do with the roots or anything. the first derivative is found using the original derivative formula that is
(f(x+h) - f(x-h)) /(2h). it is finding the derivative of the polynomial and evaluating it.
that's why. do u have a better option.

Your pdash function makes NO sense.

a.set(2, 1);
a.set(1, -7);
a.set(0, -120);

[tex] x^2 -7x -120[/tex]

You need to find the actual derivative of this

Which is:

[tex]
2x - 7
[/tex]

Where is this in your code?

and why do you need to find the second derivative?

>(f(x+h) - f(x-h)) /(2h)

Hmm, if your function doesn't contain any trig terms would it not just be easier to find the exact derivative and then plug it in to the n/r formula...hence:


[tex] x_{n+1} = x_n - \frac{x^2-7x-120}{2x-7}[/tex]

i think i understand ur point but i do not know how to do this. any help??

>(f(x+h) - f(x-h)) /(2h)

Hmm, if your function doesn't contain any trig terms would it not just be easier to find the exact derivative and then plug it in to the n/r formula...hence:


[tex] x_{n+1} = x_n - \frac{x^2-7x-120}{2x-7}[/tex]

To find the derivative of a simple function, for each term, multiply the coeff by the power, then decrease the power by one:


for e.g

2x^2

becomes 2 * 2 x ^ (2-1) = 4x

7x^3

becomes 3 * 7 x ^ ( 3 - 1 ) = 21x ^ 2

etc.

A more generic algo would be to loop through your terms (assuming each coef of corresponding power is stored in an array):-

for (int i = 0; i < highestPower; i++)
            derivCoef[i] = (i + 1) * coef[i + 1];
This article has been dead for over six months. Start a new discussion instead.