$result = 1;
$result *= $_ for 2..$end;
[download]

3. As the aforementioned node demonstrated, tail call recursion isn't all that fast in the current perl5. Speeding it up probably requires hacking on the core. If you need to compute factorials repeatedly in a recursive fashion, consider using memoization. Memoization builds a lookup table that could even beat the iterative scheme in certain situations.

Correction. Iterative is not the fastest non-lookup algorithm in Perl (at least when you get to big integers). A divide-and-conquer recursive strategy can out-scale it. The reason is that in an iterative strategy you wind up doing many multiplications of a very large number with a small one. Since the large one has O(n*log(n)) digits each time, that winds up being slightly slower than quadratic.

I would be surprised if divide and conquer were the absolute best strategy. But in pure Perl, given the overhead of Perl, I don't think that you'll easily find a faster algorithm.

I agree that a divide and conquer algorithm will eventually win for large numbers, but there is a big multiplier to overcome at moderate numbers:

use Benchmark qw(:all);

sub recurse {
  #divide and conquer
  unshift @_, 1 if 2 != @_;
  my ($m, $n) = @_;

  if ($m < $n) {
    my $k = int($m/2 + $n/2);
    return recurse($m, $k) * recurse($k+1, $n);
  }
  else {
    return $m
  }
}

sub iterate {
   my $result = 1;
   $result *= $_ for 2..shift;
   return $result
}

cmpthese(10_000, {
        'recurse' => sub { recurse( 160) },
        'iterate' => sub { iterate( 160) },
    });
[download]

yields

Benchmark: timing 10000 iterations of iterate, recurse...
   iterate:  2 wallclock secs ( 1.53 usr +  0.00 sys =  1.53 CPU) @ 65
+35.95/s (n=10000)
   recurse: 23 wallclock secs (22.82 usr +  0.00 sys = 22.82 CPU) @ 43
+8.21/s (n=10000)
          Rate recurse iterate
recurse  438/s      --    -93%
iterate 6536/s   1392%      --
[download]

If one uses Math::BigInt for larger factorials, then results even out a bit because of all the function calls needed to do multiplication. But if one can stick to the builtin operators and minimize function calls, it is usually a huge win in perl5.

-Mark

Should be pretty quick.

Better?

I don't think throwing 170 scalars onto the stack every time in order to pick one is going to be as good as using an existing array.

Good point. Updated.

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail

Um, nope, just the same. Now you're just calling the FACTORIALS subroutine to put 170 scalars on the stack. The ()[] construct is always going to do that. You have to use @foo[] or $foo->[] to access an existing array. Which you have to have constructed using some variant of @foo = (0,1,etc) or $foo = [0, 1, etc.]. And you have to arrange to do that only once (generally outside the routine, but it can be done inside if you're tricksie), or you're still in the same boat of constructing your list at run time.

Maybe?

