Skip to content

Instantly share code, notes, and snippets.

@hetelek
Created November 25, 2013 18:27
Show Gist options
  • Save hetelek/7646098 to your computer and use it in GitHub Desktop.
Save hetelek/7646098 to your computer and use it in GitHub Desktop.
A class which will calculate the real roots of a polynomial, when given the coefficients.
import java.util.*;
public class Polynomial
{
private static final double ROOT_LEEWAY = 0.000000001;
private double[] coefficients;
private double remainder;
public Polynomial(double[] coefficients, double remainder)
{
this.coefficients = coefficients;
this.remainder = remainder;
}
public Polynomial(double[] coefficients)
{
this.coefficients = coefficients;
this.remainder = 0;
}
public ArrayList<Double> possibleRoots()
{
ArrayList<Double> possibilities = new ArrayList<Double>();
double p = coefficients[coefficients.length - 1];
double q = coefficients[0];
ArrayList<Double> pFactors = findFactors(p);
ArrayList<Double> qFactors = findFactors(q);
for (Double pFactor : pFactors)
for (Double qFactor : qFactors)
{
double possibility = pFactor / qFactor;
if (!possibilities.contains(possibility))
possibilities.add(possibility);
}
return possibilities;
}
public ArrayList<Double> realRoots()
{
ArrayList<Double> roots = new ArrayList<Double>();
ArrayList<Double> possibleRoots = possibleRoots();
for (Double possibleRoot : possibleRoots)
{
double pluggedIn = plugin(possibleRoot);
if (Math.abs(pluggedIn) <= ROOT_LEEWAY)
roots.add(possibleRoot);
}
return roots;
}
public double plugin(double x)
{
double answer = 0;
for (int i = 0; i < coefficients.length; i++)
answer += coefficients[i] * Math.pow(x, coefficients.length - (i + 1));
return answer;
}
public Polynomial divide(double divisor)
{
double[] newCoefficients = new double[coefficients.length - 1];
newCoefficients[0] = coefficients[0];
for (int i = 1; i < newCoefficients.length; i++)
newCoefficients[i] = (newCoefficients[i - 1] * divisor) + coefficients[i];
double remainder = (newCoefficients[newCoefficients.length - 1] * divisor) + coefficients[coefficients.length - 1];
return new Polynomial(newCoefficients, remainder);
}
public double getRemainder()
{
return remainder;
}
public double[] getCoefficients()
{
return coefficients;
}
private ArrayList<Double> findFactors(double num)
{
ArrayList<Double> factors = new ArrayList<Double>();
for (int i = (int)(-num); i <= num; i++)
if (num / i == (int)(num / i))
factors.add((double)i);
return factors;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment