Algorithmen

[stefi]

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

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

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:

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

}

 

[Marinek]

Sicherlich müsste man beide Algorithmen aus dem Studium kennen. Bei mir ist es aber ein paar Tage her, daher gehen wir einfach mal davon aus, dass ich persönlich nicht weiß, wie sie funktionieren.

Das vorweg:

Da du keine Fehlermeldung gepostet hast, gehe ich davon aus, dass du einen allgemeinen Hinweis benötigt:

- Tests sollten so gestaltet sein, dass diese reproduzierbar sind. Statt zufällige Zahlen zu verwenden für die Verfikation, werden üblicherweise Äquivalenzklassen erstellt.

Dabei ist eine Äquivalenzklasse eine Menge von Input, die gleich sind. Zum Beispiel: Gültige Werte aus dem Bereich Minimum. Analog dazu könnte mans ich ein Maximum überlegen.

Oder ungültige Äquivalenzklassen, die einen Fehler reproduzieren sollen.

Dann Bildet man weitere je nach Implementierung für verschiedene Pfade im Quellcode.

Wenn Test mit Äquivalenzklassen scheitern, müsste man also den Quellcode debuggen und prüfen an welcher Stelle das genau passiert. Die Stelle ist dann zu korrigieren. Damit erreicht man, dass der ursüngliche Quellcode funktioniert.

---
Nachtrag:

Deine Implementierung des Hordnerschemas ist falsch. Du addierst ein array. Die Addition in Java ist dafür nicht definiert.

So wäre es korrekt: Vergleiche die Lösungen und finde den Fehler.

Horner's Method for Polynomial Evaluation - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org