Catalan numbers: Difference between revisions

Content deleted Content added

Inline

@@ Line 2,024: / Line 2,024: @@
 =={{header|Perl}}==
-<lang perl>sub f { $_[0] ? $_[0] * f($_[0]-1) : 1 }
+<lang perl>sub factorial { my $f = 1; $f *= $_ for 2 .. $_[0]; $f; }
-sub catalan { f(2 * $_[0]) / f($_[0]) / f($_[0]+1) }
+sub catalan {
+  my $n = shift;
+  factorial(2*$n) / factorial($n+1) / factorial($n);
+}
 print "$_\t@{[ catalan($_) ]}\n" for 0 .. 20;</lang>
@@ Line 2,036: / Line 2,039: @@
 # most of the time is spent displaying the long numbers, actually
+print "$_\t", catalan($_), "\n" for 0 .. 10000;</lang>
+That has two downsides: high memory use and slow access to an isolated large value.  Using a fast binomial function can solve both these issues.  Its downsides are being somewhat slower when doing a consecutive range, and it relies on the platform having the GMP library.
+{{libheader|ntheory}}
+<lang perl>use ntheory qw/binomial/;
+sub catalan {
+  my $n = shift;
+  binomial(2*$n,$n)/($n+1);
+}
 print "$_\t", catalan($_), "\n" for 0 .. 10000;</lang>