use constant FACTORIALS => [ qw[
     0 1 2 6 24 120 720 5040 40320 362880 3628800 39916800 479001600 6
+227020800
     87178291200 1307674368000 20922789888000 355687428096000 64023737
+05728000 
     1.21645100408832e+017 2.43290200817664e+018 5.109094217170944e+01
+9 
     1.124000727777608e+021 2.585201673888498e+022 6.204484017332394e+
+023 
     1.551121004333099e+025 4.032914611266057e+026 1.088886945041835e+
+028 
     3.048883446117138e+029 8.841761993739701e+030 2.65252859812191e+0
+32 
     8.222838654177922e+033 2.631308369336935e+035 8.683317618811886e+
+036 
     2.952327990396041e+038 1.033314796638614e+040 3.719933267899012e+
+041 
     1.376375309122634e+043 5.23022617466601e+044 2.039788208119744e+0
+46 
     8.159152832478977e+047 3.34525266131638e+049 1.40500611775288e+05
+1 
     6.041526306337383e+052 2.658271574788449e+054 1.196222208654802e+
+056 
     5.502622159812089e+057 2.586232415111682e+059 1.241391559253607e+
+061 
     6.082818640342675e+062 3.041409320171338e+064 1.551118753287382e+
+066 
     8.065817517094388e+067 4.274883284060026e+069 2.308436973392414e+
+071 
     1.269640335365828e+073 7.109985878048635e+074 4.052691950487722e+
+076 
     2.350561331282879e+078 1.386831185456899e+080 8.320987112741392e+
+081 
     5.075802138772248e+083 3.146997326038794e+085 1.98260831540444e+0
+87 
     1.268869321858842e+089 8.247650592082472e+090 5.443449390774431e+
+092 
     3.647111091818868e+094 2.480035542436831e+096 1.711224524281413e+
+098 
     1.197857166996989e+100 8.504785885678622e+101 6.123445837688608e+
+103 
     4.470115461512683e+105 3.307885441519386e+107 2.480914081139539e+
+109 
     1.88549470166605e+111 1.451830920282858e+113 1.13242811782063e+11
+5 
     8.946182130782973e+116 7.156945704626378e+118 5.797126020747366e+
+120 
     4.75364333701284e+122 3.945523969720657e+124 3.314240134565352e+1
+26 
     2.817104114380549e+128 2.422709538367272e+130 2.107757298379527e+
+132 
     1.854826422573984e+134 1.650795516090845e+136 1.485715964481761e+
+138 
     1.352001527678402e+140 1.24384140546413e+142 1.156772507081641e+1
+44 
     1.087366156656742e+146 1.032997848823905e+148 9.916779348709491e+
+149 
     9.619275968248206e+151 9.426890448883242e+153 9.33262154439441e+1
+55 
     9.33262154439441e+157 9.425947759838354e+159 9.614466715035121e+1
+61 
     9.902900716486175e+163 1.029901674514562e+166 1.08139675824029e+1
+68 
     1.146280563734708e+170 1.226520203196137e+172 1.324641819451828e+
+174 
     1.443859583202493e+176 1.588245541522742e+178 1.762952551090244e+
+180 
     1.974506857221073e+182 2.231192748659812e+184 2.543559733472186e+
+186 
     2.925093693493014e+188 3.393108684451897e+190 3.969937160808719e+
+192 
     4.684525849754288e+194 5.574585761207603e+196 6.689502913449124e+
+198 
     8.09429852527344e+200 9.875044200833598e+202 1.214630436702533e+2
+05 
     1.50614174151114e+207 1.882677176888925e+209 2.372173242880046e+2
+11 
     3.012660018457658e+213 3.856204823625803e+215 4.974504222477286e+
+217 
     6.466855489220472e+219 8.471580690878817e+221 1.118248651196004e+
+224 
     1.487270706090685e+226 1.992942746161518e+228 2.69047270731805e+2
+30 
     3.659042881952547e+232 5.01288874827499e+234 6.917786472619486e+2
+36 
     9.615723196941086e+238 1.346201247571752e+241 1.89814375907617e+2
+43 
     2.695364137888161e+245 3.854370717180071e+247 5.550293832739301e+
+249 
     8.047926057471987e+251 1.17499720439091e+254 1.727245890454638e+2
+56 
     2.556323917872864e+258 3.808922637630567e+260 5.713383956445851e+
+262 
     8.627209774233235e+264 1.311335885683452e+267 2.006343905095681e+
+269 
     3.089769613847349e+271 4.789142901463391e+273 7.471062926282891e+
+275 
     1.172956879426414e+278 1.853271869493734e+280 2.946702272495037e+
+282 
     4.714723635992059e+284 7.590705053947215e+286 1.229694218739449e+
+289 
     2.004401576545302e+291 3.287218585534295e+293 5.423910666131586e+
+295 
     9.003691705778433e+297 1.503616514864998e+300 2.526075744973197e+
+302 
     4.269068009004703e+304 7.257415615307994e+306 
] ];
     
sub factorial{ $_[ 0 ] < 171 ? FACTORIALS->[  $_[ 0 ] ] : '#INF'; }
[download]

---

Examine what is said, not who speaks.

"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail

0! == 1

Only by definition and because it's useful. 0! can just as easily be defined as 0, with different results.

------
We are the carpenters and bricklayers of the Information Age.

Then there are Damian modules.... *sigh* ... that's not about being less-lazy -- that's about being on some really good drugs -- you know, there is no spoon. - flyingmoose

sub fact {
  my $n = shift;
  return 1 if $n <= 1;
  return 2 if $n == 2;
  return "more than three";
}
[download]