home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / symbolic / 3427 < prev    next >
Encoding:
Internet Message Format  |  1993-01-12  |  4.9 KB
  1. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!sun-barr!olivea!mintaka.lcs.mit.edu!zurich.ai.mit.edu!jaffer
  2. From: jaffer@zurich.ai.mit.edu (Aubrey Jaffer)
  3. Newsgroups: sci.math.symbolic
  4. Subject: Re: Book "Algorithms for Computer Algebra" Authors
  5. Message-ID: <JAFFER.93Jan12212915@camelot.ai.mit.edu>
  6. Date: 13 Jan 93 02:29:15 GMT
  7. References: <JAFFER.93Jan3223634@camelot.ai.mit.edu> <1993Jan4.115541.28393@greco-prog.fr>
  8. Sender: news@mintaka.lcs.mit.edu
  9. Organization: M.I.T. Artificial Intelligence Lab.
  10. Lines: 104
  11. In-Reply-To: cohen@alioth.greco-prog.fr's message of 4 Jan 93 11:55:41 GMT
  12.  
  13. In article <1993Jan4.115541.28393@greco-prog.fr> cohen@alioth.greco-prog.fr (Henri Cohen) writes:
  14.  
  15.    In article <JAFFER.93Jan3223634@camelot.ai.mit.edu>,
  16.    jaffer@zurich.ai.mit.edu (Aubrey Jaffer) writes:
  17.    |> I have found some minor errors in "Algorithms for Computer Algebra".
  18.  
  19.    Would you care to share them with the Net, or are they so minor
  20.    that they do not really matter if one wants to use the algorithms
  21.    given in the book?
  22.  
  23. Stephen R. Czapor has been kind enough to respond to my message:
  24.  
  25.  From: steve@ramsey.cs.laurentian.ca (Stephen R. Czapor)
  26.  Subject: Re:  Algorithms for Computer Algebra.
  27.  
  28.     >From jaffer@martigny.ai.mit.edu Mon Jan  4 13:59:33 1993
  29.     >Subject: Algorithms for Computer Algebra.
  30.     >
  31.     >I am reading with great interest your recent book.  I have only
  32.     >reached Chapter 5 but I thought I would point out the following points
  33.     >while they are still fresh in my mind.
  34.     >
  35.     >There seems to be a consistent typsetting error for exponents of
  36.     >subscripted variables.  The exponents of subscripted variables are
  37.     >surrounded by parenthesis.  An example of this is at the top of page
  38.     >116.  This can be confusing as some authors (for example J.F.Ritt in
  39.     >"Differential Algebra") use this notation to denote nth derivative.
  40.     >
  41.     >Although figuring prominently in the discussion in Chapter 2, the
  42.     >notations D(x), D[[x]], D((x)), D<x>, and F_d do not appear in the
  43.     >NOTATION glossary.  It would be nice if these notations were also
  44.     >collected together in a box somewhere in Chapter 2 as well.
  45.     > . . . .
  46.     > . . . .
  47.     >----------------------------------------------------------------
  48.  
  49.  On the first point:  the superscripts in parentheses are not exponents,
  50.  but meant to indicate "order" in some sense.  On p. 112, for example,
  51.    (k)
  52.   b    is for an order k (k digit) B-adic expansion of an integer.
  53.          (i)
  54.  On p. 116, c    is the k-th coefficient of a power series expansion.
  55.          k
  56.  
  57.  On the second:  I agree that these things should have been included,
  58.  but were missed.  I'll put them in a list with others I've noticed
  59.  for the second edition [ :) ] .  As for an additional table in Chap. 2,
  60.  that may be a good idea - but this must be balanced against the fact
  61.  that it's already a fairly long chapter.
  62.  
  63.  I'll leave the other points for my co-authors.
  64.  In the meantime, thanks very much for the feedback!
  65.  
  66. Here is the rest of my message to the authors:
  67.  
  68. In chapter 4 you describe both the "Lagrange inversion formula" and
  69. "Newton's method for solving P(y)=0".  Although separated in the
  70. chapter, both of these algorithms seem to accomplish the same
  71. computation.  In other cases where you have 2 algorithms for the same
  72. problem you present cost analysis for the algorithms (which I
  73. appreciate), yet these 2 are not compared.
  74.  
  75. In Chapter 4 "Integers mod n Arithmetic" you state "The operations of
  76. addition, subtraction and multiplication in Zn are straightforward,
  77. regardless of the representation used."  This is not true for
  78. multiplication if one is using fixed precision numbers.  An algorithm
  79. for modular multiplication using fixed precision integers is given in
  80. a package referencing:
  81.   L'Ecuyer, P. and Cote, S. "Implementing a Random Number Package
  82.   with Splitting Facilities." ACM Transactions on Mathematical
  83.   Software, 17:98-111 (1991)
  84.  
  85. My version of this algorithm in Scheme follows:
  86.  
  87. ;;; modular:r = 2**((nb-2)/2) where nb = number of bits in a word.
  88. (define modular:r
  89.   (ash 1 (quotient (integer-length most-positive-fixnum) 2)))
  90. (define (modular:* m a b)
  91.   (let ((a0 a)
  92.     (p 0))
  93.     (cond ((< a modular:r))
  94.       ((< b modular:r) (set! a b) (set! b a0) (set! a0 a))
  95.       (else
  96.        (set! a0 (modulo a modular:r))
  97.        (let ((a1 (quotient a modular:r))
  98.          (qh (quotient m modular:r))
  99.          (rh (modulo m modular:r)))
  100.          (cond ((>= a1 modular:r)
  101.             (set! a1 (- a1 modular:r))
  102.             (set! p (modulo (- (* modular:r (modulo b qh))
  103.                        (* (quotient b qh) rh)) m))))
  104.          (cond ((not (zero? a1))
  105.             (let ((q (quotient m a1)))
  106.               (set! p (- p (* (quotient b q) (modulo m a1))))
  107.               (set! p (modulo (+ (if (positive? p) (- p m) p)
  108.                      (* a1 (modulo b q))) m)))))
  109.          (set! p (modulo (- (* modular:r (modulo p qh))
  110.                 (* (quotient p qh) rh)) m)))))
  111.     (if (zero? a0)
  112.     p
  113.     (let ((q (quotient m a0)))
  114.       (set! p (- p (* (quotient b q) (modulo m a0))))
  115.       (modulo (+ (if (positive? p) (- p m) p)
  116.              (* a0 (modulo b q))) m)))))
  117.