🚀 go-pugleaf

In article <1993Jan4.115541.28393@greco-prog.fr> cohen@alioth.greco-prog.fr (Henri Cohen) writes:

   In article <JAFFER.93Jan3223634@camelot.ai.mit.edu>,
   jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes:
   |> I have found some minor errors in "Algorithms for Computer Algebra".

   Would you care to share them with the Net, or are they so minor
   that they do not really matter if one wants to use the algorithms
   given in the book?

Stephen R. Czapor has been kind enough to respond to my message:

 From: steve@ramsey.cs.laurentian.ca (Stephen R. Czapor)
 Subject: Re:  Algorithms for Computer Algebra.

    >From jaffer@martigny.ai.mit.edu Mon Jan  4 13:59:33 1993
    >Subject: Algorithms for Computer Algebra.
    >
    >I am reading with great interest your recent book.  I have only
    >reached Chapter 5 but I thought I would point out the following points
    >while they are still fresh in my mind.
    >
    >There seems to be a consistent typsetting error for exponents of
    >subscripted variables.  The exponents of subscripted variables are
    >surrounded by parenthesis.  An example of this is at the top of page
    >116.  This can be confusing as some authors (for example J.F.Ritt in
    >"Differential Algebra") use this notation to denote nth derivative.
    >
    >Although figuring prominently in the discussion in Chapter 2, the
    >notations D(x), D[[x]], D((x)), D<x>, and F_d do not appear in the
    >NOTATION glossary.  It would be nice if these notations were also
    >collected together in a box somewhere in Chapter 2 as well.
    > . . . .
    > . . . .
    >----------------------------------------------------------------

 On the first point:  the superscripts in parentheses are not exponents,
 but meant to indicate "order" in some sense.  On p. 112, for example,
   (k)
  b    is for an order k (k digit) B-adic expansion of an integer.
	     (i)
 On p. 116, c    is the k-th coefficient of a power series expansion.
	     k

 On the second:  I agree that these things should have been included,
 but were missed.  I'll put them in a list with others I've noticed
 for the second edition [ :) ] .  As for an additional table in Chap. 2,
 that may be a good idea - but this must be balanced against the fact
 that it's already a fairly long chapter.

 I'll leave the other points for my co-authors.
 In the meantime, thanks very much for the feedback!

Here is the rest of my message to the authors:

In chapter 4 you describe both the "Lagrange inversion formula" and
"Newton's method for solving P(y)=0".  Although separated in the
chapter, both of these algorithms seem to accomplish the same
computation.  In other cases where you have 2 algorithms for the same
problem you present cost analysis for the algorithms (which I
appreciate), yet these 2 are not compared.

In Chapter 4 "Integers mod n Arithmetic" you state "The operations of
addition, subtraction and multiplication in Zn are straightforward,
regardless of the representation used."  This is not true for
multiplication if one is using fixed precision numbers.  An algorithm
for modular multiplication using fixed precision integers is given in
a package referencing:
  L'Ecuyer, P. and Cote, S. "Implementing a Random Number Package
  with Splitting Facilities." ACM Transactions on Mathematical
  Software, 17:98-111 (1991)

My version of this algorithm in Scheme follows:

;;; modular:r = 2**((nb-2)/2) where nb = number of bits in a word.
(define modular:r
  (ash 1 (quotient (integer-length most-positive-fixnum) 2)))
(define (modular:* m a b)
  (let ((a0 a)
	(p 0))
    (cond ((< a modular:r))
	  ((< b modular:r) (set! a b) (set! b a0) (set! a0 a))
	  (else
	   (set! a0 (modulo a modular:r))
	   (let ((a1 (quotient a modular:r))
		 (qh (quotient m modular:r))
		 (rh (modulo m modular:r)))
	     (cond ((>= a1 modular:r)
		    (set! a1 (- a1 modular:r))
		    (set! p (modulo (- (* modular:r (modulo b qh))
				       (* (quotient b qh) rh)) m))))
	     (cond ((not (zero? a1))
		    (let ((q (quotient m a1)))
		      (set! p (- p (* (quotient b q) (modulo m a1))))
		      (set! p (modulo (+ (if (positive? p) (- p m) p)
					 (* a1 (modulo b q))) m)))))
	     (set! p (modulo (- (* modular:r (modulo p qh))
				(* (quotient p qh) rh)) m)))))
    (if (zero? a0)
	p
	(let ((q (quotient m a0)))
	  (set! p (- p (* (quotient b q) (modulo m a0))))
	  (modulo (+ (if (positive? p) (- p m) p)
		     (* a0 (modulo b q))) m)))))