La fonction factorielle: Fact(N) = N!
Description
Bonjour,
Cette fonction archi-connue est souvent utilisée pour introduire les boucles ("for" ou autres) ou la notion de récursivité.
Cela correspond aux deux manières d'exprimer sa définition:
a) 0! = 1; 1! = 1; 2! = 1×2 = 2; 3! = 1×2×3 = 6; 4! = 1×2×3×4 = 24; ...
b) 0! = 1; (n+1)! = n! × (n+1).
On la voit apparaître dans divers calculs:
- Nombre de permutations: n! (Combinatoire)
- Nombre d'arrangements: A(k,n) = n!/(n-k)!
- Combinaisons (ou coefficient binomial): C(k,n) = A(k,n)/k! = n!/(n-k)!/k!
- Formules de Taylor (Wiki)
- Formules de Stirling (Wiki)
- Transformation inverse de Laplace (méthode de Stehfest) (Wiki)
- etc, etc, ...
Nous allons analyser la factorielle basée sur 4 types de nombres:
- Entiers positifs 32 bits (uint32_t)
- Entiers positifs 64 bits (uint64_t)
- Nombres en virgule flottante 32 bits (float)
- Nombres en virgule flottante 64 bits (double)
Donnons ici la partie de l'output de Main.cpp concernant ces codes:
Les résultats et limitations correspondent aux quatre codes traités plus haut.
Le temps de calcul est peut-être très légèrement plus grand.
Comme il est impossible de dépasser N = 170, l'utilisation de la mémoire (stack) reste raisonnable.
Une troisième manière, souvent oubliée par les plus grands auteurs, est de calculer à l'avance un array qui contient les factorielles utilisées:
Le petit test de comparaison fait à la fin dans Main.cpp montre clairement qu'il est fortement recommandé d'utiliser ce procédé, surtout lorsque le temps de calcul est important.
Fonction: somme = 5.62183143603746e+196, temps = 8752 ms
Array: somme = 5.62183143603746e+196, temps = 78 ms
En observant les résultats obtenus par Main.cpp, on peut indiquer les limites d'utilisation suivantes:
- Entier positif 32 bits: 0! à 12!
- Entier positif 64 bits: 0! à 20!
- Nombres en virgule flottante 32 bits (float): 0! à 34! (### 13! = 6227020800)
- Nombres en virgule flottante 64 bits (double): 0! à 170! (### 21! = 51090942171709440000)
###: Au dessus de ce nombre, les résultats ne sont plus "mathématiquement" précis car la mantisse du format utilisé est "trop petite".
Par contre, au sens "virgule flottante", ces valeurs sont bonnes et "précises".
Bonne lecture.
Cette fonction archi-connue est souvent utilisée pour introduire les boucles ("for" ou autres) ou la notion de récursivité.
Cela correspond aux deux manières d'exprimer sa définition:
a) 0! = 1; 1! = 1; 2! = 1×2 = 2; 3! = 1×2×3 = 6; 4! = 1×2×3×4 = 24; ...
b) 0! = 1; (n+1)! = n! × (n+1).
On la voit apparaître dans divers calculs:
- Nombre de permutations: n! (Combinatoire)
- Nombre d'arrangements: A(k,n) = n!/(n-k)!
- Combinaisons (ou coefficient binomial): C(k,n) = A(k,n)/k! = n!/(n-k)!/k!
- Formules de Taylor (Wiki)
- Formules de Stirling (Wiki)
- Transformation inverse de Laplace (méthode de Stehfest) (Wiki)
- etc, etc, ...
Nous allons analyser la factorielle basée sur 4 types de nombres:
- Entiers positifs 32 bits (uint32_t)
- Entiers positifs 64 bits (uint64_t)
- Nombres en virgule flottante 32 bits (float)
- Nombres en virgule flottante 64 bits (double)
Factorielles utilisant une boucle
uint32_t FoncFact32(uint32_t N) { // N! avec N <= 12
uint32_t x=1;
if (N>1) for (uint32_t i=N; i>=2; --i) x*=i;
return x;
}
uint64_t FoncFact64(uint32_t N) { // N! avec N <= 20
uint64_t x=1;
if (N>1) for (uint32_t i=N; i>=2; --i) x*=i;
return x;
}
float FoncFactF(uint32_t N) { // N! avec N <= 34; précis: N <= 13
float x=1;
if (N>1) for (uint32_t i=N; i>=2; --i) x*=i;
return x;
}
double FoncFactD(uint32_t N) { // N! avec N <= 170; précis: N <= 21
double x=1;
if (N>1) for (uint32_t i=N; i>=2; --i) x*=i;
return x;
}
Donnons ici la partie de l'output de Main.cpp concernant ces codes:
FoncFact32: 0! = 1 = 0X00000001 1! = 1 = 0X00000001 2! = 2 = 0X00000002 3! = 6 = 0X00000006 4! = 24 = 0X00000018 5! = 120 = 0X00000078 6! = 720 = 0X000002D0 7! = 5040 = 0X000013B0 8! = 40320 = 0X00009D80 9! = 362880 = 0X00058980 10! = 3628800 = 0X00375F00 11! = 39916800 = 0X02611500 12! = 479001600 = 0X1C8CFC00 13! = 1932053504 = 0X7328CC00 ..... FAUX ..... FoncFact64: 0! = 1 = 0X0000000000000001 1! = 1 = 0X0000000000000001 2! = 2 = 0X0000000000000002 3! = 6 = 0X0000000000000006 4! = 24 = 0X0000000000000018 5! = 120 = 0X0000000000000078 6! = 720 = 0X00000000000002D0 7! = 5040 = 0X00000000000013B0 8! = 40320 = 0X0000000000009D80 9! = 362880 = 0X0000000000058980 10! = 3628800 = 0X0000000000375F00 11! = 39916800 = 0X0000000002611500 12! = 479001600 = 0X000000001C8CFC00 13! = 6227020800 = 0X000000017328CC00 14! = 87178291200 = 0X000000144C3B2800 15! = 1307674368000 = 0X0000013077775800 16! = 20922789888000 = 0X0000130777758000 17! = 355687428096000 = 0X0001437EEECD8000 18! = 6402373705728000 = 0X0016BEECCA730000 19! = 121645100408832000 = 0X01B02B9306890000 20! = 2432902008176640000 = 0X21C3677C82B40000 21! = 14197454024290336768 = 0XC5077D36B8C40000 ..... FAUX ..... FoncFactF: 0! = 1 = 0X3F800000 1! = 1 = 0X3F800000 2! = 2 = 0X40000000 3! = 6 = 0X40C00000 4! = 24 = 0X41C00000 5! = 120 = 0X42F00000 6! = 720 = 0X44340000 7! = 5040 = 0X459D8000 8! = 40320 = 0X471D8000 9! = 362880 = 0X48B13000 10! = 3628800 = 0X4A5D7C00 11! = 39916800 = 0X4C184540 12! = 479001600 = 0X4DE467E0 13! = 6227020800 = 0X4FB99466 14! = 87178289152 = 0X51A261D9 15! = 1307674279936 = 0X53983BBB 16! = 2.092278847898e+013 = 0X55983BBB 17! = 3.556874146284e+014 = 0X57A1BF77 18! = 6.40237406729e+015 = 0X59B5F767 19! = 1.216450960042e+017 = 0X5BD815C9 20! = 2.432902298042e+018 = 0X5E070D9F 21! = 5.109094523522e+019 = 0X603141E0 22! = 1.124000724806e+021 = 0X6273BA93 23! = 2.585201744459e+022 = 0X64AF2E1A 24! = 6.204483105839e+023 = 0X67036292 25! = 1.551120992632e+025 = 0X694D4A06 26! = 4.032915733766e+026 = 0X6BA6CC28 27! = 1.088886923454e+028 = 0X6E0CBC3F 28! = 3.048883905132e+029 = 0X70764971 29! = 8.841760661468e+030 = 0X72DF328A 30! = 2.652529093045e+032 = 0X75513F66 31! = 8.222838447587e+033 = 0X77CAB568 32! = 2.631308303228e+035 = 0X7A4AB568 33! = 8.683317876021e+036 = 0X7CD10B14 34! = 2.952328838438e+038 = 0X7F5E1BC9 35! = 1.#INF = 0X7F800000 ..... FAUX ..... FoncFactD: 0! = 1 = 0X3FF0000000000000 1! = 1 = 0X3FF0000000000000 2! = 2 = 0X4000000000000000 3! = 6 = 0X4018000000000000 4! = 24 = 0X4038000000000000 5! = 120 = 0X405E000000000000 6! = 720 = 0X4086800000000000 7! = 5040 = 0X40B3B00000000000 8! = 40320 = 0X40E3B00000000000 9! = 362880 = 0X4116260000000000 10! = 3628800 = 0X414BAF8000000000 11! = 39916800 = 0X418308A800000000 12! = 479001600 = 0X41BC8CFC00000000 13! = 6227020800 = 0X41F7328CC0000000 14! = 87178291200 = 0X42344C3B28000000 15! = 1307674368000 = 0X4273077775800000 16! = 20922789888000 = 0X42B3077775800000 17! = 355687428096000 = 0X42F437EEECD80000 18! = 6402373705728000 = 0X4336BEECCA730000 19! = 121645100408832000 = 0X437B02B930689000 20! = 2432902008176640000 = 0X43C0E1B3BE415A00 21! = 51090942171709440000 = 0X4406283BE9B5C620 22! = 1124000727777607700000 = 0X444E77526159F06C 23! = 25852016738884978000000 = 0X4495E5C335F8A4CE 24! = 620448401733239410000000 = 0X44E06C52687A7B9A 25! = 1.5511210043330984e+025 = 0X4529A940C33F6120 26! = 4.0329146112660572e+026 = 0X4574D9849EA37EEC 27! = 1.0888869450418352e+028 = 0X45C19787E5D9F316 28! = 3.048883446117138e+029 = 0X460EC92DD23D6965 29! = 8.8417619937397008e+030 = 0X465BE6518687A784 30! = 2.652528598121911e+032 = 0X46AA27EC6E1F2D0E 31! = 8.2228386541779236e+033 = 0X46F956AD0AAE33A5 32! = 2.6313083693369355e+035 = 0X474956AD0AAE33A5 33! = 8.6833176188118895e+036 = 0X479A21627303A544 34! = 2.9523279903960408e+038 = 0X47EBC3789A33DF94 35! = 1.0333147966386144e+040 = 0X483E5DCBE8A8BC8B 36! = 3.7199332678990133e+041 = 0X489114C2B2DEEA10 37! = 1.3763753091226346e+043 = 0X48E3C0011ED1BEA1 38! = 5.2302261746660104e+044 = 0X493774015499125E 39! = 2.0397882081197447e+046 = 0X498C95619F1A8E65 40! = 8.1591528324789801e+047 = 0X49E1DD5D03709900 41! = 3.3452526613163798e+049 = 0X4A36E39F2C684404 42! = 1.4050061177528801e+051 = 0X4A8E0AC0EA48D949 43! = 6.0415263063373845e+052 = 0X4AE42F399D68F1FD 44! = 2.6582715747884495e+054 = 0X4B3BC0EF38704CBD 45! = 1.1962222086548021e+056 = 0X4B9383A833AEF5F4 46! = 5.5026221598120892e+057 = 0X4BEC0D41CA4B818E 47! = 2.5862324151116827e+059 = 0X4C4499BC508F7326 48! = 1.2413915592536068e+061 = 0X4C9EE69A78D72CB3 49! = 6.0828186403426789e+062 = 0X4CF7A88E4484BE3F 50! = 3.0414093201713376e+064 = 0X4D527BAF2587B49E 51! = 1.5511187532873816e+066 = 0X4DAD751F23D047D9 52! = 8.0658175170943901e+067 = 0X4E07EF294D193A65 53! = 4.274883284060024e+069 = 0X4E63D20E33D8E458 54! = 2.3084369733924128e+071 = 0X4EC0B93BFBBF00AA 55! = 1.2696403353658264e+073 = 0X4F1CBE5F18B04920 56! = 7.1099858780486318e+074 = 0X4F792693359A4000 57! = 4.0526919504877227e+076 = 0X4FD6665B1BBD6104 58! = 2.3505613312828789e+078 = 0X50344CC291239FEB 59! = 1.3868311854568981e+080 = 0X5092B6C35DCCD76B 60! = 8.3209871127413899e+081 = 0X50F18B5727F009F5 61! = 5.0758021387722462e+083 = 0X5150B8CF1210C97C 62! = 3.1469973260387939e+085 = 0X51B0330899804332 63! = 1.9826083154044396e+087 = 0X520FE478EE348448 64! = 1.2688693218588414e+089 = 0X526FE478EE348448 65! = 8.2476505920824715e+090 = 0X52D0320568F6AB2E 66! = 5.4434493907744319e+092 = 0X5330B395943E6088 67! = 3.6471110918188705e+094 = 0X53917C0097314D10 68! = 2.4800355424368301e+096 = 0X53F293C0A0A461DD 69! = 1.7112245242814127e+098 = 0X5454074BAD313982 70! = 1.1978571669969892e+100 = 0X54B5E7FAC56DD6E8 71! = 8.5047858856786242e+101 = 0X55184D5A3305DA6A 72! = 6.1234458376886116e+103 = 0X557B5705796695BA 73! = 4.4701154615126859e+105 = 0X55DF2F423E7902C7 74! = 3.3078854415193869e+107 = 0X564207524C1DF59A 75! = 2.4809140811395404e+109 = 0X56A5209471331BD1 76! = 1.8854947016660506e+111 = 0X570916B0466CB108 77! = 1.4518309202828591e+113 = 0X576E2F4C14BAC4FE 78! = 1.1324281178206295e+115 = 0X57D264D25CA1D008 79! = 8.9461821307829799e+116 = 0X5836B473AA57BCCF 80! = 7.1569457046263797e+118 = 0X589C619094EDABFE 81! = 5.797126020747369e+120 = 0X5901F5BD7E3E66D8 82! = 4.7536433370128435e+122 = 0X596702DAC9BFF3C6 83! = 3.9455239697206602e+124 = 0X59CDD7B3BDA4F025 84! = 3.3142401345653538e+126 = 0X5A33958DF4743D97 85! = 2.8171041143805494e+128 = 0X5A9A02A088AA61C9 86! = 2.4227095383672744e+130 = 0X5B0179C3DBD279B7 87! = 2.1077572983795269e+132 = 0X5B67C1863ED21D6F 88! = 1.854826422573984e+134 = 0X5BD0550C4B30743D 89! = 1.6507955160908465e+136 = 0X5C36B645188F61A8 90! = 1.4857159644817605e+138 = 0X5C9FF0512A89A14C 91! = 1.3520015276784033e+140 = 0X5D06B4D9B43DD8B2 92! = 1.2438414054641305e+142 = 0X5D7051FC798C73BE 93! = 1.156772507081641e+144 = 0X5DD7B722E0A0182E 94! = 1.0873661566567426e+146 = 0X5E416A7D9CF591C2 95! = 1.0329978488239061e+148 = 0X5EA9DA1274FC8460 96! = 9.916779348709491e+149 = 0X5F13638DD7BD6344 97! = 9.6192759682482155e+151 = 0X5F7D62E2FAFB0A7B 98! = 9.426890448883248e+153 = 0X5FE67FB5C8283404 99! = 9.3326215443944153e+155 = 0X605166C698CF183B 100! = 9.3326215443944175e+157 = 0X60BB30964EC395DE 101! = 9.4259477598383599e+159 = 0X612574569A265440 102! = 9.6144667150351251e+161 = 0X619118B502D68B22 103! = 9.9029007164861779e+163 = 0X61FB83C3509147EA 104! = 1.0299016745145631e+166 = 0X62665B0EB1760A72 105! = 1.0813967582402912e+168 = 0X62D256B20D92D491 106! = 1.1462805637347086e+170 = 0X633E5F96E67B3010 107! = 1.2265202031961373e+172 = 0X63A963E824AAFA28 108! = 1.324641819451829e+174 = 0X64156C4BDEF04315 109! = 1.4438595832024942e+176 = 0X64823E389BD89922 110! = 1.5882455415227423e+178 = 0X64EF5AF14BDC472B 111! = 1.7629525510902457e+180 = 0X655B30DD3FC905BF 112! = 1.9745068572210749e+182 = 0X65C7CAC197CFE506 113! = 2.2311927486598138e+184 = 0X663500FEE805882D 114! = 2.5435597334721862e+186 = 0X66A2B4E306A4ED45 115! = 2.9250936934930141e+188 = 0X6710CE83F7F82D2C 116! = 3.3931086844518989e+190 = 0X677E764F3171D1E6 117! = 3.96993716080872e+192 = 0X67EBD824633209D9 118! = 4.6845258497542896e+194 = 0X6859AB418B722114 119! = 5.5745857612076058e+196 = 0X68C7DD36EFA41AC2 120! = 6.6895029134491346e+198 = 0X69365F6380A9D91D 121! = 8.0942985252734441e+200 = 0X69A5262C0FA08F37 122! = 9.8750442008336011e+202 = 0X6A142861FEE50880 123! = 1.2146304367025332e+205 = 0X6A835ECE2AF0162C 124! = 1.5061417415111409e+207 = 0X6AF2C3D7B998957A 125! = 1.8826771768889261e+209 = 0X6B625340AB3F01F9 126! = 2.3721732428800483e+211 = 0X6BD209F3A89205F4 127! = 3.0126600184576624e+213 = 0X6C41E5DFC140E1EA 128! = 3.8562048236258079e+215 = 0X6CB1E5DFC140E1EA 129! = 4.9745042224772875e+217 = 0X6D2209AB80C363A9 130! = 6.4668554892204729e+219 = 0X6D9251D22EC67137 131! = 8.4715806908788126e+221 = 0X6E02BFBD1BDF17DA 132! = 1.1182486511960037e+224 = 0X6E7355BB04BE109B 133! = 1.4872707060906847e+226 = 0X6EE4171452ED7D40 134! = 1.9929427461615201e+228 = 0X6F55082946D09F27 135! = 2.6904727073180491e+230 = 0X6FC62E9B88B007D4 136! = 3.6590428819525483e+232 = 0X70379185413B0854 137! = 5.0128887482749884e+234 = 0X70A939C09FD12EE6 138! = 6.9177864726194823e+236 = 0X711B3243AC4D868E 139! = 9.6157231969410894e+238 = 0X718D88957D1C3026 140! = 1.3462012475717523e+241 = 0X720026B1C06B6A54 141! = 1.8981437590761713e+243 = 0X7271CA9FCDF65322 142! = 2.6953641378881633e+245 = 0X72E3BCC9487D443A 143! = 3.8543707171800694e+247 = 0X73560CE8DEFBF232 144! = 5.5502938327393076e+249 = 0X73C8CE85FADB7082 145! = 8.0479260574719887e+251 = 0X743C19F3C62C956C 146! = 1.1749972043909107e+254 = 0X74B006CD07056D39 147! = 1.7272458904546399e+256 = 0X752267CF76103B73 148! = 2.5563239178728637e+258 = 0X75954807E082C4B5 149! = 3.8089226376305687e+260 = 0X7608C5D92B5838FE 150! = 5.7133839564458575e+262 = 0X767D07DA7ECB62D0 151! = 8.6272097742332436e+264 = 0X76F11FA1E0C9F748 152! = 1.3113358856834527e+267 = 0X776455903AEFD5A4 153! = 2.0063439050956838e+269 = 0X77D84E466672AD62 154! = 3.0897696138473515e+271 = 0X784D3E2CB341F896 155! = 4.7891429014633931e+273 = 0X78C1B4A51088F181 156! = 7.4710629262828918e+275 = 0X793594292C26E654 157! = 1.1729568794264134e+278 = 0X79AA77BA8027B67F 158! = 1.8532718694937346e+280 = 0X7A2055E51B1882A6 159! = 2.9467022724950358e+282 = 0X7A944AB297A87246 160! = 4.7147236359920609e+284 = 0X7B095D5F3D928EDD 161! = 7.5907050539472232e+286 = 0X7B7FE771CB7257B8 162! = 1.2296942187394494e+289 = 0X7BF4307602BE5B7F 163! = 2.0044015765453032e+291 = 0X7C69B5B6477E6886 164! = 3.2872185855342987e+293 = 0X7CE07868C5CCFAF8 165! = 5.4239106661315832e+295 = 0X7D553B370EFA3B79 166! = 9.0036917057784341e+297 = 0X7DCB88CB676C8526 167! = 1.5036165148649983e+300 = 0X7E41F63CB077CADB 168! = 2.5260757449731988e+302 = 0X7EB7932FA79D3A44 169! = 4.2690680090047056e+304 = 0X7F2F2054EB4D96ED 170! = 7.257415615308004e+306 = 0X7FA4AB786441863D 171! = 1.#INF = 0X7FF0000000000000 ..... FAUX .....
Factorielles calculées récursivement
uint32_t RecFact32(uint32_t N) {return (N<=1)?1:N*RecFact32(N-1);}
uint64_t RecFact64(uint32_t N) {return (N<=1)?1:N*RecFact64(N-1);}
float RecFactF(uint32_t N) {return (N<=1)?1:N*RecFactF(N-1);}
double RecFactD(uint32_t N) {return (N<=1)?1:N*RecFactD(N-1);}
Les résultats et limitations correspondent aux quatre codes traités plus haut.
Le temps de calcul est peut-être très légèrement plus grand.
Comme il est impossible de dépasser N = 170, l'utilisation de la mémoire (stack) reste raisonnable.
Factorielles précalculées
Une troisième manière, souvent oubliée par les plus grands auteurs, est de calculer à l'avance un array qui contient les factorielles utilisées:
uint32_t fact32[13]={1,1};
for (uint32_t N=2; N<=12; ++N) fact32[N]=N*fact32[N-1];
uint64_t fact64[21]={1,1};
for (uint32_t N=2; N<=20; ++N) fact64[N]=N*fact64[N-1];
float factF[35]={1,1};
for (uint32_t N=2; N<=34; ++N) factF[N]=N*factF[N-1];
double factD[171]={1,1};
for (uint32_t N=2; N<=170; ++N) factD[N]=N*factD[N-1];
Le petit test de comparaison fait à la fin dans Main.cpp montre clairement qu'il est fortement recommandé d'utiliser ce procédé, surtout lorsque le temps de calcul est important.
Fonction: somme = 5.62183143603746e+196, temps = 8752 ms
Array: somme = 5.62183143603746e+196, temps = 78 ms
Limites
En observant les résultats obtenus par Main.cpp, on peut indiquer les limites d'utilisation suivantes:
- Entier positif 32 bits: 0! à 12!
- Entier positif 64 bits: 0! à 20!
- Nombres en virgule flottante 32 bits (float): 0! à 34! (### 13! = 6227020800)
- Nombres en virgule flottante 64 bits (double): 0! à 170! (### 21! = 51090942171709440000)
###: Au dessus de ce nombre, les résultats ne sont plus "mathématiquement" précis car la mantisse du format utilisé est "trop petite".
Par contre, au sens "virgule flottante", ces valeurs sont bonnes et "précises".
Bonne lecture.
Codes Sources
A voir également
- La fonction factorielle: Fact(N) = N!
- Fonction factorielle python - Forum Python
- Dérivée factorielle - Forum C
- Remise en fonction - Forum C / C++ / C++.NET
- Sub ou fonction non définie - Forum VB.NET
- Fonction pow en c ✓ - Forum C
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.