home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #23 / NN_1992_23.iso / spool / sci / math / 13315 < prev    next >
Encoding:
Internet Message Format  |  1992-10-16  |  2.5 KB
  1. Path: sparky!uunet!mcsun!uknet!pavo.csi.cam.ac.uk!camcus!cet1
  2. From: cet1@cus.cam.ac.uk (C.E. Thompson)
  3. Newsgroups: sci.math
  4. Subject: Re: Looking for fast methods of computing PI
  5. Message-ID: <1992Oct16.145024.14509@infodev.cam.ac.uk>
  6. Date: 16 Oct 92 14:50:24 GMT
  7. References: <1992Oct13.025820.4593@eecs.nwu.edu> <-g1zrgc@rpi.edu> <1992Oct16.111222.4303@CSD-NewsHost.Stanford.EDU>
  8. Sender: news@infodev.cam.ac.uk (USENET news)
  9. Organization: U of Cambridge, England
  10. Lines: 40
  11. Nntp-Posting-Host: grus.cus.cam.ac.uk
  12.  
  13. In article <1992Oct16.111222.4303@CSD-NewsHost.Stanford.EDU>,
  14. pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt) writes, as part of a 
  15. very interesting posting:
  16. |> 
  17. |> Before Lagrange-Gauss-Salamin, all improvements over Archimedes were
  18. |> mere constant factors, as follows.
  19. |> 
  20. |>      Inventor          Speed in bits/op     Method
  21. |> 
  22. |>      Archimedes, c.250 BC    1       half-angle method
  23. |>      Vieta, 1593             1       product(r=sqrt((r+1)/2))
  24. |>      Descartes, < 1650       1       constant perimeter method
  25. |>      Newton, 1666            2       series related to arcsin x
  26. |>      Sharp, 1705             1.585   Gregory(sqrt(3))
  27. |>      Machin, 1706            3.589   Gregory(5, 239)
  28. |>      Stoermer, 1896          3.168   Gregory(8, 57, 239)
  29. |> 
  30. |> Here Gregory(a1,a2,...,an) is the formula pi/4 = a linear integer
  31. |> combination of the arctan(1/ai)'s, e.g.  pi/4 = 6 arctan(1/8) + 2
  32. |> arctan(1/57) + 4 arctan(1/239).  Note that both Sharp's and Stoermer's
  33. |> "improvements" weren't, showing what happens when you don't do an
  34. |> explicit complexity analysis.  Both Sharp's and Machin's methods were
  35. |> used in early computer evaluations of pi.  For some reason Stoermer's
  36. |> method was later chosen by Shanks and Wrench over Machin's, perhaps due
  37. |> to inappropriate focus on the dominant arctan: arctan(1/8) must have
  38. |> seemed more promising than arctan(1/5).
  39.  
  40. Do not the detailed mechanics of dividing by small integers with particular
  41. hardware provide some reasons why theoretical bit complexity might be
  42. ignored? Certainly Machin's formula was considered particularly suitable
  43. for hand computation (in decimal, of course) because the divisions by 5 were
  44. easy. I can imagine a similar argument being used in favour of Stoermer's
  45. formula w.r.t. division by 8 on binary computers.
  46.  
  47. One would also like to know: are there Gregory(a1,...,an) methods with
  48. arbitrarily high bits/op? If not, are there any better than Machin's?
  49.  
  50. Chris Thompson
  51. JANET:    cet1@uk.ac.cam.phx
  52. Internet: cet1@phx.cam.ac.uk
  53.