Найдите наименьший квадратный корень в определенном интервале

Я хочу создать метод Java, который возвращает наименьший корень квадратного уравнения в интервале (0, 1). Если в интервале нет решений, вернуть 1. Мне нужна помощь в создании эффективного алгоритма.

Это мой текущий метод:

public static float getLowestRoot(float A, float B, float C) {
    float D = B*B - 4*A*C;
    if(D < 0) return 1;

    float sD = (float) Math.sqrt(D);

    float x1 = (-B + sD) / (2*A);
    float x2 = (-B - sD) / (2*A);

    if(x2 < x1) {
        float tmp = x2;
        x2 = x1;
        x1 = tmp;
    }

    if(x1 > 0 && x1 < 1) return x1;
    if(x2 > 0 && x2 < 1) return x2;

    return 1;
}

Этот метод работает, но мне было интересно, есть ли способ сжать алгоритм, потому что сейчас он кажется раздутым.


java algorithm quadratic
person Wilco    schedule 15.10.2013    source источник
comment
Что делать, если решение равно 1?   -  person arynaq    schedule 15.10.2013
comment
Я предлагаю поменять float на double. Вы получите более точные результаты.   -  person Konstantin Yovkov    schedule 15.10.2013
comment
Я думаю, что в вашем коде нет ничего принципиально неправильного (за исключением того, что я бы определенно не использовал 1.0 для обозначения отсутствия решения, поскольку это также допустимое решение).   -  person NPE    schedule 15.10.2013
comment
@arynaq: тогда возвращаемое значение должно быть 1.   -  person Wilco    schedule 15.10.2013
comment
@kocko: спасибо за предложение, но мне не нужна точность, с плавающей запятой все в порядке.   -  person Wilco    schedule 15.10.2013
comment
Если он не сломан, не чините его. Почему вы думаете, что это "раздутый"? Мне он кажется коротким и чистым.   -  person Troubleshoot    schedule 15.10.2013
comment
@NPE: в этом приложении я хочу, чтобы 1.0 было возвращаемым значением, если решений нет. Но, скажем, нет, каким будет возвращаемое значение в случае отсутствия решений? Это должен быть поплавок, верно?   -  person Wilco    schedule 15.10.2013
comment
@Wilco: NaN звучит как хороший кандидат. en.wikipedia.org/wiki/NaN   -  person NPE    schedule 15.10.2013
comment
@Troubleshoot: в этом случае я ищу метод с максимальной производительностью. Заявленная проблема действительно проста, и мне кажется, что я упускаю что-то, что может легко сократить алгоритм до меньшего количества строк кода.   -  person Wilco    schedule 15.10.2013
comment
@NPE: Спасибо за совет!   -  person Wilco    schedule 15.10.2013
comment
Если вы знаете, где находится максимальное / минимальное значение, вы можете сначала проверить значения y (0) и y (1), поскольку тогда вы сможете пропустить укоренение, если все точки имеют один и тот же знак.   -  person jgroenen    schedule 15.10.2013

Ответы (1)


arrow_upward
0
arrow_downward

1) обратите внимание, что "меньше строк кода" не означает "более высокая производительность".

2) вы можете рассмотреть Math.abs(sD) < Epsilon - если да, то вам не нужно вычислять оба корня. Я предполагаю, что в таких случаях это может повысить скорость.

3) Я думаю, вы можете улучшить проверку того, какой корень меньше:

x1 <= x2 <===>  -B+sD/(2A) <= -B-sD/(2A) <==(adding sD/(2A) to both sides)==> 
         <===> -B+2sD/(2A) <= -B/(2A)    <==(adding B/(2A) to both sides)==>
         <===>    2sD/(2A) <= 0
         <===>           A <= 0 (because sD >= 0)

Таким образом, вы можете избежать замены корней:

int signA = Math.signum(A);
float x1 = (-B + -signA * sD) / (2*A);
float x2 = (-B + signA * sD) / (2*A);

// always x1 <= x2

Опять же, я предполагаю, что это повышает производительность, но не измерял.

Итак, окончательный ответ будет выглядеть примерно так:

public static float getLowestRoot(float A, float B, float C) {
    float D = B*B - 4*A*C;

    if (D < 0) return 1;

    if (Math.abs(D) < 0.0001)  // not sure how many 0s for float
    {
        float x = -B / (2*A);

        if (x > 0 && x < 1) return x;

        return 1;
    }

    float sD = (float) Math.sqrt(D);

    int signA = Math.signum(A);
    float x1 = (-B + -signA * sD) / (2*A);
    float x2 = (-B + signA * sD) / (2*A);

    if (x1 > 0 && x1 < 1) return x1;
    if (x2 > 0 && x2 < 1) return x2;

    return 1;
}
person BartoszKP    schedule 15.10.2013
comment
@Wilco Я изменил ответ, чтобы показать некоторые идеи производительности. - person BartoszKP; 15.10.2013