Root Finder for polynomials

[gibsonrocker800]

Hey guys, i've been working on a program that finds the roots of a complex function in Pre-Calculus (x^3 + 2x^2 - 4x + 1 or something like that), and i'm not doing this to help me with my math, i just enjoy making programs that are useful in math and physics. Now, i've already made a class that does Synthetic Division for you, after putting in the root and all of the coefficients of the original function, and it returns the resulting function, and tells you whether or not the root you tested is a root of the function. This class works great, as seen through my tester class where the user enters the coefficients and the root they want to test.
So here's the problem. This isn't as efficient as i would like it to be. i want to make it so that the user doesn't have to enter in the possible root, it automatically finds the possible roots (when you do constant coefficient over leading coefficient, and you take the factors). So with all of this said, my problem is that i'm trying to figure out a way to get all of the possible roots.

MY IDEA FOR THIS: divide the number (leading and constant) by all of the numbers less than that number.

I hope this isn't too wordy or confusing, so let me give you an example.

x^3 + 3x^2 + 2x + 2

Finding the possible roots:

2/1 ( 1 , 2 )/ 1

So, the possible roots are -1, -2, 1, 2. (because you take the positive and the negative of each division).

So like i said, my idea is to test if the number divided by each individual number less than it is an int. (because if it were a decimal number, it is not a factor) .

Would it be possible to test if the resulting number is instanceof Integer?


Any help would be appreciated, and i'm sorry if explained it terribly =]

[tim]

Hello

I'm also into this stuff. I programmed a similar program in C# and I'm sure it's possible in Java. I would recommend that you use Newton's method for root finding. Just Google it. It's very fast. It's a bit tricky to list all the roots if you do not know where to begin. Why don't you try the turning points of the polynomials. That should give you a good starting point. A warning though: you cannot start Newton's method at a turning point.

Have fun!

[gibsonrocker800]

k, i'll check out Newton's method.

[gibsonrocker800]

i realized a major flaw in my idea. no matter what, the quotient of the two numbers will always be an int, because when you divide an int by and int, you get an int no matter what. but, i cant make the numbers doubles because then the quotient will be a double no matter what (1.0 or something). damn. back at square 1.

[roots]

Correct me if i am wrong

Code:

public class demo {

	public static void main(String[] args) {
		assert isInt(2.2) ;
		assert ! isInt(2.0) ;
		System.out.println("Passed simple test");
	}
	
	public static boolean isInt(double number){		
		return ((Math.floor(number) - number ) == 0.0);
	}

}

[gibsonrocker800]

dude. i had no idea that such a method existed (floor). i just looked up the API, and yep, this should work nicely. thanks alot man!

[roots]

No problem .. we are here .. lol

[gibsonrocker800]

YESSSSSSSSSS i got everything working. It finds the possible roots. Now for the easy part, since i got my SyntheticDivision class working. I'll update you when the final program is done.

[tim]

Hello gibsonrocker800.

I think that when you write a scientific program, you should always use the most accurate data type to represent a number, like Double.
You will need to differentiate a simple polynomial like the one you gave us initially. If you can't do differentiation then Newton's method won't help you much. In that case, look at the Bisection or Secant methods. Can you explain your SyntheticDivision class and what it does?

Thank you.

[gibsonrocker800]

Ok, my SyntheticDivision constructor calls for an array of doubles, the root you want to perform on, and the number of numbers (although this is kinda useless).
Here, its a very short simple class, so here's the code.

------------------------------------------------------

public class SyntheticDivision {

private double[] numbers;
private double root;
private double mid;
private double length;
public SyntheticDivision(double[] nums, double rt, double lth)
{
length = lth;
root = rt;
numbers = nums;
mid = 0;
}

public double findCoefficients(int in)
{

int index = in;
double coef = numbers[index] + mid;
mid = coef * root;
return coef;
}

}

-------------------------------------------------------------

[tim]

Oh. I thought it was a class implementing some kind of root finding method. Thank you anyway.

[gibsonrocker800]

ahh, well, i'm working on a class RootFinder. and this class is what finds the root. (it uses SyntheticDivision)