Finding the root of a polynomial

This is a discussion on Finding the root of a polynomial within the C Programming forums, part of the General Programming Boards category; I can find the root of a polinomial in a segment [A,B]. I can find it if root == A, ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    74

    Finding the root of a polynomial

    I can find the root of a polinomial in a segment [A,B]. I can find it if root == A, root == B or if root is between A and B. And all of this using 2 methods not one.

    But for the life of me I cannot determine if the root is not in the segment. For example, let's say that the polynomial is a simple one
    Code:
    x-5=0
    The root is obviously 5. But if A and B are both bigger (A=10, B=14) or both smaller (A=-1, B=4) than the root (5 here), then I am stuck!!

    EDIT: EUREKA!!! I figured it out. If both A and B are of the same sign (both positive or negative) than the root simply isn't in the segment [A,B].

    EDIT 2: IDIOT!!! why shouldn't A and B be both positive, A= 3, B=10. A and B don't matter. There values once inputed in the polynomial matter.

    so if we transform
    Code:
    x-5=0
    into
    Code:
    f(x) = x-5
    then f(A) and f(B) must be of the same sign.
    Last edited by budala; 08-05-2009 at 10:42 AM.

  2. #2
    Registered User
    Join Date
    Jun 2009
    Posts
    452
    Could you post your code?

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    so you are given a string like this one
    "x-5=0"

    and you want to solve it?
    i couldnt understand in details what is your goal?

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    74
    Ok, this is my code. I half the segment if the root is in it until the segment length reaches an error tolerance.

    Code:
    #include <stdio.h>
    #include <math.h>
    
    float f(float x)
    {
    	return (x-5);
    }
    
    void Halfing ()
    {
    	float a,b,s,e;
    	int n = 0;
    	int test = 0;
    	
    	do
    	{
    		printf("Enter the beginning of the segment -> ");
    		scanf("%f",&a);
    		printf("Enter the end of the segment -> ");
    		scanf("%f",&b);
    		if ((f(a) > 0 && f(b) > 0) || (f(a) < 0 && f(b) < 0))
    		{
    			printf("The root is not inside the segment [%4.2f,%4.2f]",a,b);
    			printf("\nChoose other endpoints\n");
    		}
    		else test = 1;
    	} while  (test != 1);
    	
    	printf("Enter error tolerance -> ");
    	scanf("%f",&e);
    	
    	if (f(a) == 0) printf("The root is at an endpoint and it is %6.4f\n",a);
    	else if (f(b) == 0) printf("The root is at an endpoint and it is %6.4f\n",b); 
    	else	
    	{
    		do 
    		{
    			n++;
    			s = (a+b)/2;
    			printf("%d. pass x = %6.4f\n",n,s);
    			if (f(a)*f(s)<0)   b = s;
    			else  a = s;
    		} while (fabsf(a-b)>e);	
    		
    		printf("\nRoot = %6.4f", (a+b)/2);
    	}
    }
    
    
    int main (int argc, const char * argv[]) 
    {
    	Halfing ()
    
    	return 0;
    }

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    You probably can't just look at the values of the endpoints. Consider

    f(x) = x^2 - 3,

    with A = -2 and B = 2.

    Then f(A) = 1 and f(B) = 1. However, even though they have the same sign, there are two roots in the domain, sqrt(3) and -sqrt(3). If you are limited to just linear functions, your algorithm is fine, but I don't think there's any foolproof way for a general polynomial (although there is a way for 2nd order, and maybe some higher orders). You can make it better by checking many points for sign changes, though, instead of just two.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed! Finding Root of an Equation?
    By reader in forum C Programming
    Replies: 4
    Last Post: 06-13-2008, 11:10 AM
  2. Pointer confusion
    By Blackroot in forum C++ Programming
    Replies: 11
    Last Post: 09-12-2007, 01:44 AM
  3. Bisection Method function value at root incorrect
    By mr_glass in forum C Programming
    Replies: 3
    Last Post: 11-10-2005, 09:10 AM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  5. Templated Binary Tree... dear god...
    By Nakeerb in forum C++ Programming
    Replies: 15
    Last Post: 01-17-2003, 02:24 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21