| CC: | stefan.petrea [...] gmail.com |
| Subject: | [PATCH] inefficient recursion in CM::Polynomial::Chebyshev |
The generation of Chebyshev polynomials with a recursion like it is
implemented in CM-Polynomial-0.94 is very inefficient. Its cost grows
exponentially with increasing degree.
The recursion formula can be unfolded to an iteration very easily though.
See the patch below.
By the way, there is a funny typo in the documentation of CM::Polynomial.
"between brides and permutations" should presumably read "between braids
and permutations".
-Martin
| Subject: | cmp-cheb-recursion.patch |
diff -rup CM-Permutation-0.94.orig/lib/CM/Polynomial/Chebyshev.pm CM-Permutation-0.94/lib/CM/Polynomial/Chebyshev.pm
--- CM-Permutation-0.94.orig/lib/CM/Polynomial/Chebyshev.pm 2011-10-29 12:18:31.000000000 +0200
+++ CM-Permutation-0.94/lib/CM/Polynomial/Chebyshev.pm 2012-08-13 10:04:31.000000000 +0200
@@ -40,13 +40,15 @@ sub cheb {
my ($n) = @_;
#print "cheb $n\n";
- return Math::Polynomial->new(1)
- if $n == 0;
+ my $t0 = Math::Polynomial->new(1);
+ return $t0 if $n == 0;
- return Math::Polynomial->new(0,1)
- if $n == 1;
-
- return Math::Polynomial->new(0,2) * cheb($n-1) - cheb($n-2);
+ my $t1 = Math::Polynomial->new(0, 1);
+ my $two_x = $t1 + $t1;
+ while (--$n > 0) {
+ ($t1, $t0) = ($two_x * $t1 - $t0, $t1);
+ }
+ return $t1;
}
1;