Results 1 to 12 of 12
  1. #1
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default Root Finder for polynomials

    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 =]

  2. #2
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default

    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!
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  3. #3
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

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

  4. #4
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    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.

  5. #5
    roots's Avatar
    roots is offline Moderator
    Join Date
    Jan 2008
    Location
    Dallas
    Posts
    293
    Rep Power
    7

    Default

    Correct me if i am wrong

    Java 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);
    	}
    
    }
    dont worry newbie, we got you covered.

  6. #6
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    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!

  7. #7
    roots's Avatar
    roots is offline Moderator
    Join Date
    Jan 2008
    Location
    Dallas
    Posts
    293
    Rep Power
    7

    Default

    No problem .. we are here .. lol
    dont worry newbie, we got you covered.

  8. #8
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    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.

  9. #9
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default

    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. :D
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  10. #10
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

    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;
    }

    }

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

  11. #11
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default Okay then

    Oh. I thought it was a class implementing some kind of root finding method. Thank you anyway. ;)
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  12. #12
    gibsonrocker800's Avatar
    gibsonrocker800 is offline Senior Member
    Join Date
    Nov 2007
    Location
    New York
    Posts
    143
    Rep Power
    0

    Default

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

Similar Threads

  1. Listing file system from root directory
    By Java Tip in forum Java Tip
    Replies: 1
    Last Post: 04-18-2009, 11:03 AM
  2. JSP/Servlet getting root directory
    By Java Tip in forum Java Tip
    Replies: 1
    Last Post: 01-06-2009, 09:51 AM
  3. Find nth root of a number
    By perito in forum New To Java
    Replies: 1
    Last Post: 03-03-2008, 07:51 AM
  4. Library Finder 1.2
    By JavaBean in forum Java Software
    Replies: 0
    Last Post: 07-15-2007, 05:43 PM
  5. Context Root change
    By rvasu_77 in forum Advanced Java
    Replies: 2
    Last Post: 07-12-2007, 11:18 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •