Динамическая проверка целочисленных / длинных переполнений Java в зависимости от производительности

Question

Это довольно теоретический вопрос, поэтому, хотя язык определенно является Java, подойдет любое общее решение.

Предположим, я хотел написать тривиальную факторную функцию:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }
    return p;
}

НоТеперь я также хочу проверить, не переполняется ли факториал (без простого жесткого кодирования MAX_FACTORIAL_PARAMETER или чего-то подобного).В общем, проверка переполнения во время умножения так же проста, как проверка результата по исходным входам, но в этом случае, поскольку переполнение может произойти в любой точке, было бы довольно дорого выполнять больше делений и сравнений в каждом цикле.*

Тогда возникает двоякий вопрос: есть ли способ решить факторную проблему переполнения без проверки переполнения умножения на каждом шаге или жесткого кодирования максимально допустимого параметра?

И вообще какя должен подходить к проблемам, которые включают много этапов итерации / рекурсии, которые могут молча завершаться сбоем на каждом этапе без ущерба для производительности, вводя дорогие проверки на каждом?

Answer 1

В этом конкретном случае самое простое, что нужно сделать, это жестко указать максимальное значение 'n'. Если бы скорость была для вас важна, вы бы хранили все возможные значения в массиве (их не много) и ничего не вычисляли. ;)

Если вы хотите улучшить метод, используйте long результат (не намного лучше, но простое изменение) или используйте BigInteger, у которого нет проблемы переполнения. ;)

Answer 2

Хотя Java не помогает вам в этом, безусловно, есть языки, которые помогают с переполнением.Например, C # предоставляет проверенное ключевое слово .Внизу эта функция, вероятно, использует аппаратную поддержку в виде флага переполнения .

Answer 3

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

В данном примере лучше всего проверять каждый цикл. Это не так много времени, так как даже не изменит ваш класс сложности (потому что O (n) = O (n + n) = O (2n) = O (n)) В большинстве случаев было бы также лучше выполнить простую проверку, поскольку она сохраняет ваш код чистым и обслуживаемым.

Answer 4

Начиная с Java 8, Java имеет метод Math.multiplyExact(). Это проверяет внутренне для переполнения. Поскольку метод является «внутренним» ( см. Здесь список ), реализация Java будет заменена выделенными низкоуровневыми машинными инструкциями, если это возможно, возможно, просто проверяется флаг переполнения ЦП, что делает проверку вполне быстро.

Кстати, обратите внимание, что на JDK 1.8.0_40 это выглядит намного быстрее по сравнению с JDK 1.0.8_05.

Answer 5

В Java переполнение должно давать отрицательный результат, так что вы, вероятно, можете использовать его в качестве проверки:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    long p = 1;
    for(int i = 1; i <= n; i++)
    {
        p = p * n;
    }

    if (p < 0)
    {
        throw new ArithmeticException("factorial: Overflow");
    }

    return p;
}

В качестве альтернативы, для языков с положительным переполнением, так как n!> (n - 1)!Вы можете попробовать:

long factorial(int n)
{
    //handle special cases like negatives, etc.

    if (n == 1 || n == 2) { return n; }

    // Calculate (n-1)!
    long p = 2;
    for(int i = 3; i < n; i++)  // Note changes to loop start and end.
    {
        p = p * n;
    }

    long previous = p;  // (n-1)!

    p = p * n;  // Calculate n!

    if (p < previous)
    {
        throw new ArithmeticException("factorial: Overflow");
    }
    return p;
}

Эти методы требуют только одну проверку на факториал.

Answer 6

Есть ли способ решить факторную проблему переполнения без проверки переполнения умножения на каждом шаге или жесткого кодирования максимально допустимого параметра?

Нет.

И вообще, как я должен подходить к проблемам, которые включают в себя много этапов итерации / рекурсии, которые могут молча завершаться неудачей на каждом этапе без ущерба для производительности, вводя дорогие проверки на каждом?думаю, что вы можете в Java.

Некоторые наборы машинных инструкций устанавливают бит 'oveflow', если предыдущая целочисленная арифметическая операция переполнена, но большинство языков программирования не предоставляют способ ее использования.C # является исключением, как и (IIRC) Ada.