Эффективно вычислять факториал в 32-разрядной машине

Question

Как я могу реализовать функцию так, чтобы, учитывая число, она вычисляла факториал. Данное число будет большим числом (например, 100!), И я не хочу использовать библиотеку java.math.

Спасибо!

Answer 1

1. Самый большой факториал, который вы можете вычислить и по-прежнему вписываться в подписанное 32-битное целое число - 12!

2. Для факториалов, которые будут вписываться в 32-разрядное целое число, вы можете использовать любой алгоритм, который вы хотите. Фактически, вы можете даже посмотреть их так, чтобы добиться оптимальной производительности.

Как так

private static int factorial(int n) { 
    final int f[] = { 
     1, 2, 6, 24, 120, 720, 5040, 40320, 
     362880, 3628800, 39916800, 479001600 
    }; 
    if (n < 1 || n > f.length+1) 
     throw new IllegalArgumentException("n"); 
    return f[n-1]; 
} 

Answer 2

При использовании 32-битных целых чисел, независимо от того, если они подписаны или без знака, наибольшее факториала, которое может быть представлено в 12! = 479001600. Учитывая, что память дешева, эффективная реализация будет таблица поиска:

static final int [] FACTORIALS = 
    {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 
    3628800, 39916800, 479001600 }; 

int factorial(int n) { 
    return FACTORIALS[n]; 
} 

Конечно, вы должны добавить диапазон проверки для n здесь.

Для более крупных факториалов используйте BigInteger.

Answer 3

Это действительно зависит от того, какой тип данных вы указываете. Помните, что это не количество бит, которое использует ваша машина, даже на 32-битной машине, Java long будет 64 бит.

Если вы выводите либо к int или long, в быстрого способ сделать это просто иметь статический постоянный массив правильных факторных значений и искать ответ там. Это примерно так же дешево, как и получается. Вы можете вручную поместить эти константы, или написать

static final int[] factorials = { 
    1, 
    1, 
    1 * 2, 
    1 * 2 * 3, 
    1 * 2 * 3 * 4, 
    ..., 
    1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12}; 

... и компилятор вычислит эти значения во время компиляции для вас.

Если вы хотите вывести на BigInteger ... это немного интереснее. Guava's BigIntegerMath.factorial делает некоторые интересные вещи здесь; вы можете использовать его или попытаться переопределить его самостоятельно. Переход от 1 до п, ...

• факторов из полномочий 2, считая их специально, чтобы быть сдвинуты назад в конце
• умножает на число до точки, где они будут переполнять long, в этот момент он преобразует результат в BigInteger и добавляет его в список
• разделитель-победитель, умножающий список, если он имеет четыре элемента, a, b, c, d, он будет делать (a * b) * (c * d), поэтому он разбивает список пополам, рекурсивно умножает, а затем умножает результаты.
• сдвигает назад в степенях 2 в конце