* faster log factorials
@ 2003-04-28 4:57 James Theiler
2003-05-10 19:09 ` Brian Gough
2003-05-10 19:29 ` Brian Gough
0 siblings, 2 replies; 9+ messages in thread
From: James Theiler @ 2003-04-28 4:57 UTC (permalink / raw)
To: gsl-discuss
[-- Attachment #1: Type: TEXT/PLAIN, Size: 3780 bytes --]
hello,
This message is mostly for Gerard Jungman, since it relates to his
specfunc/gamma.c, but others may have worthwhile opinions as well.
While looking at another part of GSL (randist/binomial.c -- I'll
have more to say about that in a later email), I realized that the
function gsl_sf_lnfact() [this computes log(n!)] could be speeded up
for small arguments by pre-computing the logarithms. For small
arguments, the existing code already pre-computes real (double) and
integer (long) values, and maintains a static array of those values.
So including pre-computed logarithms is not a major design change.
For the current gsl_sf_lnfact() call, it takes the logarithm of the
precomputed value:
result->val = log(fact_table[n].f);
I altered the fact_table struct array to include an extra field,
double lnf; and then altered the array initialization to include the
logarithm of those first values. So now the above line is replaced by
result->val = fact_table[n].lnf;
This is about 3x faster on my machine than taking the log. (I was
hoping for about 12x improvement, based on initial experiments with a
fact_table array built directly into my test code, but there appears
to be a fair bit of overhead involved with going through the GSL -- I'm
guessing it has to do with the computation of the error estimates, which
are computed even if they are not used. Error estimates are very worthwhile
things to have around, so we should think hard before we go in and try to
optimize them away.)
While I was at it, I also modified the doub_fact_table in a similar way,
and the gsl_sf_lndoublefact() routine. [This returns log(n!!)]
I'll attach the diff file (I tried attaching the full gamma.c, but
the mail daemon bounced it because it was too big); I'll happily
send the full gamma.c to anybody who asks for it. Meanwhile, I
have a few more general questions:
1. I used a perl script to rebuild the precomputed fact_table[] and
doub_fact_table[]. Should this perl script be part of GSL? (Mark,
you'll be relieved to know it's not part of the build script!)
2. For the logarithms, we could easily extend the array well beyond the
current bound of 170. The cost is a large static array as part of GSL,
and the question is: how large? By the way, we could save some space
by making the integer, double, and log tables separate. One of length
12, one of length 171, and one of substantially larger length?
3. Speaking of saving space, do we really need the 'n' component of
the fact_table struct? It isn't used in gamma.c as far as I can
tell. To be sure, that makes it easier on the eye to cross-check
with other tables that the values are correct, but we could just
as well do something like
static double fact_table_d[] = {
/* 0 */ 1.0,
/* 1 */ 1.0,
/* 2 */ 2.0,
/* 3 */ 6.0,
...etc
}
4. Also, a trick for computing the table size at compile time, so that
you don't have to worry about simultaneously updating the
'#define FACT_TABLE_MAX' and the table itself, is to use -- after
the actual initialization such as that above for fact_table_d, a
define statement along the lines of
#define FACT_TABLE_D_SIZE (sizeof(fact_table_d)/sizeof(double))
#define FACT_TABLE_D_MAX (FACT_TABLE_SIZE-1)
Sometimes, I've also seen sizeof(fact_table_d[0]) in place of
sizeof(double); one less place to hardcode the table's type.
regards,
jt
---------------------------------------------
James Theiler jt@lanl.gov
MS-B244, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----
[-- Attachment #2: diff file --]
[-- Type: TEXT/PLAIN, Size: 71024 bytes --]
41d40
<
44,250c43,247
< static struct {int n; double f; long i; } fact_table[FACT_TABLE_SIZE] = {
< { 0, 1.0, 1L },
< { 1, 1.0, 1L },
< { 2, 2.0, 2L },
< { 3, 6.0, 6L },
< { 4, 24.0, 24L },
< { 5, 120.0, 120L },
< { 6, 720.0, 720L },
< { 7, 5040.0, 5040L },
< { 8, 40320.0, 40320L },
<
< { 9, 362880.0, 362880L },
< { 10, 3628800.0, 3628800L },
< { 11, 39916800.0, 39916800L },
< { 12, 479001600.0, 479001600L },
<
< { 13, 6227020800.0, 0 },
< { 14, 87178291200.0, 0 },
< { 15, 1307674368000.0, 0 },
< { 16, 20922789888000.0, 0 },
< { 17, 355687428096000.0, 0 },
< { 18, 6402373705728000.0, 0 },
< { 19, 121645100408832000.0, 0 },
< { 20, 2432902008176640000.0, 0 },
< { 21, 51090942171709440000.0, 0 },
< { 22, 1124000727777607680000.0, 0 },
< { 23, 25852016738884976640000.0, 0 },
< { 24, 620448401733239439360000.0, 0 },
< { 25, 15511210043330985984000000.0, 0 },
< { 26, 403291461126605635584000000.0, 0 },
< { 27, 10888869450418352160768000000.0, 0 },
< { 28, 304888344611713860501504000000.0, 0 },
< { 29, 8841761993739701954543616000000.0, 0 },
< { 30, 265252859812191058636308480000000.0, 0 },
< { 31, 8222838654177922817725562880000000.0, 0 },
< { 32, 263130836933693530167218012160000000.0, 0 },
< { 33, 8683317618811886495518194401280000000.0, 0 },
< { 34, 2.95232799039604140847618609644e38, 0 },
< { 35, 1.03331479663861449296666513375e40, 0 },
< { 36, 3.71993326789901217467999448151e41, 0 },
< { 37, 1.37637530912263450463159795816e43, 0 },
< { 38, 5.23022617466601111760007224100e44, 0 },
< { 39, 2.03978820811974433586402817399e46, 0 },
< { 40, 8.15915283247897734345611269600e47, 0 },
< { 41, 3.34525266131638071081700620534e49, 0 },
< { 42, 1.40500611775287989854314260624e51, 0 },
< { 43, 6.04152630633738356373551320685e52, 0 },
< { 44, 2.65827157478844876804362581101e54, 0 },
< { 45, 1.19622220865480194561963161496e56, 0 },
< { 46, 5.50262215981208894985030542880e57, 0 },
< { 47, 2.58623241511168180642964355154e59, 0 },
< { 48, 1.24139155925360726708622890474e61, 0 },
< { 49, 6.08281864034267560872252163321e62, 0 },
< { 50, 3.04140932017133780436126081661e64, 0 },
< { 51, 1.55111875328738228022424301647e66, 0 },
< { 52, 8.06581751709438785716606368564e67, 0 },
< { 53, 4.27488328406002556429801375339e69, 0 },
< { 54, 2.30843697339241380472092742683e71, 0 },
< { 55, 1.26964033536582759259651008476e73, 0 },
< { 56, 7.10998587804863451854045647464e74, 0 },
< { 57, 4.05269195048772167556806019054e76, 0 },
< { 58, 2.35056133128287857182947491052e78, 0 },
< { 59, 1.38683118545689835737939019720e80, 0 },
< { 60, 8.32098711274139014427634118320e81, 0 },
< { 61, 5.07580213877224798800856812177e83, 0 },
< { 62, 3.14699732603879375256531223550e85, 0 },
< { 63, 1.982608315404440064116146708360e87, 0 },
< { 64, 1.268869321858841641034333893350e89, 0 },
< { 65, 8.247650592082470666723170306800e90, 0 },
< { 66, 5.443449390774430640037292402480e92, 0 },
< { 67, 3.647111091818868528824985909660e94, 0 },
< { 68, 2.480035542436830599600990418570e96, 0 },
< { 69, 1.711224524281413113724683388810e98, 0 },
< { 70, 1.197857166996989179607278372170e100, 0 },
< { 71, 8.504785885678623175211676442400e101, 0 },
< { 72, 6.123445837688608686152407038530e103, 0 },
< { 73, 4.470115461512684340891257138130e105, 0 },
< { 74, 3.307885441519386412259530282210e107, 0 },
< { 75, 2.480914081139539809194647711660e109, 0 },
< { 76, 1.885494701666050254987932260860e111, 0 },
< { 77, 1.451830920282858696340707840860e113, 0 },
< { 78, 1.132428117820629783145752115870e115, 0 },
< { 79, 8.946182130782975286851441715400e116, 0 },
< { 80, 7.156945704626380229481153372320e118, 0 },
< { 81, 5.797126020747367985879734231580e120, 0 },
< { 82, 4.753643337012841748421382069890e122, 0 },
< { 83, 3.945523969720658651189747118010e124, 0 },
< { 84, 3.314240134565353266999387579130e126, 0 },
< { 85, 2.817104114380550276949479442260e128, 0 },
< { 86, 2.422709538367273238176552320340e130, 0 },
< { 87, 2.107757298379527717213600518700e132, 0 },
< { 88, 1.854826422573984391147968456460e134, 0 },
< { 89, 1.650795516090846108121691926250e136, 0 },
< { 90, 1.485715964481761497309522733620e138, 0 },
< { 91, 1.352001527678402962551665687590e140, 0 },
< { 92, 1.243841405464130725547532432590e142, 0 },
< { 93, 1.156772507081641574759205162310e144, 0 },
< { 94, 1.087366156656743080273652852570e146, 0 },
< { 95, 1.032997848823905926259970209940e148, 0 },
< { 96, 9.916779348709496892095714015400e149, 0 },
< { 97, 9.619275968248211985332842594960e151, 0 },
< { 98, 9.426890448883247745626185743100e153, 0 },
< { 99, 9.332621544394415268169923885600e155, 0 },
< { 100, 9.33262154439441526816992388563e157, 0 },
< { 101, 9.42594775983835942085162312450e159, 0 },
< { 102, 9.61446671503512660926865558700e161, 0 },
< { 103, 9.90290071648618040754671525458e163, 0 },
< { 104, 1.02990167451456276238485838648e166, 0 },
< { 105, 1.08139675824029090050410130580e168, 0 },
< { 106, 1.146280563734708354534347384148e170, 0 },
< { 107, 1.226520203196137939351751701040e172, 0 },
< { 108, 1.324641819451828974499891837120e174, 0 },
< { 109, 1.443859583202493582204882102460e176, 0 },
< { 110, 1.588245541522742940425370312710e178, 0 },
< { 111, 1.762952551090244663872161047110e180, 0 },
< { 112, 1.974506857221074023536820372760e182, 0 },
< { 113, 2.231192748659813646596607021220e184, 0 },
< { 114, 2.543559733472187557120132004190e186, 0 },
< { 115, 2.925093693493015690688151804820e188, 0 },
< { 116, 3.393108684451898201198256093590e190, 0 },
< { 117, 3.96993716080872089540195962950e192, 0 },
< { 118, 4.68452584975429065657431236281e194, 0 },
< { 119, 5.57458576120760588132343171174e196, 0 },
< { 120, 6.68950291344912705758811805409e198, 0 },
< { 121, 8.09429852527344373968162284545e200, 0 },
< { 122, 9.87504420083360136241157987140e202, 0 },
< { 123, 1.21463043670253296757662432419e205, 0 },
< { 124, 1.50614174151114087979501416199e207, 0 },
< { 125, 1.88267717688892609974376770249e209, 0 },
< { 126, 2.37217324288004688567714730514e211, 0 },
< { 127, 3.01266001845765954480997707753e213, 0 },
< { 128, 3.85620482362580421735677065923e215, 0 },
< { 129, 4.97450422247728744039023415041e217, 0 },
< { 130, 6.46685548922047367250730439554e219, 0 },
< { 131, 8.47158069087882051098456875820e221, 0 },
< { 132, 1.11824865119600430744996307608e224, 0 },
< { 133, 1.48727070609068572890845089118e226, 0 },
< { 134, 1.99294274616151887673732419418e228, 0 },
< { 135, 2.69047270731805048359538766215e230, 0 },
< { 136, 3.65904288195254865768972722052e232, 0 },
< { 137, 5.01288874827499166103492629211e234, 0 },
< { 138, 6.91778647261948849222819828311e236, 0 },
< { 139, 9.61572319694108900419719561353e238, 0 },
< { 140, 1.34620124757175246058760738589e241, 0 },
< { 141, 1.89814375907617096942852641411e243, 0 },
< { 142, 2.69536413788816277658850750804e245, 0 },
< { 143, 3.85437071718007277052156573649e247, 0 },
< { 144, 5.55029383273930478955105466055e249, 0 },
< { 145, 8.04792605747199194484902925780e251, 0 },
< { 146, 1.17499720439091082394795827164e254, 0 },
< { 147, 1.72724589045463891120349865931e256, 0 },
< { 148, 2.55632391787286558858117801578e258, 0 },
< { 149, 3.80892263763056972698595524351e260, 0 },
< { 150, 5.71338395644585459047893286526e262, 0 },
< { 151, 8.62720977423324043162318862650e264, 0 },
< { 152, 1.31133588568345254560672467123e267, 0 },
< { 153, 2.00634390509568239477828874699e269, 0 },
< { 154, 3.08976961384735088795856467036e271, 0 },
< { 155, 4.78914290146339387633577523906e273, 0 },
< { 156, 7.47106292628289444708380937294e275, 0 },
< { 157, 1.17295687942641442819215807155e278, 0 },
< { 158, 1.85327186949373479654360975305e280, 0 },
< { 159, 2.94670227249503832650433950735e282, 0 },
< { 160, 4.71472363599206132240694321176e284, 0 },
< { 161, 7.59070505394721872907517857094e286, 0 },
< { 162, 1.22969421873944943411017892849e289, 0 },
< { 163, 2.00440157654530257759959165344e291, 0 },
< { 164, 3.28721858553429622726333031164e293, 0 },
< { 165, 5.42391066613158877498449501421e295, 0 },
< { 166, 9.00369170577843736647426172359e297, 0 },
< { 167, 1.50361651486499904020120170784e300, 0 },
< { 168, 2.52607574497319838753801886917e302, 0 },
< { 169, 4.26906800900470527493925188890e304, 0 },
< { 170, 7.25741561530799896739672821113e306, 0 },
<
< /*
< { 171, 1.24101807021766782342484052410e309, 0 },
< { 172, 2.13455108077438865629072570146e311, 0 },
< { 173, 3.69277336973969237538295546352e313, 0 },
< { 174, 6.42542566334706473316634250653e315, 0 },
< { 175, 1.12444949108573632830410993864e318, 0 },
< { 176, 1.97903110431089593781523349201e320, 0 },
< { 177, 3.50288505463028580993296328086e322, 0 },
< { 178, 6.23513539724190874168067463993e324, 0 },
< { 179, 1.11608923610630166476084076055e327, 0 },
< { 180, 2.00896062499134299656951336898e329, 0 },
< { 181, 3.63621873123433082379081919786e331, 0 },
< { 182, 6.61791809084648209929929094011e333, 0 },
< { 183, 1.21107901062490622417177024204e336, 0 },
< { 184, 2.22838537954982745247605724535e338, 0 },
< { 185, 4.12251295216718078708070590390e340, 0 },
< { 186, 7.66787409103095626397011298130e342, 0 },
< { 187, 1.43389245502278882136241112750e345, 0 },
< { 188, 2.69571781544284298416133291969e347, 0 },
< { 189, 5.09490667118697324006491921822e349, 0 },
< { 190, 9.68032267525524915612334651460e351, 0 },
< { 191, 1.84894163097375258881955918429e354, 0 },
< { 192, 3.54996793146960497053355363384e356, 0 },
< { 193, 6.85143810773633759312975851330e358, 0 },
< { 194, 1.32917899290084949306717315158e361, 0 },
< { 195, 2.59189903615665651148098764559e363, 0 },
< { 196, 5.08012211086704676250273578535e365, 0 },
< { 197, 1.00078405584080821221303894971e368, 0 },
< { 198, 1.98155243056480026018181712043e370, 0 },
< { 199, 3.94328933682395251776181606966e372, 0 },
< { 200, 7.88657867364790503552363213932e374, 0 }
< */
---
> static struct {int n; double f; long i; double lnf; }
> fact_table[FACT_TABLE_SIZE] = {
> { 0, 1.0, 1L, 0.0000000000000000},
> { 1, 1.0, 1L, 0.0000000000000000},
> { 2, 2.0, 2L, 0.6931471805599453},
> { 3, 6.0, 6L, 1.7917594692280550},
> { 4, 24.0, 24L, 3.1780538303479453},
> { 5, 120.0, 120L, 4.7874917427820458},
> { 6, 720.0, 720L, 6.5792512120101012},
> { 7, 5040.0, 5040L, 8.5251613610654147},
> { 8, 40320.0, 40320L, 10.6046029027452509},
> { 9, 362880.0, 362880L, 12.8018274800814709},
> { 10, 3628800.0, 3628800L, 15.1044125730755177},
> { 11, 39916800.0, 39916800L, 17.5023078458738865},
> { 12, 479001600.0, 479001600L, 19.9872144956618882},
> { 13, 6227020800.0, 0L, 22.5521638531234245},
> { 14, 87178291200.0, 0L, 25.1912211827386834},
> { 15, 1307674368000.0, 0L, 27.8992713838408939},
> { 16, 20922789888000.0, 0L, 30.6718601060806755},
> { 17, 355687428096000.0, 0L, 33.5050734501368908},
> { 18, 6402373705728000.0, 0L, 36.3954452080330526},
> { 19, 121645100408832000.0, 0L, 39.3398841871994946},
> { 20, 2432902008176640000.0, 0L, 42.3356164607534851},
> { 21, 51090942171709440000.0, 0L, 45.3801388984769076},
> { 22, 1124000727777607680000.0, 0L, 48.4711813518352272},
> { 23, 25852016738884976640000.0, 0L, 51.6066755677643769},
> { 24, 620448401733239439360000.0, 0L, 54.7847293981123258},
> { 25, 15511210043330985984000000.0, 0L, 58.0036052229805250},
> { 26, 403291461126605635584000000.0, 0L, 61.2617017610020085},
> { 27, 10888869450418352160768000000.0, 0L, 64.5575386270063376},
> { 28, 304888344611713860501504000000.0, 0L, 67.8897431371815401},
> { 29, 8841761993739701954543616000000.0, 0L, 71.2570389671680147},
> { 30, 265252859812191058636308480000000.0, 0L, 74.6582363488301723},
> { 31, 8222838654177922817725562880000000.0, 0L, 78.0922235533153213},
> { 32, 263130836933693530167218012160000000.0, 0L, 81.5579594561150429},
> { 33, 8683317618811886495518194401280000000.0, 0L, 85.0544670175815298},
> { 34, 2.95232799039604140847618609644e38, 0L, 88.5808275421976958},
> { 35, 1.03331479663861449296666513375e40, 0L, 92.1361756036871071},
> { 36, 3.71993326789901217467999448151e41, 0L, 95.7196945421432162},
> { 37, 1.37637530912263450463159795816e43, 0L, 99.3306124547874418},
> { 38, 5.23022617466601111760007224100e44, 0L, 102.9681986145138239},
> { 39, 2.03978820811974433586402817399e46, 0L, 106.6317602606434747},
> { 40, 8.15915283247897734345611269596e47, 0L, 110.3206397147574052},
> { 41, 3.34525266131638071081700620534e49, 0L, 114.0342117814617069},
> { 42, 1.40500611775287989854314260624e51, 0L, 117.7718813997450695},
> { 43, 6.04152630633738356373551320685e52, 0L, 121.5330815154386386},
> { 44, 2.65827157478844876804362581101e54, 0L, 125.3172711493568983},
> { 45, 1.19622220865480194561963161496e56, 0L, 129.1239336391272161},
> { 46, 5.50262215981208894985030542880e57, 0L, 132.9525750356163201},
> { 47, 2.58623241511168180642964355154e59, 0L, 136.8027226373263829},
> { 48, 1.24139155925360726708622890474e61, 0L, 140.6739236482342790},
> { 49, 6.08281864034267560872252163321e62, 0L, 144.5657439463448952},
> { 50, 3.04140932017133780436126081661e64, 0L, 148.4777669517730487},
> { 51, 1.55111875328738228022424301647e66, 0L, 152.4095925844973749},
> { 52, 8.06581751709438785716606368564e67, 0L, 156.3608363030787984},
> { 53, 4.27488328406002556429801375339e69, 0L, 160.3311282166309297},
> { 54, 2.30843697339241380472092742683e71, 0L, 164.3201122631951989},
> { 55, 1.26964033536582759259651008476e73, 0L, 168.3274454484276816},
> { 56, 7.10998587804863451854045647464e74, 0L, 172.3527971391628171},
> { 57, 4.05269195048772167556806019054e76, 0L, 176.3958484069973736},
> { 58, 2.35056133128287857182947491052e78, 0L, 180.4562914175437811},
> { 59, 1.38683118545689835737939019720e80, 0L, 184.5338288614495070},
> { 60, 8.32098711274139014427634118322e81, 0L, 188.6281734236715977},
> { 61, 5.07580213877224798800856812177e83, 0L, 192.7390472878448975},
> { 62, 3.14699732603879375256531223550e85, 0L, 196.8661816728899794},
> { 63, 1.98260831540444006411614670836e87, 0L, 201.0093163992815164},
> { 64, 1.26886932185884164103433389335e89, 0L, 205.1681994826411994},
> { 65, 8.24765059208247066672317030679e90, 0L, 209.3425867525368460},
> { 66, 5.44344939077443064003729240248e92, 0L, 213.5322414945632659},
> { 67, 3.64711109181886852882498590966e94, 0L, 217.7369341139542200},
> { 68, 2.48003554243683059960099041857e96, 0L, 221.9564418191303332},
> { 69, 1.71122452428141311372468338881e98, 0L, 226.1905483237275973},
> { 70, 1.19785716699698917960727837217e100, 0L, 230.4390435657769558},
> { 71, 8.50478588567862317521167644240e101, 0L, 234.7017234428182633},
> { 72, 6.12344583768860868615240703853e103, 0L, 238.9783895618343195},
> { 73, 4.47011546151268434089125713813e105, 0L, 243.2688490029827051},
> { 74, 3.30788544151938641225953028221e107, 0L, 247.5729140961868779},
> { 75, 2.48091408113953980919464771166e109, 0L, 251.8904022097231916},
> { 76, 1.88549470166605025498793226086e111, 0L, 256.2211355500095351},
> { 77, 1.45183092028285869634070784086e113, 0L, 260.5649409718632228},
> { 78, 1.13242811782062978314575211587e115, 0L, 264.9216497985528349},
> { 79, 8.94618213078297528685144171540e116, 0L, 269.2910976510198680},
> { 80, 7.15694570462638022948115337232e118, 0L, 273.6731242856937456},
> { 81, 5.79712602074736798587973423158e120, 0L, 278.0675734403661750},
> { 82, 4.75364333701284174842138206989e122, 0L, 282.4742926876304523},
> { 83, 3.94552396972065865118974711801e124, 0L, 286.8931332954270488},
> { 84, 3.31424013456535326699938757913e126, 0L, 291.3239500942703444},
> { 85, 2.81710411438055027694947944226e128, 0L, 295.7666013507606522},
> { 86, 2.42270953836727323817655232034e130, 0L, 300.2209486470141542},
> { 87, 2.10775729837952771721360051870e132, 0L, 304.6868567656687219},
> { 88, 1.85482642257398439114796845646e134, 0L, 309.1641935801469572},
> { 89, 1.65079551609084610812169192625e136, 0L, 313.6528299498791057},
> { 90, 1.48571596448176149730952273362e138, 0L, 318.1526396202093565},
> { 91, 1.35200152767840296255166568759e140, 0L, 322.6634991267262080},
> { 92, 1.24384140546413072554753243259e142, 0L, 327.1852877037752592},
> { 93, 1.15677250708164157475920516231e144, 0L, 331.7178871969285296},
> { 94, 1.08736615665674308027365285257e146, 0L, 336.2611819791985113},
> { 95, 1.03299784882390592625997020994e148, 0L, 340.8150588707990778},
> { 96, 9.91677934870949689209571401542e149, 0L, 345.3794070622669210},
> { 97, 9.61927596824821198533284259496e151, 0L, 349.9541180407703109},
> { 98, 9.42689044888324774562618574306e153, 0L, 354.5390855194409028},
> { 99, 9.33262154439441526816992388563e155, 0L, 359.1342053695755112},
> { 100, 9.33262154439441526816992388563e157, 0L, 363.7393755555635835},
> { 101, 9.42594775983835942085162312448e159, 0L, 368.3544960724048565},
> { 102, 9.61446671503512660926865558697e161, 0L, 372.9794688856891298},
> { 103, 9.90290071648618040754671525458e163, 0L, 377.6141978739187834},
> { 104, 1.02990167451456276238485838648e166, 0L, 382.2585887730601826},
> { 105, 1.08139675824029090050410130580e168, 0L, 386.9125491232177296},
> { 106, 1.14628056373470835453434738415e170, 0L, 391.5759882173297797},
> { 107, 1.22652020319613793935175170104e172, 0L, 396.2488170517916615},
> { 108, 1.32464181945182897449989183712e174, 0L, 400.9309482789158778},
> { 109, 1.44385958320249358220488210246e176, 0L, 405.6222961611450160},
> { 110, 1.58824554152274294042537031271e178, 0L, 410.3227765269374459},
> { 111, 1.76295255109024466387216104711e180, 0L, 415.0323067282498073},
> { 112, 1.97450685722107402353682037276e182, 0L, 419.7508055995448899},
> { 113, 2.23119274865981364659660702122e184, 0L, 424.4781934182572058},
> { 114, 2.54355973347218755712013200419e186, 0L, 429.2143918666516811},
> { 115, 2.92509369349301569068815180482e188, 0L, 433.9593239950149268},
> { 116, 3.39310868445189820119825609359e190, 0L, 438.7129141861212815},
> { 117, 3.96993716080872089540195962950e192, 0L, 443.4750881209190538},
> { 118, 4.68452584975429065657431236281e194, 0L, 448.2457727453847269},
> { 119, 5.57458576120760588132343171174e196, 0L, 453.0248962384962397},
> { 120, 6.68950291344912705758811805409e198, 0L, 457.8123879812782775},
> { 121, 8.09429852527344373968162284545e200, 0L, 462.6081785268750082},
> { 122, 9.87504420083360136241157987145e202, 0L, 467.4121995716082552},
> { 123, 1.21463043670253296757662432419e205, 0L, 472.2243839269806926},
> { 124, 1.50614174151114087979501416199e207, 0L, 477.0446654925857501},
> { 125, 1.88267717688892609974376770249e209, 0L, 481.8729792298880739},
> { 126, 2.37217324288004688567714730514e211, 0L, 486.7092611368395296},
> { 127, 3.01266001845765954480997707753e213, 0L, 491.5534482232981190},
> { 128, 3.85620482362580421735677065923e215, 0L, 496.4054784872177493},
> { 129, 4.97450422247728744039023415041e217, 0L, 501.2652908915794114},
> { 130, 6.46685548922047367250730439554e219, 0L, 506.1328253420350052},
> { 131, 8.47158069087882051098456875815e221, 0L, 511.0080226652361830},
> { 132, 1.11824865119600430744996307608e224, 0L, 515.8908245878225216},
> { 133, 1.48727070609068572890845089118e226, 0L, 520.7811737160442362},
> { 134, 1.99294274616151887673732419418e228, 0L, 525.6790135159951660},
> { 135, 2.69047270731805048359538766215e230, 0L, 530.5842882944335770},
> { 136, 3.65904288195254865768972722052e232, 0L, 535.4969431801696373},
> { 137, 5.01288874827499166103492629211e234, 0L, 540.4169241059977367},
> { 138, 6.91778647261948849222819828311e236, 0L, 545.3441777911549480},
> { 139, 9.61572319694108900419719561353e238, 0L, 550.2786517242856235},
> { 140, 1.34620124757175246058760738589e241, 0L, 555.2202941468949575},
> { 141, 1.89814375907617096942852641411e243, 0L, 560.1690540372730993},
> { 142, 2.69536413788816277658850750804e245, 0L, 565.1248810948743539},
> { 143, 3.85437071718007277052156573649e247, 0L, 570.0877257251343053},
> { 144, 5.55029383273930478955105466055e249, 0L, 575.0575390247103087},
> { 145, 8.04792605747199194484902925780e251, 0L, 580.0342727671309149},
> { 146, 1.17499720439091082394795827164e254, 0L, 585.0178793888392192},
> { 147, 1.72724589045463891120349865931e256, 0L, 590.0083119756179713},
> { 148, 2.55632391787286558858117801578e258, 0L, 595.0055242493821197},
> { 149, 3.80892263763056972698595524351e260, 0L, 600.0094705553275389},
> { 150, 5.71338395644585459047893286526e262, 0L, 605.0201058494237714},
> { 151, 8.62720977423324043162318862654e264, 0L, 610.0373856862387356},
> { 152, 1.31133588568345254560672467123e267, 0L, 615.0612662070850547},
> { 153, 2.00634390509568239477828874699e269, 0L, 620.0917041284775451},
> { 154, 3.08976961384735088795856467036e271, 0L, 625.1286567308911799},
> { 155, 4.78914290146339387633577523906e273, 0L, 630.1720818478104320},
> { 156, 7.47106292628289444708380937294e275, 0L, 635.2219378550599913},
> { 157, 1.17295687942641442819215807155e278, 0L, 640.2781836604083310},
> { 158, 1.85327186949373479654360975305e280, 0L, 645.3407786934352544},
> { 159, 2.94670227249503832650433950735e282, 0L, 650.4096828956554646},
> { 160, 4.71472363599206132240694321176e284, 0L, 655.4848567108892894},
> { 161, 7.59070505394721872907517857094e286, 0L, 660.5662610758737401},
> { 162, 1.22969421873944943411017892849e289, 0L, 665.6538574111061735},
> { 163, 2.00440157654530257759959165344e291, 0L, 670.7476076119129402},
> { 164, 3.28721858553429622726333031164e293, 0L, 675.8474740397371079},
> { 165, 5.42391066613158877498449501421e295, 0L, 680.9534195136376411},
> { 166, 9.00369170577843736647426172359e297, 0L, 686.0654073019941279},
> { 167, 1.50361651486499904020120170784e300, 0L, 691.1834011144109127},
> { 168, 2.52607574497319838753801886917e302, 0L, 696.3073650938141554},
> { 169, 4.26906800900470527493925188890e304, 0L, 701.4372638087372707},
> { 170, 7.25741561530799896739672821113e306, 0L, 706.5730622457875825}
> /*
> { 171, 1.24101807021766782342484052410e309, 0L, 711.7147258022902179},
> { 172, 2.13455108077438865629072570146e311, 0L, 716.8622202791036671},
> { 173, 3.69277336973969237538295546352e313, 0L, 722.0155118736014401},
> { 174, 6.42542566334706473316634250653e315, 0L, 727.1745671728159550},
> { 175, 1.12444949108573632830410993864e318, 0L, 732.3393531467394268},
> { 176, 1.97903110431089593781523349201e320, 0L, 737.5098371417775525},
> { 177, 3.50288505463028580993296328086e322, 0L, 742.6859868743513289},
> { 178, 6.23513539724190874168067463993e324, 0L, 747.8677704246433677},
> { 179, 1.11608923610630166476084076055e327, 0L, 753.0551562304841582},
> { 180, 2.00896062499134299656951336898e329, 0L, 758.2481130813744130},
> { 181, 3.63621873123433082379081919786e331, 0L, 763.4466101126402009},
> { 182, 6.61791809084648209929929094011e333, 0L, 768.6506167997169996},
> { 183, 1.21107901062490622417177024204e336, 0L, 773.8601029525584636},
> { 184, 2.22838537954982745247605724535e338, 0L, 779.0750387101674050},
> { 185, 4.12251295216718078708070590390e340, 0L, 784.2953945352456913},
> { 186, 7.66787409103095626397011298126e342, 0L, 789.5211412089588521},
> { 187, 1.43389245502278882136241112750e345, 0L, 794.7522498258134647},
> { 188, 2.69571781544284298416133291969e347, 0L, 799.9886917886434503},
> { 189, 5.09490667118697324006491921822e349, 0L, 805.2304388037031231},
> { 190, 9.68032267525524915612334651462e351, 0L, 810.4774628758635799},
> { 191, 1.84894163097375258881955918429e354, 0L, 815.7297363039101583},
> { 192, 3.54996793146960497053355363384e356, 0L, 820.9872316759378919},
> { 193, 6.85143810773633759312975851331e358, 0L, 826.2499218648428041},
> { 194, 1.32917899290084949306717315158e361, 0L, 831.5177800239060844},
> { 195, 2.59189903615665651148098764559e363, 0L, 836.7907795824697814},
> { 196, 5.08012211086704676250273578535e365, 0L, 842.0688942417002636},
> { 197, 1.00078405584080821221303894971e368, 0L, 847.3520979704383080},
> { 198, 1.98155243056480026018181712043e370, 0L, 852.6403650011328637},
> { 199, 3.94328933682395251776181606966e372, 0L, 857.9336698258573506},
> { 200, 7.88657867364790503552363213932e374, 0L, 863.2319871924054269}
> */
255,558c252,556
< static struct {int n; double f; long i; } doub_fact_table[DOUB_FACT_TABLE_SIZE] = {
< { 0, 1.000000000000000000000000000, 1L },
< { 1, 1.000000000000000000000000000, 1L },
< { 2, 2.000000000000000000000000000, 2L },
< { 3, 3.000000000000000000000000000, 3L },
< { 4, 8.000000000000000000000000000, 8L },
< { 5, 15.00000000000000000000000000, 15L },
< { 6, 48.00000000000000000000000000, 48L },
< { 7, 105.0000000000000000000000000, 105L },
< { 8, 384.0000000000000000000000000, 384L },
< { 9, 945.0000000000000000000000000, 945L },
< { 10, 3840.000000000000000000000000, 3840L },
< { 11, 10395.00000000000000000000000, 10395L },
< { 12, 46080.00000000000000000000000, 46080L },
< { 13, 135135.0000000000000000000000, 135135L },
< { 14, 645120.00000000000000000000000, 645120L },
< { 15, 2.02702500000000000000000000000e6, 2027025L },
< { 16, 1.03219200000000000000000000000e7, 10321920L },
< { 17, 3.4459425000000000000000000000e7, 34459425L },
< { 18, 1.85794560000000000000000000000e8, 185794560L },
< { 19, 6.5472907500000000000000000000e8, 0 },
< { 20, 3.7158912000000000000000000000e9, 0 },
< { 21, 1.37493105750000000000000000000e10, 0 },
< { 22, 8.1749606400000000000000000000e10, 0 },
< { 23, 3.1623414322500000000000000000e11, 0 },
< { 24, 1.96199055360000000000000000000e12, 0 },
< { 25, 7.9058535806250000000000000000e12, 0 },
< { 26, 5.1011754393600000000000000000e13, 0 },
< { 27, 2.13458046676875000000000000000e14, 0 },
< { 28, 1.42832912302080000000000000000e15, 0 },
< { 29, 6.1902833536293750000000000000e15, 0 },
< { 30, 4.2849873690624000000000000000e16, 0 },
< { 31, 1.91898783962510625000000000000e17, 0 },
< { 32, 1.37119595809996800000000000000e18, 0 },
< { 33, 6.3326598707628506250000000000e18, 0 },
< { 34, 4.6620662575398912000000000000e19, 0 },
< { 35, 2.21643095476699771875000000000e20, 0 },
< { 36, 1.67834385271436083200000000000e21, 0 },
< { 37, 8.2007945326378915593750000000e21, 0 },
< { 38, 6.3777066403145711616000000000e22, 0 },
< { 39, 3.1983098677287777081562500000e23, 0 },
< { 40, 2.55108265612582846464000000000e24, 0 },
< { 41, 1.31130704576879886034406250000e25, 0 },
< { 42, 1.07145471557284795514880000000e26, 0 },
< { 43, 5.6386202968058350994794687500e26, 0 },
< { 44, 4.7144007485205310026547200000e27, 0 },
< { 45, 2.53737913356262579476576093750e28, 0 },
< { 46, 2.16862434431944426122117120000e29, 0 },
< { 47, 1.19256819277443412353990764062e30, 0 },
< { 48, 1.04093968527333324538616217600e31, 0 },
< { 49, 5.8435841445947272053455474391e31, 0 },
< { 50, 5.2046984263666662269308108800e32, 0 },
< { 51, 2.98022791374331087472622919392e33, 0 },
< { 52, 2.70644318171066643800402165760e34, 0 },
< { 53, 1.57952079428395476360490147278e35, 0 },
< { 54, 1.46147931812375987652217169510e36, 0 },
< { 55, 8.6873643685617511998269581003e36, 0 },
< { 56, 8.1842841814930553085241614926e37, 0 },
< { 57, 4.9517976900801981839013661172e38, 0 },
< { 58, 4.7468848252659720789440136657e39, 0 },
< { 59, 2.92156063714731692850180600912e40, 0 },
< { 60, 2.84813089515958324736640819942e41, 0 },
< { 61, 1.78215198865986332638610166557e42, 0 },
< { 62, 1.76584115499894161336717308364e43, 0 },
< { 63, 1.12275575285571389562324404931e44, 0 },
< { 64, 1.13013833919932263255499077353e45, 0 },
< { 65, 7.2979123935621403215510863205e45, 0 },
< { 66, 7.4589130387155293748629391053e46, 0 },
< { 67, 4.8896013036866340154392278347e47, 0 },
< { 68, 5.0720608663265599749067985916e48, 0 },
< { 69, 3.3738248995437774706530672060e49, 0 },
< { 70, 3.5504426064285919824347590141e50, 0 },
< { 71, 2.39541567867608200416367771623e51, 0 },
< { 72, 2.55631867662858622735302649017e52, 0 },
< { 73, 1.74865344543353986303948473285e53, 0 },
< { 74, 1.89167582070515380824123960272e54, 0 },
< { 75, 1.31149008407515489727961354964e55, 0 },
< { 76, 1.43767362373591689426334209807e56, 0 },
< { 77, 1.00984736473786927090530243322e57, 0 },
< { 78, 1.12138542651401517752540683649e58, 0 },
< { 79, 7.9777941814291672401518892225e58, 0 },
< { 80, 8.9710834121121214202032546920e59, 0 },
< { 81, 6.4620132869576254645230302702e60, 0 },
< { 82, 7.3562883979319395645666688474e61, 0 },
< { 83, 5.3634710281748291355541151243e62, 0 },
< { 84, 6.1792822542628292342360018318e63, 0 },
< { 85, 4.5589503739486047652209978556e64, 0 },
< { 86, 5.3141827386660331414429615754e65, 0 },
< { 87, 3.9662868253352861457422681344e66, 0 },
< { 88, 4.6764808100261091644698061863e67, 0 },
< { 89, 3.5299952745484046697106186396e68, 0 },
< { 90, 4.2088327290234982480228255677e69, 0 },
< { 91, 3.2122956998390482494366629620e70, 0 },
< { 92, 3.8721261107016183881809995223e71, 0 },
< { 93, 2.98743500085031487197609655470e72, 0 },
< { 94, 3.6397985440595212848901395509e73, 0 },
< { 95, 2.83806325080779912837729172696e74, 0 },
< { 96, 3.4942066022971404334945339689e75, 0 },
< { 97, 2.75292135328356515452597297515e76, 0 },
< { 98, 3.4243224702511976248246432895e77, 0 },
< { 99, 2.72539213975072950298071324540e78, 0 },
< { 100, 3.4243224702511976248246432895e79, 0 },
< { 101, 2.75264606114823679801052037785e80, 0 },
< { 102, 3.4928089196562215773211361553e81, 0 },
< { 103, 2.83522544298268390195083598919e82, 0 },
< { 104, 3.6325212764424704404139816015e83, 0 },
< { 105, 2.97698671513181809704837778865e84, 0 },
< { 106, 3.8504725530290186668388204976e85, 0 },
< { 107, 3.1853757851910453638417642339e86, 0 },
< { 108, 4.1585103572713401601859261374e87, 0 },
< { 109, 3.4720596058582394465875230149e88, 0 },
< { 110, 4.5743613929984741762045187512e89, 0 },
< { 111, 3.8539861625026457857121505465e90, 0 },
< { 112, 5.1232847601582910773490610013e91, 0 },
< { 113, 4.3550043636279897378547301176e92, 0 },
< { 114, 5.8405446265804518281779295415e93, 0 },
< { 115, 5.0082550181721881985329396352e94, 0 },
< { 116, 6.7750317668333241206863982681e95, 0 },
< { 117, 5.8596583712614601922835393732e96, 0 },
< { 118, 7.9945374848633224624099499564e97, 0 },
< { 119, 6.9729934618011376288174118541e98, 0 },
< { 120, 9.5934449818359869548919399477e99, 0 },
< { 121, 8.4373220887793765308690683435e100, 0 },
< { 122, 1.17040028778399040849681667362e102, 0 },
< { 123, 1.03779061691986331329689540625e103, 0 },
< { 124, 1.45129635685214810653605267528e104, 0 },
< { 125, 1.29723827114982914162111925781e105, 0 },
< { 126, 1.82863340963370661423542637086e106, 0 },
< { 127, 1.64749260436028300985882145742e107, 0 },
< { 128, 2.34065076433114446622134575470e108, 0 },
< { 129, 2.12526545962476508271787968008e109, 0 },
< { 130, 3.04284599363048780608774948111e110, 0 },
< { 131, 2.78409775210844225836042238090e111, 0 },
< { 132, 4.0165567115922439040358293151e112, 0 },
< { 133, 3.7028500103042282036193617666e113, 0 },
< { 134, 5.3821859935336068314080112822e114, 0 },
< { 135, 4.9988475139107080748861383849e115, 0 },
< { 136, 7.3197729512057052907148953438e116, 0 },
< { 137, 6.8484210940576700625940095873e117, 0 },
< { 138, 1.01012866726638733011865555744e119, 0 },
< { 139, 9.5193053207401613870056733264e119, 0 },
< { 140, 1.41418013417294226216611778042e121, 0 },
< { 141, 1.34222205022436275556779993902e122, 0 },
< { 142, 2.00813579052557801227588724819e123, 0 },
< { 143, 1.91937753182083874046195391280e124, 0 },
< { 144, 2.89171553835683233767727763739e125, 0 },
< { 145, 2.78309742114021617366983317355e126, 0 },
< { 146, 4.2219046860009752130088253506e127, 0 },
< { 147, 4.0911532090761177752946547651e128, 0 },
< { 148, 6.2484189352814433152530615189e129, 0 },
< { 149, 6.0958182815234154851890356000e130, 0 },
< { 150, 9.3726284029221649728795922783e131, 0 },
< { 151, 9.2046856051003573826354437561e132, 0 },
< { 152, 1.42463951724416907587769802630e134, 0 },
< { 153, 1.40831689758035467954322289468e135, 0 },
< { 154, 2.19394485655602037685165496051e136, 0 },
< { 155, 2.18289119124954975329199548675e137, 0 },
< { 156, 3.4225539762273917878885817384e138, 0 },
< { 157, 3.4271391702617931126684329142e139, 0 },
< { 158, 5.4076352824392790248639591467e140, 0 },
< { 159, 5.4491512807162510491428083336e141, 0 },
< { 160, 8.6522164519028464397823346347e142, 0 },
< { 161, 8.7731335619531641891199214170e143, 0 },
< { 162, 1.40165906520826112324473821082e145, 0 },
< { 163, 1.43002077059836576282654719098e146, 0 },
< { 164, 2.29872086694154824212137066574e147, 0 },
< { 165, 2.35953427148730350866380286512e148, 0 },
< { 166, 3.8158766391229700819214753051e149, 0 },
< { 167, 3.9404222333837968594685507847e150, 0 },
< { 168, 6.4106727537265897376280785126e151, 0 },
< { 169, 6.6593135744186166925018508262e152, 0 },
< { 170, 1.08981436813352025539677334714e154, 0 },
< { 171, 1.13874262122558345441781649128e155, 0 },
< { 172, 1.87448071318965483928245015709e156, 0 },
< { 173, 1.97002473472025937614282252992e157, 0 },
< { 174, 3.2615964409499994203514632733e158, 0 },
< { 175, 3.4475432857604539082499394274e159, 0 },
< { 176, 5.7404097360719989798185753611e160, 0 },
< { 177, 6.1021516157960034176023927864e161, 0 },
< { 178, 1.02179293302081581840770641427e163, 0 },
< { 179, 1.09228513922748461175082830877e164, 0 },
< { 180, 1.83922727943746847313387154568e165, 0 },
< { 181, 1.97703610200174714726899923887e166, 0 },
< { 182, 3.3473936485761926211036462131e167, 0 },
< { 183, 3.6179760666631972795022686071e168, 0 },
< { 184, 6.1592043133801944228307090322e169, 0 },
< { 185, 6.6932557233269149670791969232e170, 0 },
< { 186, 1.14561200228871616264651187999e172, 0 },
< { 187, 1.25163882026213309884380982464e173, 0 },
< { 188, 2.15375056430278638577544233437e174, 0 },
< { 189, 2.36559737029543155681480056857e175, 0 },
< { 190, 4.0921260721752941329733404353e176, 0 },
< { 191, 4.5182909772642742735162690860e177, 0 },
< { 192, 7.8568820585765647353088136358e178, 0 },
< { 193, 8.7203015861200493478863993359e179, 0 },
< { 194, 1.52423511936385355864990984535e181, 0 },
< { 195, 1.70045880929340962283784787050e182, 0 },
< { 196, 2.98750083395315297495382329688e183, 0 },
< { 197, 3.3499038543080169569905603049e184, 0 },
< { 198, 5.9152516512272428904085701278e185, 0 },
< { 199, 6.6663086700729537444112150067e186, 0 },
< { 200, 1.18305033024544857808171402556e188, 0 },
< { 201, 1.33992804268466370262665421635e189, 0 },
< { 202, 2.38976166709580612772506233164e190, 0 },
< { 203, 2.72005392664986731633210805920e191, 0 },
< { 204, 4.8751138008754445005591271565e192, 0 },
< { 205, 5.5761105496322279984808215214e193, 0 },
< { 206, 1.00427344298034156711518019425e195, 0 },
< { 207, 1.15425488377387119568553005492e196, 0 },
< { 208, 2.08888876139911045959957480403e197, 0 },
< { 209, 2.41239270708739079898275781478e198, 0 },
< { 210, 4.3866663989381319651591070885e199, 0 },
< { 211, 5.0901486119543945858536189892e200, 0 },
< { 212, 9.2997327657488397661373070276e201, 0 },
< { 213, 1.08420165434628604678682084470e203, 0 },
< { 214, 1.99014281187025170995338370390e204, 0 },
< { 215, 2.33103355684451500059166481610e205, 0 },
< { 216, 4.2987084736397436934993088004e206, 0 },
< { 217, 5.0583428183525975512839126509e207, 0 },
< { 218, 9.3711844725346412518284931849e208, 0 },
< { 219, 1.10777707721921886373117687056e210, 0 },
< { 220, 2.06166058395762107540226850068e211, 0 },
< { 221, 2.44818734065447368884590088393e212, 0 },
< { 222, 4.5768864963859187873930360715e213, 0 },
< { 223, 5.4594577696594763261263589712e214, 0 },
< { 224, 1.02522257519044580837604008002e216, 0 },
< { 225, 1.22837799817338217337843076851e217, 0 },
< { 226, 2.31700301993040752692985058084e218, 0 },
< { 227, 2.78841805585357753356903784452e219, 0 },
< { 228, 5.2827668854413291614000593243e220, 0 },
< { 229, 6.3854773479046925518730966640e221, 0 },
< { 230, 1.21503638365150570712201364459e223, 0 },
< { 231, 1.47504526736598397948268532937e224, 0 },
< { 232, 2.81888441007149324052307165546e225, 0 },
< { 233, 3.4368554729627426721946568174e226, 0 },
< { 234, 6.5961895195672941828239876738e227, 0 },
< { 235, 8.0766103614624452796574435210e228, 0 },
< { 236, 1.55670072661788142714646109101e230, 0 },
< { 237, 1.91415665566659953127881411447e231, 0 },
< { 238, 3.7049477293505577966085773966e232, 0 },
< { 239, 4.5748344070431728797563657336e233, 0 },
< { 240, 8.8918745504413387118605857518e234, 0 },
< { 241, 1.10253509209740466402128414180e236, 0 },
< { 242, 2.15183364120680396827026175195e237, 0 },
< { 243, 2.67916027379669333357172046456e238, 0 },
< { 244, 5.2504740845446016825794386748e239, 0 },
< { 245, 6.5639426708018986672507151382e240, 0 },
< { 246, 1.29161662479797201391454191399e242, 0 },
< { 247, 1.62129383968806897081092663913e243, 0 },
< { 248, 3.2032092294989705945080639467e244, 0 },
< { 249, 4.0370216608232917373192073314e245, 0 },
< { 250, 8.0080230737474264862701598667e246, 0 },
< { 251, 1.01329243686664622606712104019e248, 0 },
< { 252, 2.01802181458435147454008028642e249, 0 },
< { 253, 2.56362986527261495194981623168e250, 0 },
< { 254, 5.1257754090442527453318039275e251, 0 },
< { 255, 6.5372561564451681274720313908e252, 0 },
< { 256, 1.31219850471532870280494180544e254, 0 },
< { 257, 1.68007483220640820876031206743e255, 0 },
< { 258, 3.3854721421655480532367498580e256, 0 },
< { 259, 4.3513938154145972606892082546e257, 0 },
< { 260, 8.8022275696304249384155496309e258, 0 },
< { 261, 1.13571378582320988503988335446e260, 0 },
< { 262, 2.30618362324317133386487400329e261, 0 },
< { 263, 2.98692725671504199765489322224e262, 0 },
< { 264, 6.0883247653619723214032673687e263, 0 },
< { 265, 7.9153572302948612937854670389e264, 0 },
< { 266, 1.61949438758628463749326912007e266, 0 },
< { 267, 2.11340038048872796544071969939e267, 0 },
< { 268, 4.3402449587312428284819612418e268, 0 },
< { 269, 5.6850470235146782270355359914e269, 0 },
< { 270, 1.17186613885743556369012953528e271, 0 },
< { 271, 1.54064774337247779952663025366e272, 0 },
< { 272, 3.1874758976922247332371523360e273, 0 },
< { 273, 4.2059683394068643927077005925e274, 0 },
< { 274, 8.7336839596766957690697974006e275, 0 },
< { 275, 1.15664129333688770799461766294e277, 0 },
< { 276, 2.41049677287076803226326408256e278, 0 },
< { 277, 3.2038963825431789511450909263e279, 0 },
< { 278, 6.7011810285807351296918741495e280, 0 },
< { 279, 8.9388709072954692736948036845e281, 0 },
< { 280, 1.87633068800260583631372476186e283, 0 },
< { 281, 2.51182272495002686590823983534e284, 0 },
< { 282, 5.2912525401673484584047038284e285, 0 },
< { 283, 7.1084583116085760305203187340e286, 0 },
< { 284, 1.50271572140752696218693588728e288, 0 },
< { 285, 2.02591061880844416869829083919e289, 0 },
< { 286, 4.2977669632255271118546366376e290, 0 },
< { 287, 5.8143634759802347641640947085e291, 0 },
< { 288, 1.23775688540895180821413535163e293, 0 },
< { 289, 1.68035104455828784684342337075e294, 0 },
< { 290, 3.5894949676859602438209925197e295, 0 },
< { 291, 4.8898215396646176343143620089e296, 0 },
< { 292, 1.04813253056430039119572981576e298, 0 },
< { 293, 1.43271771112173296685410806860e299, 0 },
< { 294, 3.08150963985904315011544565835e300, 0 },
< { 295, 4.2265172478091122522196188024e301, 0 },
< { 296, 9.1212685339827677243417191487e302, 0 },
< { 297, 1.25527562259930633890922678431e304, 0 },
< /*
< { 298, 2.71813802312686478185383230631e305, 0 },
< { 299, 3.7532741115719259533385880851e306, 0 },
< { 300, 8.1544140693805943455614969189e307, }
< */
---
> static struct {int n; double f; long i; double lnf; }
> doub_fact_table[DOUB_FACT_TABLE_SIZE] = {
> { 0, 1.0, 1L, 0.0000000000000000},
> { 1, 1.0, 1L, 0.0000000000000000},
> { 2, 2.0, 2L, 0.6931471805599453},
> { 3, 3.0, 3L, 1.0986122886681098},
> { 4, 8.0, 8L, 2.0794415416798357},
> { 5, 15.0, 15L, 2.7080502011022101},
> { 6, 48.0, 48L, 3.8712010109078907},
> { 7, 105.0, 105L, 4.6539603501575231},
> { 8, 384.0, 384L, 5.9506425525877269},
> { 9, 945.0, 945L, 6.8511849274937422},
> { 10, 3840.0, 3840L, 8.2532276455817737},
> { 11, 10395.0, 10395L, 9.2490802002921129},
> { 12, 46080.0, 46080L, 10.7381342953697736},
> { 13, 135135.0, 135135L, 11.8140295577536492},
> { 14, 645120.0, 645120L, 13.3771916249850324},
> { 15, 2027025.0, 2027025L, 14.5220797588558597},
> { 16, 10321920.0, 10321920L, 16.1497803472248123},
> { 17, 34459425.0, 34459425L, 17.3552931029120749},
> { 18, 185794560.0, 185794560L, 19.0401521051209777},
> { 19, 654729075.0, 654729075L, 20.2997320820785134},
> { 20, 3715891200.0, 0L, 22.0358843786749681},
> { 21, 13749310575.0, 0L, 23.3442545198019360},
> { 22, 81749606400.0, 0L, 25.1269268320332841},
> { 23, 316234143225.0, 0L, 26.4797487357310857},
> { 24, 1961990553600.0, 0L, 28.3049806623812295},
> { 25, 7905853580625.0, 0L, 29.6986245605992849},
> { 26, 51011754393600.0, 0L, 31.5630772004027129},
> { 27, 213458046676875.0, 0L, 32.9944614266036140},
> { 28, 1428329123020800.0, 0L, 34.8952817105779189},
> { 29, 6190283353629375.0, 0L, 36.3617572565900886},
> { 30, 42849873690624000.0, 0L, 38.2964790922400766},
> { 31, 191898783962510625.0, 0L, 39.7957444610752376},
> { 32, 1371195958099968000.0, 0L, 41.7622149950398054},
> { 33, 6332659870762850625.0, 0L, 43.2922520225417173},
> { 34, 46620662575398912000.0, 0L, 45.2885755196559643},
> { 35, 221643095476699771875.0, 0L, 46.8476000840311286},
> { 36, 1678343852714360832000.0, 0L, 48.8720944581120733},
> { 37, 8200794532637891559375.0, 0L, 50.4585179966753543},
> { 38, 63777066403145711616000.0, 0L, 52.5096806178384554},
> { 39, 319830986772877770815625.0, 0L, 54.1220796428049979},
> { 40, 2551082656125828464640000.0, 0L, 56.1985600719523930},
> { 41, 13113070457687988603440625.0, 0L, 57.8356517095093068},
> { 42, 107145471557284795514880000.0, 0L, 59.9362296902357627},
> { 43, 563862029680583509947946875.0, 0L, 61.5968518252028687},
> { 44, 4714400748520531002654720000.0, 0L, 63.7204193241540224},
> { 45, 25373791335626257947657609375.0, 0L, 65.4035143149731937},
> { 46, 216862434431944426122117120000.0, 0L, 67.5490607206431122},
> { 47, 1192568192774434123539907640625.0, 0L, 69.2536619166832565},
> { 48, 10409396852733332453861621760000.0, 0L, 71.4202617315510082},
> { 49, 58435841445947272053455474390625.0, 0L, 73.1454822147938870},
> { 50, 520469842636666622693081088000000.0, 0L, 75.3322847369791475},
> { 51, 2980227913743310874726229193921875.0, 0L, 77.0773078475182132},
> { 52, 27064431817106664380040216576000000.0, 0L, 79.2835284555605710},
> { 53, 157952079428395476360490147277859375.0, 0L, 81.0475997610703303},
> { 54, 1461479318123759876522171695104000000.0, 0L, 83.2725125021248402},
> { 55, 8687364368561751199826958100282265625.0, 0L, 85.0549329463027988},
> { 56, 8.18428418149305530852416149258e37, 0L, 87.2978641928599899},
> { 57, 4.95179769008019818390136611716e38, 0L, 89.0979842141373553},
> { 58, 4.74688482526597207894401366570e39, 0L, 91.3583072034064116},
> { 59, 2.92156063714731692850180600912e40, 0L, 93.1755216580430812},
> { 60, 2.84813089515958324736640819942e41, 0L, 95.4526517656285165},
> { 61, 1.78215198865986332638610166557e42, 0L, 97.2863955222163952},
> { 62, 1.76584115499894161336717308364e43, 0L, 99.5797861506736126},
> { 63, 1.12275575285571389562324404931e44, 0L, 101.4295302486079322},
> { 64, 1.13013833919932263255499077353e45, 0L, 103.7386692340332814},
> { 65, 7.29791239356214032155108632049e45, 0L, 105.6039175185035646},
> { 66, 7.45891303871552937486293910529e46, 0L, 107.9283239760597013},
> { 67, 4.88960130368663401543922783473e47, 0L, 109.8086101378945330},
> { 68, 5.07206086632655997490679859160e48, 0L, 112.1478316812358145},
> { 69, 3.37382489954377747065306720596e49, 0L, 114.0427166424917971},
> { 70, 3.55044260642859198243475901412e50, 0L, 116.3963269232851729},
> { 71, 2.39541567867608200416367771623e51, 0L, 118.3053965195331187},
> { 72, 2.55631867662858622735302649017e52, 0L, 120.6729930423012291},
> { 73, 1.74865344543353986303948473285e53, 0L, 122.5958559606815044},
> { 74, 1.89167582070515380824123960272e54, 0L, 124.9770581355054020},
> { 75, 1.31149008407515489727961354964e55, 0L, 126.9133440742178180},
> { 76, 1.43767362373591689426334209807e56, 0L, 129.3077914757917313},
> { 77, 1.00984736473786927090530243322e57, 0L, 131.2571494960714915},
> { 78, 1.12138542651401517752540683649e58, 0L, 133.6645003024813150},
> { 79, 7.97779418142916724015188922245e58, 0L, 135.6265973485385246},
> { 80, 8.97108341211212142020325469195e59, 0L, 138.0465269371551926},
> { 81, 6.46201328695762546452303027018e60, 0L, 140.0210465032109539},
> { 82, 7.35628839793193956456666884740e61, 0L, 142.4532461844194415},
> { 83, 5.36347102817482913555411512425e62, 0L, 144.4398871110075504},
> { 84, 6.17928225426282923423600183182e63, 0L, 146.8840629832627656},
> { 85, 4.55895037394860476522099785562e64, 0L, 148.8825383674978582},
> { 86, 5.31418273866603314144296157536e65, 0L, 151.3384102795162676},
> { 87, 3.96628682533528614574226813439e66, 0L, 153.3484464861524543},
> { 88, 4.67648081002610916446980618632e67, 0L, 155.8157470939944744},
> { 89, 3.52999527454840466971061863960e68, 0L, 157.8370828558846028},
> { 90, 4.20883272902349824802282556769e69, 0L, 160.3155567643247537},
> { 91, 3.21229569983904824943666296204e70, 0L, 162.3479423624014544},
> { 92, 3.87212611070161838818099952227e71, 0L, 164.8373453413738048},
> { 93, 2.98743500085031487197609655470e72, 0L, 166.8805418555547249},
> { 94, 3.63979854405952128489013955094e73, 0L, 169.3806401236438148},
> { 95, 2.83806325080779912837729172696e74, 0L, 171.4344187471552630},
> { 96, 3.49420660229714043349453396890e75, 0L, 173.9449883151116580},
> { 97, 2.75292135328356515452597297515e76, 0L, 176.0091297256586529},
> { 98, 3.42432247025119762482464328952e77, 0L, 178.5299557937822215},
> { 99, 2.72539213975072950298071324540e78, 0L, 180.6042495757932329},
> { 100, 3.42432247025119762482464328952e79, 0L, 183.1351259797703221},
> { 101, 2.75264606114823679801052037785e80, 0L, 185.2193700926345059},
> { 102, 3.49280891965622157732113615531e81, 0L, 187.7600987930545955},
> { 103, 2.83522544298268390195083598919e82, 0L, 189.8540990808641311},
> { 104, 3.63252127644247044041398160152e83, 0L, 192.4044896921959662},
> { 105, 2.97698671513181809704837778865e84, 0L, 194.5080594310216497},
> { 106, 3.85047255302901866683882049762e85, 0L, 197.0679287863080447},
> { 107, 3.18537578519104536384176423386e86, 0L, 199.1808882654835600},
> { 108, 4.15851035727134016018592613742e87, 0L, 201.7500600134322610},
> { 109, 3.47205960585823944658752301490e88, 0L, 203.8722361477126981},
> { 110, 4.57436139299847417620451875117e89, 0L, 206.4505403792246909},
> { 111, 3.85398616250264578571215054654e90, 0L, 208.5817663490250311},
> { 112, 5.12328476015829107734906100131e91, 0L, 211.1690392505197735},
> { 113, 4.35500436362798973785473011759e92, 0L, 213.3091541677373755},
> { 114, 5.84054462658045182817792954149e93, 0L, 215.9052376989142772},
> { 115, 5.00825501817218819853293963523e94, 0L, 218.0540862961006212},
> { 116, 6.77503176683332412068639826813e95, 0L, 220.6588278900206319},
> { 117, 5.85965837126146019228353937322e96, 0L, 222.8162602308983651},
> { 118, 7.99453748486332246240994995639e97, 0L, 225.4295125144863050},
> { 119, 6.97299346180113762881741185413e98, 0L, 227.5953837240099062},
> { 120, 9.59344498183598695489193994767e99, 0L, 230.2170042572683428},
> { 121, 8.43732208877937653086906834350e100, 0L, 232.3911742696066369},
> { 122, 1.17040028778399040849681667362e102, 0L, 235.0210253020015898},
> { 123, 1.03779061691986331329689540625e103, 0L, 237.2033586249790460},
> { 124, 1.45129635685214810653605267528e104, 0L, 239.8413068676066189},
> { 125, 1.29723827114982914162111925781e105, 0L, 242.0316723622813413},
> { 126, 1.82863340963370661423542637086e106, 0L, 244.6775887745581031},
> { 127, 1.64749260436028300985882145742e107, 0L, 246.8758594487399307},
> { 128, 2.34065076433114446622134575470e108, 0L, 249.5296190384777333},
> { 129, 2.12526545962476508271787968008e109, 0L, 251.7356718531015929},
> { 130, 3.04284599363048780608774948111e110, 0L, 254.3971534889333270},
> { 131, 2.78409775210844225836042238090e111, 0L, 256.6108691763027423},
> { 132, 4.01655671159224390403582931506e112, 0L, 259.2799554115197225},
> { 133, 3.70285001030422820361936176660e113, 0L, 261.5012183045245138},
> { 134, 5.38218599353360683140801128218e114, 0L, 264.1777952114706522},
> { 135, 4.99884751391070807488613838490e115, 0L, 266.4064930829629247},
> { 136, 7.31977295120570529071489534377e116, 0L, 269.0904500972067126},
> { 137, 6.84842109405767006259400958732e117, 0L, 271.3264740087910241},
> { 138, 1.01012866726638733011865555744e119, 0L, 274.0177037823639239},
> { 139, 9.51930532074016138700567332637e119, 0L, 276.2609479419216996},
> { 140, 1.41418013417294226216611778042e121, 0L, 278.9593462049732011},
> { 141, 1.34222205022436275556779993902e122, 0L, 281.2097078322998414},
> { 142, 2.00813579052557801227588724819e123, 0L, 283.9151732625744557},
> { 143, 1.91937753182083874046195391280e124, 0L, 286.1725524625597359},
> { 144, 2.89171553835683233767727763739e125, 0L, 288.8849865621504591},
> { 145, 2.78309742114021617366983317355e126, 0L, 291.1492862049802852},
> { 146, 4.22190468600097521300882535059e127, 0L, 293.8685931838588203},
> { 147, 4.09115320907611777529465476513e128, 0L, 296.1397187917590372},
> { 148, 6.24841893528144331525306151888e129, 0L, 298.8658054576229119},
> { 149, 6.09581828152341548518903560004e130, 0L, 301.1436650977045133},
> { 150, 9.37262840292216497287959227832e131, 0L, 303.8764407517191444},
> { 151, 9.20468560510035738263544375606e132, 0L, 306.1609449345194207},
> { 152, 1.42463951724416907587769802630e134, 0L, 308.9003212725654066},
> { 153, 1.40831689758035467954322289468e135, 0L, 311.1913828559118542},
> { 154, 2.19394485655602037685165496051e136, 0L, 313.9372738749790415},
> { 155, 2.18289119124954975329199548675e137, 0L, 316.2348079728311063},
> { 156, 3.42255397622739178788858173839e138, 0L, 318.9871298822286008},
> { 157, 3.42713917026179311266843291420e139, 0L, 321.2910537781793892},
> { 158, 5.40763528243927902486395914666e140, 0L, 324.0497249152555810},
> { 159, 5.44915128071625104914280833357e141, 0L, 326.3599579803995994},
> { 160, 8.65221645190284643978233463466e142, 0L, 329.1248987304894058},
> { 161, 8.77313356195316418911992141705e143, 0L, 331.4413623453840501},
> { 162, 1.40165906520826112324473821082e145, 0L, 334.2124950657217823},
> { 163, 1.43002077059836576282654719098e146, 0L, 336.5351125461908168},
> { 164, 2.29872086694154824212137066574e147, 0L, 339.3123614935460068},
> { 165, 2.35953427148730350866380286512e148, 0L, 341.6410580200914069},
> { 166, 3.81587663912297008192147530512e149, 0L, 344.4243492819025505},
> { 167, 3.94042223338379685946855078474e150, 0L, 346.7590518325081348},
> { 168, 6.41067275372658973762807851261e151, 0L, 349.5483132613057933},
> { 169, 6.65931357441861669250185082621e152, 0L, 351.8889505474311932},
> { 170, 1.08981436813352025539677334714e154, 0L, 354.6841116983560482},
> { 171, 1.13874262122558345441781649128e155, 0L, 357.0306141039338286},
> { 172, 1.87448071318965483928245015709e156, 0L, 359.8316061751694974},
> { 173, 1.97002473472025937614282252992e157, 0L, 362.1839056984316016},
> { 174, 3.26159644094999942035146327333e158, 0L, 364.9906614743840123},
> { 175, 3.44754328576045390824993942736e159, 0L, 367.3486916723551303},
> { 176, 5.74040973607199897981857536106e160, 0L, 370.1611454694221379},
> { 177, 6.10215161579600341760239278642e161, 0L, 372.5248414049289636},
> { 178, 1.02179293302081581840770641427e163, 0L, 375.3429290197142336},
> { 179, 1.09228513922748461175082830877e164, 0L, 377.7122272107696972},
> { 180, 1.83922727943746847313387154568e165, 0L, 380.5358858706044316},
> { 181, 1.97703610200174714726899923887e166, 0L, 382.9107242420355419},
> { 182, 3.34739364857619262110364621314e167, 0L, 385.7398925576812303},
> { 183, 3.61797606666319727950226860714e168, 0L, 388.1202103948769491},
> { 184, 6.15920431338019442283070903219e169, 0L, 390.9548283152902286},
> { 185, 6.69325572332691496707919692321e170, 0L, 393.3405662199552921},
> { 186, 1.14561200228871616264651187999e172, 0L, 396.1805749890034463},
> { 187, 1.25163882026213309884380982464e173, 0L, 398.5716748368099047},
> { 188, 2.15375056430278638577544233437e174, 0L, 401.4170169518333751},
> { 189, 2.36559737029543155681480056857e175, 0L, 403.8134218518695207},
> { 190, 4.09212607217529413297334043531e176, 0L, 406.6640410239938888},
> { 191, 4.51829097726427427351626908597e177, 0L, 409.0656952799161559},
> { 192, 7.85688205857656473530881363580e178, 0L, 411.9215363960216791},
> { 193, 8.72030158612004934788639933592e179, 0L, 414.3283854688210681},
> { 194, 1.52423511936385355864990984535e181, 0L, 417.1893945550850162},
> { 195, 1.70045880929340962283784787050e182, 0L, 419.6013850273848220},
> { 196, 2.98750083395315297495382329688e183, 0L, 422.4675092143155553},
> { 197, 3.34990385430801695699056030489e184, 0L, 424.8845887561228096},
> { 198, 5.91525165122724289040857012782e185, 0L, 427.7557762450101109},
> { 199, 6.66630867007295374441121500674e186, 0L, 430.1778935808472966},
> { 200, 1.18305033024544857808171402556e188, 0L, 433.0540936115581303},
> { 201, 1.33992804268466370262665421635e189, 0L, 435.4811984889063865},
> { 202, 2.38976166709580612772506233164e190, 0L, 438.3623613089593505},
> { 203, 2.72005392664986731633210805920e191, 0L, 440.7944044679481976},
> { 204, 4.87511380087544450055912715654e192, 0L, 443.6804813028035710},
> { 205, 5.57611054963222799848082152136e193, 0L, 446.1174144470866167},
> { 206, 1.00427344298034156711518019425e195, 0L, 449.0083574715931718},
> { 207, 1.15425488377387119568553005492e196, 0L, 451.4501332403519882},
> { 208, 2.08888876139911045959957480403e197, 0L, 454.3458955512944613},
> { 209, 2.41239270708739079898275781478e198, 0L, 456.7924674923168027},
> { 210, 4.38666639893813196515910708847e199, 0L, 459.6930030820119555},
> { 211, 5.09014861195439458585361898919e200, 0L, 462.1443256257928738},
> { 212, 9.29973276574883976613730702756e201, 0L, 465.0495893566839527},
> { 213, 1.08420165434628604678682084470e203, 0L, 467.5056177915022886},
> { 214, 1.99014281187025170995338370390e204, 0L, 470.4155653717057817},
> { 215, 2.33103355684451500059166481610e205, 0L, 472.8762558196299324},
> { 216, 4.29870847363974369349930880042e206, 0L, 475.7908437793899452},
> { 217, 5.05834281835259755128391265094e207, 0L, 478.2561531731703894},
> { 218, 9.37118447253464125182849318492e208, 0L, 481.1753388421790305},
> { 219, 1.10777707721921886373117687056e210, 0L, 483.6452249029869108},
> { 220, 2.06166058395762107540226850068e211, 0L, 486.5689663885314076},
> { 221, 2.44818734065447368884590088393e212, 0L, 489.0433876045046873},
> { 222, 4.57688649638591878739303607151e213, 0L, 491.9716437704036593},
> { 223, 5.45945776965947632612635897116e214, 0L, 494.4505593759648150},
> { 224, 1.02522257519044580837604008002e216, 0L, 497.3832898222586891},
> { 225, 1.22837799817338217337843076851e217, 0L, 499.8666597781692076},
> { 226, 2.31700301993040752692985058084e218, 0L, 502.8038248215309522},
> { 227, 2.78841805585357753356903784452e219, 0L, 505.2916097956506292},
> { 228, 5.28276688544132916140005932432e220, 0L, 508.2331704504853747},
> { 229, 6.38547734790469255187309666395e221, 0L, 510.7253317992048665},
> { 230, 1.21503638365150570712201364459e223, 0L, 513.6712497594086244},
> { 231, 1.47504526736598397948268532937e224, 0L, 516.1677495097266046},
> { 232, 2.81888441007149324052307165546e225, 0L, 519.1179871310749832},
> { 233, 3.43685547296274267219465681744e226, 0L, 521.6187879632923341},
> { 234, 6.59618951956729418282398767377e227, 0L, 524.5733082464327026},
> { 235, 8.07661036146244527965744352098e228, 0L, 527.0783734774364575},
> { 236, 1.55670072661788142714646109101e230, 0L, 530.0371400514583229},
> { 237, 1.91415665566659953127881411447e231, 0L, 532.5464336185715410},
> { 238, 3.70494772935055779660857739660e232, 0L, 535.5094107251297828},
> { 239, 4.57483440704317287975636573359e233, 0L, 538.0228971705030290},
> { 240, 8.89187455044133871186058575185e234, 0L, 540.9900496484717678},
> { 241, 1.10253509209740466402128414180e236, 0L, 543.5076941039936855},
> { 242, 2.15183364120680396827026175195e237, 0L, 546.4789873746284457},
> { 243, 2.67916027379669333357172046456e238, 0L, 549.0007555473342791},
> { 244, 5.25047408454460168257943867475e239, 0L, 551.9761555999216398},
> { 245, 6.56394267080189866725071513818e240, 0L, 554.5020137578790127},
> { 246, 1.29161662479797201391454191399e242, 0L, 557.4814871358539676},
> { 247, 1.62129383968806897081092663913e243, 0L, 560.0114020945069342},
> { 248, 3.20320922949897059450806394669e244, 0L, 562.9949158820189723},
> { 249, 4.03702166082329173731920733143e245, 0L, 565.5288549909716949},
> { 250, 8.00802307374742648627015986673e246, 0L, 568.5163767998811863},
> { 251, 1.01329243686664622606712104019e248, 0L, 571.0543079301035050},
> { 252, 2.01802181458435147454008028642e249, 0L, 574.0458058873925893},
> { 253, 2.56362986527261495194981623168e250, 0L, 576.5876974188309987},
> { 254, 5.12577540904425274533180392750e251, 0L, 579.5831401544111259},
> { 255, 6.53725615644516812747203139078e252, 0L, 582.1289609639894707},
> { 256, 1.31219850471532870280494180544e254, 0L, 585.1283175988907033},
> { 257, 1.68007483220640820876031206743e255, 0L, 587.6780370488846756},
> { 258, 3.38547214216554805323674985803e256, 0L, 590.6812771838123126},
> { 259, 4.35139381541459726068920825465e257, 0L, 593.2348651105842237},
> { 260, 8.80222756963042493841554963089e258, 0L, 596.2419588148278535},
> { 261, 1.13571378582320988503988335446e260, 0L, 598.7993855179068987},
> { 262, 2.30618362324317133386487400329e261, 0L, 601.8103033185889217},
> { 263, 2.98692725671504199765489322224e262, 0L, 604.3715395500846626},
> { 264, 6.08832476536197232140326736869e263, 0L, 607.3862524217352075},
> { 265, 7.91535723029486129378546703893e264, 0L, 609.9512693760708544},
> { 266, 1.61949438758628463749326912007e266, 0L, 612.9697487305169261},
> { 267, 2.11340038048872796544071969939e267, 0L, 615.5385180344710534},
> { 268, 4.34024495873124282848196124179e268, 0L, 618.5607357110277462},
> { 269, 5.68504702351467822703553599137e269, 0L, 621.1332294140728436},
> { 270, 1.17186613885743556369012953528e271, 0L, 624.1591576700261612},
> { 271, 1.54064774337247779952663025366e272, 0L, 626.7353482349525393},
> { 272, 3.18747589769222473323715233597e273, 0L, 629.7649597363221119},
> { 273, 4.20596833940686439270770059250e274, 0L, 632.3448200301374982},
> { 274, 8.73368395967669576906979740057e275, 0L, 635.3780878427102152},
> { 275, 1.15664129333688770799461766294e277, 0L, 637.9615911278040130},
> { 276, 2.41049677287076803226326408256e278, 0L, 640.9984887084273169},
> { 277, 3.20389638254317895114509092633e279, 0L, 643.5856086339913418},
> { 278, 6.70118102858073512969187414951e280, 0L, 646.6261098221179964},
> { 279, 8.93887090729546927369480368447e281, 0L, 649.2168204158126628},
> { 280, 1.87633068800260583631372476186e283, 0L, 652.2608994252872208},
> { 281, 2.51182272495002686590823983534e284, 0L, 654.8551750851463567},
> { 282, 5.29125254016734845840470382845e285, 0L, 657.9028064962253666},
> { 283, 7.10845831160857603052031873400e286, 0L, 660.5006219827895393},
> { 284, 1.50271572140752696218693588728e288, 0L, 663.5517807343866252},
> { 285, 2.02591061880844416869829083919e289, 0L, 666.1531111630581563},
> { 286, 4.29776696322552711185463663762e290, 0L, 669.2077725452064669},
> { 287, 5.81436347598023476416409470848e291, 0L, 671.8125933788177235},
> { 288, 1.23775688540895180821413535163e293, 0L, 674.8707330253423606},
> { 289, 1.68035104455828784684342337075e294, 0L, 677.4790200669301612},
> { 290, 3.58949496768596024382099251974e295, 0L, 680.5406139483228571},
> { 291, 4.88982153966461763431436200888e296, 0L, 683.1523433341016016},
> { 292, 1.04813253056430039119572981576e298, 0L, 686.2173677505911655},
> { 293, 1.43271771112173296685410806860e299, 0L, 688.8325159431186648},
> { 294, 3.08150963985904315011544565835e300, 0L, 691.9009475179298079},
> { 295, 4.22651724780911225221961880238e301, 0L, 694.5194912994585366},
> { 296, 9.12126853398276772434171914871e302, 0L, 697.5913069722538467},
> { 297, 1.25527562259930633890922678431e304, 0L, 700.2132234382612523}
> /*
> { 298, 2.71813802312686478185383230631e305, 0L, 703.2884004587592699},
> { 299, 3.75327411157192595333858808507e306, 0L, 705.9136670116519099},
> { 300, 8.15441406938059434556149691894e307, 0L, 708.9921829334155063}
> */
1513c1511
< result->val = log(fact_table[n].f);
---
> result->val = fact_table[n].lnf;
1529c1527
< result->val = log(doub_fact_table[n].f);
---
> result->val = doub_fact_table[n].lnf;
1566c1564
< if(m*2 > n) m = n-m;
---
> if(m*2 > n) m = n-m; /* this doesn't seem necessary */
^ permalink raw reply [flat|nested] 9+ messages in thread* Re: faster log factorials
2003-04-28 4:57 faster log factorials James Theiler
@ 2003-05-10 19:09 ` Brian Gough
2003-05-10 19:29 ` Brian Gough
1 sibling, 0 replies; 9+ messages in thread
From: Brian Gough @ 2003-05-10 19:09 UTC (permalink / raw)
To: James Theiler; +Cc: gsl-discuss
James Theiler writes:
> While looking at another part of GSL (randist/binomial.c -- I'll
> have more to say about that in a later email), I realized that the
> function gsl_sf_lnfact() [this computes log(n!)] could be speeded up
> for small arguments by pre-computing the logarithms.
Sounds reasonable to provide the log in the table as well.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-04-28 4:57 faster log factorials James Theiler
2003-05-10 19:09 ` Brian Gough
@ 2003-05-10 19:29 ` Brian Gough
2003-05-12 14:02 ` James Theiler
1 sibling, 1 reply; 9+ messages in thread
From: Brian Gough @ 2003-05-10 19:29 UTC (permalink / raw)
To: James Theiler; +Cc: gsl-discuss
James Theiler writes:
> 1. I used a perl script to rebuild the precomputed fact_table[] and
> doub_fact_table[]. Should this perl script be part of GSL? (Mark,
> you'll be relieved to know it's not part of the build script!)
It should be a 1-liner in gp-pari or Emacs Calc and could go
in the comments.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-10 19:29 ` Brian Gough
@ 2003-05-12 14:02 ` James Theiler
2003-05-12 21:56 ` Gerard Jungman
0 siblings, 1 reply; 9+ messages in thread
From: James Theiler @ 2003-05-12 14:02 UTC (permalink / raw)
To: Brian Gough; +Cc: gsl-discuss
On Sat, 10 May 2003, Brian Gough wrote:
] James Theiler writes:
] > 1. I used a perl script to rebuild the precomputed fact_table[] and
] > doub_fact_table[]. Should this perl script be part of GSL? (Mark,
] > you'll be relieved to know it's not part of the build script!)
]
] It should be a 1-liner in gp-pari or Emacs Calc and could go
] in the comments.
]
Right, computing logs is not exactly rocket science; the hard part
(the perl part) was to get all the braces and commas right, and the
indenting neat and even. I guess I agree that posterity will not miss
much if it does not have access to that code.
The ubiquitous use of factorials in multinomial expressions, in
special functions, and in random distributions, puts a premium on
their fast evaluation. A still-open question: If we provide
pre-computed values, how many should we provide? For the straight (no
logarithm) values, there is a natural cutoff at 170 since 170! (or is
it 171!?) is the largest value that is a valid IEEE double precison
number. But for the logs, we can assume the higher the cutoff the
more often we'll be able to provide a fast precomputed value. We
could easily provide thousands, and I think most computers nowadays
would not begrudge the memory. But there may be other issues that I
am not considering.
jt
---------------------------------------------
James Theiler jt@lanl.gov
MS-B244, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-12 14:02 ` James Theiler
@ 2003-05-12 21:56 ` Gerard Jungman
2003-05-12 23:34 ` James Theiler
0 siblings, 1 reply; 9+ messages in thread
From: Gerard Jungman @ 2003-05-12 21:56 UTC (permalink / raw)
To: gsl-discuss
On Mon, 2003-05-12 at 08:02, James Theiler wrote:
> A still-open question: If we provide
> pre-computed values, how many should we provide? For the straight (no
> logarithm) values, there is a natural cutoff at 170 since 170! (or is
> it 171!?) is the largest value that is a valid IEEE double precison
> number. But for the logs, we can assume the higher the cutoff the
> more often we'll be able to provide a fast precomputed value. We
> could easily provide thousands, and I think most computers nowadays
> would not begrudge the memory. But there may be other issues that I
> am not considering.
The natural cutoff is where Stirling's formula becomes good enough.
Computing that way will also be better than a memory access,
I imagine.
If we start using Stirling at 170 then it should be good
enough to take up to sixth order in the series correction.
So we can probably use the same arrays, etc.
I don't remember how the logic works in the factorial functions.
It might need a little tweaking to get optimal performance,
so it takes the right branch without too much fuss.
--
Gerard Jungman <jungman@lanl.gov>
Los Alamos National Laboratory
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-12 21:56 ` Gerard Jungman
@ 2003-05-12 23:34 ` James Theiler
2003-05-15 4:16 ` James Theiler
0 siblings, 1 reply; 9+ messages in thread
From: James Theiler @ 2003-05-12 23:34 UTC (permalink / raw)
To: Gerard Jungman; +Cc: gsl-discuss
On 12 May 2003, Gerard Jungman wrote:
] On Mon, 2003-05-12 at 08:02, James Theiler wrote:
]
]
] > A still-open question: If we provide
] > pre-computed values, how many should we provide? For the straight (no
] > logarithm) values, there is a natural cutoff at 170 since 170! (or is
] > it 171!?) is the largest value that is a valid IEEE double precison
] > number. But for the logs, we can assume the higher the cutoff the
] > more often we'll be able to provide a fast precomputed value. We
] > could easily provide thousands, and I think most computers nowadays
] > would not begrudge the memory. But there may be other issues that I
] > am not considering.
]
] The natural cutoff is where Stirling's formula becomes good enough.
good suggestion.
] Computing that way will also be better than a memory access,
] I imagine.
]
] If we start using Stirling at 170 then it should be good
] enough to take up to sixth order in the series correction.
] So we can probably use the same arrays, etc.
]
] I don't remember how the logic works in the factorial functions.
] It might need a little tweaking to get optimal performance,
] so it takes the right branch without too much fuss.
For large arguments, seems to be gsl_sf_lnfact_e -> gsl_sf_lngamma_e
-> lngamma_lanczos which implements a Stirling-like formula.
However, Lanczos requires two log evals (cf Stirling requires one),
and Lanczos and Stirling both require several terms of a polynomial
(Lanczos has eight terms). Going straight to Stirling from the ln_fact
code could save a few branches, and one logarithm, and possibly a few
polynomial terms. My intuition is that that won't beat a table
lookup, but it could be a substantial improvement. (And we have to
switch over from table lookup to large n formula at *some* point.) If
I get a chance, I'll give it a try.
jt
---------------------------------------------
James Theiler jt@lanl.gov
MS-B244, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-12 23:34 ` James Theiler
@ 2003-05-15 4:16 ` James Theiler
2003-05-19 9:39 ` Brian Gough
0 siblings, 1 reply; 9+ messages in thread
From: James Theiler @ 2003-05-15 4:16 UTC (permalink / raw)
To: Gerard Jungman; +Cc: gsl-discuss
On Mon, 12 May 2003, James Theiler wrote:
] On 12 May 2003, Gerard Jungman wrote:
]
] ] On Mon, 2003-05-12 at 08:02, James Theiler wrote:
] ]
] ]
] ] > A still-open question: If we provide
] ] > pre-computed values, how many should we provide? For the straight (no
] ] > logarithm) values, there is a natural cutoff at 170 since 170! (or is
] ] > it 171!?) is the largest value that is a valid IEEE double precison
] ] > number. But for the logs, we can assume the higher the cutoff the
] ] > more often we'll be able to provide a fast precomputed value. We
] ] > could easily provide thousands, and I think most computers nowadays
] ] > would not begrudge the memory. But there may be other issues that I
] ] > am not considering.
] ]
] ] The natural cutoff is where Stirling's formula becomes good enough.
]
] good suggestion.
]
] ] Computing that way will also be better than a memory access,
] ] I imagine.
] ]
] ] If we start using Stirling at 170 then it should be good
] ] enough to take up to sixth order in the series correction.
] ] So we can probably use the same arrays, etc.
] ]
] ] I don't remember how the logic works in the factorial functions.
] ] It might need a little tweaking to get optimal performance,
] ] so it takes the right branch without too much fuss.
]
] For large arguments, seems to be gsl_sf_lnfact_e -> gsl_sf_lngamma_e
] -> lngamma_lanczos which implements a Stirling-like formula.
] However, Lanczos requires two log evals (cf Stirling requires one),
] and Lanczos and Stirling both require several terms of a polynomial
] (Lanczos has eight terms). Going straight to Stirling from the ln_fact
] code could save a few branches, and one logarithm, and possibly a few
] polynomial terms. My intuition is that that won't beat a table
] lookup, but it could be a substantial improvement. (And we have to
] switch over from table lookup to large n formula at *some* point.) If
] I get a chance, I'll give it a try.
]
] jt
Hi Gerard and others,
I looked into timings for different ways of computing log(n!).
There are basically three approaches. One is direct table lookup,
which obviously works only for n less than the size of the table. Two
is to call gsl_sf_lngamma(n+1.0), which currently employs a Lanczos
approximation for all arguments except n=0 and n=1. A third approach,
suggested above, is to use the venerable Stirling's approximation [eg,
see Abramowitz and Stegen, 6.1.41].
Currently, gsl_sf_lnfact(n) uses table lookup for n<=170, and
the Lanczos formula for large n. A relevant point for comparison,
therefore, is n ~ 170, and at that value I find for my machine [*]
Lookup: 0.05 usec/eval
Lanczos: 1.03 usec/eval
Stirling: 0.34 usec/eval
(usec = 1e-6 sec) Actually, the value for Stirling varies from
0.3-0.4, depending on the number of terms in the polynomial correction
are used. I found that two terms were adequate for double precision
on my machine [*] for large numbers: n > 170.
That is, Lookup is 7x faster than Stirling, which in turn is 3x faster
than Lanczos. To my mind, this is an argument in favor of running up
the upper bound on the table for log(n!); further, whenever n exceeds
whatever upper bound we choose, we should use Stirling instead of
Lanczos for the large n result.
In fact, we might even consider Stirling instead of Lanczos for large
arguments of the gsl_sf_lngamma() function as well. Admittedly, this
does make the code that much more complicated...
regards,
jt
[*] my computer is a two-headed Intel Pentium linux box running at
933Mhz. Only one head is used in these computations. I would expect
the relative timings to be (more or less) invariant to computer type.
---------------------------------------------
James Theiler jt@lanl.gov
MS-B244, NIS-2, LANL tel: 505/665-5682
Los Alamos, NM 87545 fax: 505/665-4414
----- Space and Remote Sensing Sciences -----
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-15 4:16 ` James Theiler
@ 2003-05-19 9:39 ` Brian Gough
2003-05-19 18:55 ` Gerard Jungman
0 siblings, 1 reply; 9+ messages in thread
From: Brian Gough @ 2003-05-19 9:39 UTC (permalink / raw)
To: James Theiler; +Cc: Gerard Jungman, gsl-discuss
James Theiler writes:
> That is, Lookup is 7x faster than Stirling, which in turn is 3x faster
> than Lanczos. To my mind, this is an argument in favor of running up
> the upper bound on the table for log(n!); further, whenever n exceeds
> whatever upper bound we choose, we should use Stirling instead of
> Lanczos for the large n result.
A version with a larger lookup table could go in the new contrib/
directory. Some people might want to optimise for space instead of
speed.
I think 170 is a good natural limit.
--
Brian
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: faster log factorials
2003-05-19 9:39 ` Brian Gough
@ 2003-05-19 18:55 ` Gerard Jungman
0 siblings, 0 replies; 9+ messages in thread
From: Gerard Jungman @ 2003-05-19 18:55 UTC (permalink / raw)
To: Brian Gough; +Cc: James Theiler, gsl-discuss
On Mon, 2003-05-19 at 03:40, Brian Gough wrote:
>
> A version with a larger lookup table could go in the new contrib/
> directory. Some people might want to optimise for space instead of
> speed.
Ummm... nevertheless, the current stuff could be improved
without any loss. So don't be in a hurry to push everything
off into some other directory.
--
Gerard Jungman <jungman@lanl.gov>
Los Alamos National Laboratory
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2003-05-19 18:55 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-04-28 4:57 faster log factorials James Theiler
2003-05-10 19:09 ` Brian Gough
2003-05-10 19:29 ` Brian Gough
2003-05-12 14:02 ` James Theiler
2003-05-12 21:56 ` Gerard Jungman
2003-05-12 23:34 ` James Theiler
2003-05-15 4:16 ` James Theiler
2003-05-19 9:39 ` Brian Gough
2003-05-19 18:55 ` Gerard Jungman
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).