Типи зі знаком (signed)
Найшвидший алгоритм обчислення факторіала числа з типом int - це використання таблиці. Так як переповнення int призводить до невизначеного поведінки (UB), то максимальне значення факторіала обмежена INT_MAX.
Для 32-розрядної int максимальний факторіал це fac (12) = 479001600. з цього найшвидша функція обчислення факторіала int32_t виглядає так:
Типи без знака (unsigned)
Для unsigned int все цікавіше, він може переповнюватися, але fac (34) має множник 2 ^ 32:
З цього починаючи з 34 всі результати fac (uint32_t) дорівнюватимуть нулю.
64-розрядні типи
Для 64-розрядних чисел переповнення відбувається після fac (20). нулі починаючи з fac (66).
Таким чином, використання таблиці факториалов з 66 елементів покриє всіх типи до 64 розрядів:
Думаю, що найшвидший алгоритм обчислення факторіала визначається структурою обчислювальних засобів.
Наприклад, формула Стірлінга допускає подання виду
n!
S (n) = a (n / e) n + 1/2. де a = sqrt (2 * pi * e).
log2 S (n) = ((n +1/2) (ln n - 1) + ln a) * log2 e = L (n), S (n) = exp (* ln2) * 2 [L (n) ].
При цьому двійковий запис факторіала закінчується на B (n) = [n / 2] + [n / 2 2] + [n / 2 3] +. нулів (наприклад, B (2 k) = [2 k / 2] + [2 k / 2 2] +. + 2 + 1 = 2 k -1), і тому множник при ній цілий.
В результаті отримуємо формулу для швидкого факторіала як цілого числа з бінарним масштабним коефіцієнтом.
n! = [Exp (L (n) * ln2) * 2 L (n) -B (n) +1/2] * 2 B (n),
яка при правильно обраної точності обчислень буде точною.
відповідь дан 2 дек '15 о 17:06
Питання дуже швидко вирішується за допомогою гугла, відповідь узятий з сайту algolist.manual.ru:
Звертаю увагу на те, що при обчисленнях відбувається послідовне множення довгого числа на звичайне (з базового типу даних, наприклад, long int). В результаті алгоритм множення має складність O (m), m - довжина числа, і простий в реалізації.
Ось наближення десяткового логарифма факторіала:
Ціла частина цього покаже кількість знаків числа-1, а з мантиссой можна працювати.
Можна обчислювати факторіал як eln (n!), І це буде швидше, ніж пряме множення. Але це не буде точне значення для великих значень n, де є реальний виграш в швидкості.
Проте, часто (наприклад, в обчисленні біноміальних коефіцієнтів) нам потрібен не сам факторіал, а якесь значення, що виходить в результаті поділу величезного факторіала на інші числа того ж порядку, і в результаті виходить невелика кількість.
У цьому випадку має сенс оперувати саме з логарифмом факторіала, який обчислюється (як видно, наприклад, з исходника вище) набагато простіше і швидше. Розподіл і множення будуть замінені різницею і сумою логарифмів. Якщо потрібні реально ефективні обчислення, то такий шлях при контролі точності обчислень, безумовно, краще.
відповідь дан 28 Січня '11 о 10:46
По-перше, треба відмовитися від рекурсії: чи не буде накладних витрат на розгортання і згортання стека.
По-друге, можна зробити многопоточность: заюзать стоку ядер, скільки є в ядрі - вийде O (n) / число ядер. Наприклад, 2 ядра і факторіал 100: перший потік 1 * 2 *. * 50; другий потік 51 * 52 *. 100. потім перемножити результат. По-третє, розвиваючи ідею номер 2, можна скласти статичний масив з уже вичісеннимі факторіалами (його крок ділення і кількість елементів впливають на загальну швидкість в цілому)
Треба порахувати факторіал 102, беремо вже порахувати факторіал 100, множимо його на 101 і на 102, - швидко.
А взагалі, все 3 методу відразу - буде досить спритно.
До речі, можна скласти масив не під час компіляції, а при роботі програми. Наприклад, при статичної компіляції було в масиві 2 значення: 1! і 10! а треба порахувати 102! Ми його вважаємо і потім додаємо в масив факторіал 100! Раптом нам треба буде вважати 105!
Думаю, обчислювати рекурсивно нікому в голову б і не прийшло. Предподсчёт деяких значень не вносить взагалі ніякого поліпшення, коли обчислюється один факторіал. Природно, якщо треба обчислити кілька факториалов послідовно, то можна зберегти попередня результати і це ваще буде працювати за амортизовану одиницю! Розпаралелювання - це хитрощі, а питання-то алгоритмічний, а не практичний. - kirelagin 28 Січня '11 о 11:01
Питання алгоритмічний, але має прикладний характер. - Nicolas Chabanovsky ♦ 28 Січня '11 о 11:27
@ Матроскін в такому випадку, зберіть воєдино всі запропоновані оптимізації :). - kirelagin 29 Січня '11 о 11:30