Видове със знак (подпис)
Най-бързият алгоритъм за изчисляване на факториел на INT тип - това е използването на таблицата. Тъй като преливане INT резултати в неопределен поведение (UB), максималната стойност се ограничава факторен INT_MAX.
За 32-битова вътр е максималната факторен FAC (12) = 479001600. на най-бързите int32_t факторен функция изглежда така:
Видове неподписан (неподписан)
Unsigned Int за по-интересно, тя може да изтече, но FAC (34) има коефициент на 2 ^ 32:
На че от всички 34 от фак (uint32_t) ще бъде нула.
типове 64-битови
За 64-битови числа преливане настъпва след FAC (20). нула, тъй FAC (66).
По този начин, използването на масата 66 факториелите обхващат всички видове елементи до 64 бита:
Мисля, че най-бързият алгоритъм за изчисляване на факториел структура се определя чрез изчисляване средства.
Например, формулата Stirling признава представяне
н!
S (п) = а (п / е) п + 1/2. където а = SQRT (2 * пи * д).
log2 S (п) = ((п +1/2) (LN п - 1) + LN а) * log2 е = L (п), S (п) = ехр (* ln2) * 2 [L (п) ].
В този двоичен нотация факторен завърши B (п) = [п / 2] + [п / 2 2] + [п / 2 3] +. нули (например, В (2 к) = [2 к / 2] + [2 к / 2 2] +. + 2 + 1 = 2 к-1), и следователно, фактор с него.
В резултат на това ние се получи формула за бързо факторен като цяло число с фактор на двоичен мащаб.
н! = [Exp (L (п) * ln2) * 2 L (п) -В (п) +1/2] * 2 B (п),
който при правилно избрана точност на изчисленията ще бъде точна.
Отговорено 02 декември '15 в 17:06
Въпросът е решен много бързо с помощта на Google, отговорът е взета от algolist.manual.ru сайт:
Да се обърне внимание на факта, че изчисленията са последователно умножаване дълго брой на нормален (от типа на база данни, например дълго Int). Резултатът от алгоритъма за умножение има сложност на O (m), м - дължина на брой, и е лесна за изпълнение.
Това е подходът на общата логаритъм на факториел:
цялата част от тази цифра показва броя на 1-шест цифри, и може да работи с мантисата.
Можете да изчислите факториела като ELN (п!), И това ще бъде по-бързо от пряк размножаването. Но това няма да е точната стойност за големи стойности на N, където има истинска полза за скорост.
Въпреки това, често (например при изчисляването на Биномен коефициент), ние не се нуждаем от факториел, както и някои ценности, които са получени чрез разделяне на огромен факториел от друга от същия порядък, както и резултатът е малък номер.
В този случай, че има смисъл да го оперират с логаритъм на факториел, който се изчислява (както се вижда, например, от източника по-горе) е много по-лесно и по-бързо. Division и умножение ще бъде заменен от разликата и сумата от логаритмите. Ако имате нужда от наистина ефективен изчисление, този път под контрола на точността на изчисленията, разбира се, за предпочитане.
Отговорено 28 '11 януари в 10:46
Първо, трябва да се откаже от рекурсията не е над разгръщане и свиване на комина.
На второ място, това е възможно да се направи многонишкова: zayuzat отток ядра, тъй като има в основата - ще бъде O (N) / брой ядра. Например, ядрото 2 и факторен 100: първи поток 1 * 2 *. * 50; втори поток 51 * 52 *. 100. След това полученият резултат се умножава. На трето място, развитие на идеята за номер 2, можете да създадете статичен масив е вече vychisennymi факториелите (и стъпка се раздели броят на елементи се отрази като цяло скоростта на цялото)
Необходимо е да се изчисли факториела на 102, вече брои, да вземе факториела на 100, го умножете по 101 и 102 - бързо.
Като цяло, всички 3 методи наведнъж - ще доста бързо.
Между другото, можете да направите на масива не е по време на компилация, а когато програмата. Например, когато статичен компилация е в масива 2 стойности: 1! и 10! и е необходимо да се брои 102! Ние го вярвам, и след това добавете към дългия списък с факториела на 100! ние изведнъж трябва да се разглежда като 105!
Мисля, рекурсивно изчисляване на някой в главата няма да дойде. Predpodschot някои стойности не носи никакво подобрение на всички, когато се изчислява един факторен. Разбира се, ако имате нужда да се изчисли броят на факториелите в серия, можете да спестите предишните резултати и най-накрая, че ще работи за амортизирана единица! Паралелното - трик, и въпросът е алгоритмично, отколкото практични. - kirelagin 28 януари '11 в 11:01
Въпрос алгоритмично, но е приложен характер. - Никола Chabanovsky ♦ 28 януари '11 в 11:27
@ Matroskin в такъв случай, събери всичките всички предложения :). - kirelagin 29 яну '11 в 11:30
Свързани статии