From: Richard Kreckel <Richard.Kreckel@uni-mainz.de>
Date: Mon, 23 Jul 2001 21:32:45 +0000 (+0000)
Subject: - comment: elaborate on matrix::pow().
X-Git-Tag: release_0-9-2~22
X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=commitdiff_plain;h=1b5601580eba6925b0af9408c56d6b2027b56013;hp=e64bfb923b62db2402ac8a078732e8f987bc6ec0

- comment: elaborate on matrix::pow().
---

diff --git a/ginac/matrix.cpp b/ginac/matrix.cpp
index 15ebd9aa..ca574cc3 100644
--- a/ginac/matrix.cpp
+++ b/ginac/matrix.cpp
@@ -612,8 +612,11 @@ matrix matrix::pow(const ex & expn) const
 			for (unsigned r=0; r<row; ++r)
 				result(r,r) = _ex1();
 			numeric b(1);
-			// this loop computes the representation of k in base 2 and
-			// multiplies the factors whenever needed:
+			// This loop computes the representation of k in base 2 from right
+			// to left(!) and multiplies the factors whenever needed.  Note
+			// that this is not entirely optimal but close to optimal and
+			// "better" algorithms are much harder to implement.  (See Knuth,
+			// TAoCP2, section "Evaluation of Powers" for a good discussion.)
 			while (b.compare(k)<=0) {
 				b *= numeric(2);
 				numeric r(mod(k,b));