Hallo zusammen, ich habe versucht diese zwei Algorithmen (HornersRule und Estrin) zu implementieren um einen zufällig erzeugten Polynom aufzulösen. Aber irgendwie bekomm ich das mit den Test nicht hin.
Wie bekomme ich es hin, dass meine zwei Algorithmen auch bei zufällig sehr gross erzeugten Polynomen funktionieren?
Danke im Voraus für eure Hilfe.
Gruss Stefi
Test:
Wie bekomme ich es hin, dass meine zwei Algorithmen auch bei zufällig sehr gross erzeugten Polynomen funktionieren?
Danke im Voraus für eure Hilfe.
Gruss Stefi
Java:
public class Horner {
public static int horner(int[] polynomial, int x) {
int ergebnis = polynomial[0];
for (int i = 1; i < polynomial.length; i++) {
ergebnis = x * ergebnis + polynomial;
}
return ergebnis;
}
Java:
public class Estrin {
public static int estrin3_Main(int xWert, int[] polynom) {
if (polynom.length == 0) {
return 0;
} else if (polynom.length == 1) {
return polynom[0];
} else {
int exponent;
exponent = polynom.length - 2;
return estrin3((int) Math.pow(xWert, exponent), polynom, 0, polynom.length - 1, 4);
}
}
private static int estrin3(int xWert, int[] polynom, int lower_bound, int upper_bound, int x_original) {
int new_bound, sum, left_half, right_half;
if (upper_bound == lower_bound) {
return polynom[lower_bound];
} else {
if ((upper_bound + lower_bound) % 2 != 0 || (upper_bound - lower_bound) == 2) {
new_bound = ((lower_bound + upper_bound) / 2);
} else {
new_bound = ((lower_bound + upper_bound) / 2) - 1;
}
left_half = estrin3(xWert / x_original, polynom, lower_bound, new_bound, x_original);
right_half = estrin3(xWert / x_original, polynom, new_bound + 1, upper_bound, x_original);
if (lower_bound == 0 && upper_bound == 1 && polynom.length % 2 == 1) {
xWert = xWert / x_original;
}
if (lower_bound == 0 && upper_bound == polynom.length - 1 && polynom.length % 2 == 1) {
sum = right_half * (xWert / x_original) + left_half;
} else {
sum = left_half + right_half * xWert;
}
}
return sum;
}
Test:
Java:
public class HornerEstrinTest {
@Test
public void testHorner() {
int x = 4;
int[] polynomial;
int result;
for (int i = 0; i < 1000; i++) { // test 1000 different polynomials
polynomial = generatePolynomial(10000); // generate a random polynomial with 10000 coefficients
result = 0;
int exponent = polynomial.length - 1;
for (int j : polynomial) {
result += (int) (j * Math.pow(x, exponent));
exponent--;
}
assertEquals(result, Horner.horner(polynomial, x));
}
}
public int[] generatePolynomial(int size) {
int[] polynomial = new int[size];
for (int i = 0; i < size; i++) {
polynomial[i] = (int) (Math.random() * 100); // generate random coefficients between 0 and 99
}
return polynomial;
}
@Test
public void testEstrin() {
int x = 4;
int[] polynomial;
int result;
for (int i = 0; i < 1000; i++) { // test 1000 different polynomials
polynomial = generatePolynomial(10000); // generate a random polynomial with 10000 coefficients
result = Estrin.estrin3_Main(x, polynomial);
int exponent = polynomial.length - 1;
int expectedResult = 0;
for (int j : polynomial) {
expectedResult += (int) (j * Math.pow(x, exponent));
exponent--;
}
assertEquals(expectedResult, result);
}
}
private int[] generatePolynomial(int size) {
int[] polynomial = new int[size];
for (int i = 0; i < size; i++) {
polynomial[i] = (int) (Math.random() * 100); // generate random coefficients between 0 and 99
}
return polynomial;
}
}