home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / comp / parallel / 3084 < prev    next >
Encoding:
Text File  |  1993-01-28  |  1.5 KB  |  43 lines
  1. Newsgroups: comp.parallel
  2. Path: sparky!uunet!destroyer!gatech!hubcap!fpst
  3. From: maniattb@cs.rpi.edu (Bill Maniatty)
  4. Subject: Re: Wanted: Folk Theormes in Fortran Programming
  5. Message-ID: <1993Jan28.142743.24324@hubcap.clemson.edu>
  6. Apparently-To: comp-parallel@cis.ohio-state.edu
  7. Sender: fpst@hubcap.clemson.edu (Steve Stevenson)
  8. Nntp-Posting-Host: sage.cs.rpi.edu
  9. Organization: Clemson University
  10. References:  <1993Jan27.123645.8334@hubcap.clemson.edu>
  11. Date: Thu, 28 Jan 1993 03:12:31 GMT
  12. Approved: parallel@hubcap.clemson.edu
  13. Lines: 28
  14.  
  15. Horner's method for polynomial evaluation is usually a good idea.
  16.  
  17. (I'm not a Fortran Expert, so I'll use psuedocode)
  18. f = a[0] + a[1] * x + a[2] * x**2 + a[3] * x**3 + ... + a[n] * x ** n
  19.  
  20. The brute force method takes 0 + 1 + 2 + ... + n multiplies, to compute the
  21. various powers of x, that is O(n**2) multiplications.
  22.  
  23. We now consider a smarter way, which uses intermediate results:
  24.  
  25. f = a[0] + x * (a[1] + x *( a[2] + x * ( ... )))
  26.  
  27. We see that we have O(n) multiplications, with no extra additions.
  28. I suspect that this has the added bonus of being better numerically in that
  29. fewer multiplications will tend to reduce roundoff error.
  30.  
  31. You can also do some smart things like eliminating induction variables,
  32. constant subexpression elimination, common subexpression elimination,
  33. dead code elimination, etc.  This can be found in the Red Dragon book
  34. by Aho, Sethi, and Ullman.  The basic ideas are simple, but the implementation
  35. details can be a bit tricky.
  36.  
  37. Bill
  38. -- 
  39. |
  40. |    maniattb@cs.rpi.edu - in real life Bill Maniatty
  41. |
  42.  
  43.