Home > database >  Golden-section search in C
Golden-section search in C

Time:05-16

I'm trying to write a program that uses Golden-section search method to find the maximum area of a triangle inside an ellipse that is generated by the function (x^2 / 4) (y^2 / 9) = 1 but haven't had any luck. Managed to get the program to compile but the output I got was "-nan"

Here is what I tried:

#include <stdio.h>
#include <math.h>

// As the ellipse is given by the function (x^2 / 4)   (y^2 / 9) = 1 which can be rewritten as y = sqrt(9(1 - (x^2 / 4)))
// Thus, it can deduced that max(x) = 2, min(x) = -2, max(y) = 3 and min(y) = -3



double triangleArea(double base, double height) { // Calculates the area of one of the triangles that make up a half of the full triangle. The result will later be multiplied with 2 in order to get the area of the full triangle.

    double area = (base * height) / 2;
    return area;

}

double goldenSearch_Max (double xLower, double xUpper) {

    double goldenRatio = 0.5 * (sqrt(5) - 1.0); // Initialising Golden Ratio.

    double x1 = xUpper - (xUpper - xLower) / goldenRatio;
    double x2 = xLower   (xUpper - xLower) / goldenRatio;

    while (fabs(x2 - x1) > 0.00001) {

        if ((triangleArea(x1, sqrt(9 * (1 - (x1 * x1 / 4))))) > (triangleArea(x2, sqrt(9 * (1 - (x2 * x2 / 4)))))) {

            xUpper = x2;

        }
        else {

            xLower = x1;

        }

        x1 = xUpper - (xUpper - xLower) / goldenRatio;
        x2 = xLower   (xUpper - xLower) / goldenRatio;

    }

    return (xUpper   xLower);   

}

int main() {

    double goldenRatio = 0.5 * (sqrt(5) - 1.0); // Initialising Golden Ratio.

    //double triangleBase = 2   x; // The elliptical equation's max(x) was 2 and the base of the two halves of the triangle is located on the x axis. So the base of one of the halves is 2   x, x being the extra length after the 2 units of the x axis.
    //double triangleHeight = sqrt(1 - (x * x) / 4) * 3; // As the elliptical equation can also be written as y = sqrt(9(1 - (x^2 / 4))) after changing the places of the y terms and the result.
    double xNew = goldenSearch_Max(0, 2);
    printf("%f", (triangleArea(xNew, sqrt(9 * (1 - (xNew * xNew / 4))))));

    return 0;
}

Any help would be appreciated.

CodePudding user response:

I can spot a couple of problems:

double goldenRatio = 0.5 * (sqrt(5) - 1.0);

That's the inverse of the Golden Ratio. Which is fine, as long as it's used accordingly:

double const inv_golden_ratio = 0.5 * (sqrt(5) - 1.0);
double x1 = xUpper - (xUpper - xLower) * inv_golden_ratio;
//                                     ^
// ... 

return (xUpper   xLower);

Shouldn't be better to return the value corresponding to the actual max (or min)?

The average of the points could be fine, too, but the plain sum is wrong.

return (x1   x2) * 0.5;
  • Related