From: tchow@math.lsa.umich.edu (Timothy Chow) Newsgroups: sci.math Subject: Re: Know a fast calculation of sin(x)? Date: 9 Sep 1995 00:53:08 GMT In article <42qe1n$bbd@wdl1.wdl.loral.com>, Mark A Biggar wrote: >In article <42pkkd$egj@oban.cc.ic.ac.uk> "Mr Adrian P. Umpleby" writes: >>Given X to N decimal places, does anybody out there know >>of a fast method ( e.g. < O(N^2) ) to find sin(X) to N >>decimal places? > >Look for someting called the CORDIC algorithm it generates the sin and cos >of an angle simultaniously using only 2*N tables lookups and 2*N >additions/subtractions. Here is some more information about CORDIC, from an old sci.math article. From knighten@ssd.intel.com Wed Aug 31 18:31:36 EDT 1994 Article: 61830 of sci.math Newsgroups: sci.math Path: galois!bloom-beacon.mit.edu!grapevine.lcs.mit.edu!uhog.mit.edu!news.kei.com!ssd.intel.com!ssdintel!knighten From: knighten@ssd.intel.com (Robert L. Knighten) Subject: Re: How calculators compute sin(x) In-Reply-To: pmohseni@iastate.edu's message of 30 Aug 94 18:35:05 GMT Message-ID: Sender: usenet@SSD.intel.com Nntp-Posting-Host: tualatin Reply-To: knighten@ssd.intel.com (Bob Knighten) Organization: Supercomputer System Division, Intel References: Date: Wed, 31 Aug 1994 21:46:42 GMT Lines: 71 Status: RO CORDIC and Elementary Function Computation CORDIC stands for COordinate Rotation DIgital Computer. It was initially a special purpose digital computer for real-time aircraft navigation. It has come to stand for the method embodied in this computer. That method is based on the observation that the sin of 128 degrees is the y-coordinate of the result of rotating the vector (1,0) through 128 degrees and that can be efficiently computed as a composition of rotations through smaller angles: 128 ~ 90 + 45 - 22.5 + 11.2 + 5.7 - 2.9 + 1.5 - 0.8 and these rotations can be very efficiently computed. This was generalized to other functions by considering vectors in the complex plane and complex rotations. The information about the CORDIC algorithm, which is used in virtually all scientific calculators and very seldom in computers, can be found in: Jack E. Volder, The CORDIC Trignometric Computing Technique IRE Trans. Electronic Computing, EC-8 (1959) pp. 330-334 The original paper. J. E. Meggitt, Pseudo Division and Pseudo Multiplication Processes IBM J. of Res. and Devel., (1962) pp. 210-226 Extension of the CORDIC method to division and multiplication. R. J. Linhardt and H. S. Miller, Digit-by-Digit Transcendental-Function Computation. RCA Review, 30 (1969) pp. 209-247 This considers a somewhat different algorithm, but is a good survey article and has a nice comparison with polynomial approximations. J. S. Walther, A Unified Algorithm for Elementary Functions Spring Joint Computer Conference (1971) pp. 379-385 The paper by Walther is particularly interesting as it describes a unified method for computing the trignometric functions, the hyperbolic functions, exp, ln and square root. This is the base for all of the Hewlett-Packard scientific calculators. The recently developed table based methods are discussed in R. C. Agarwal, J. W. Cooley, F. G. Gustavson, J. B. Gustavson, J. B. Shearer, G. Slishman and B. Tuckerman, New Scalar and Vector Elementary Functions for the IBM System/370. IBM J. Res. Develop., 30 (1986) pp. 126-144 S. Gal, Computing Elementary Functions: A New Approach for Achieving High Accuracy and Good Performance. Proceedings of the International Scientific Symposium of IBM, March 12-14, 1985 (Bad Neuenahr, Germany) A good general discussion of the methods for computing elementary functions is in W. J. Cody, Software for the Elementary Functions in MATHEMATICAL SOFTWARE, J. Rice, ed., Academic Press, Inc. (1971) pp. 171-186 and the usual reference for a discusion of common algorithms for polynomial approximation methods from a how-to-do-it perspective is W. J. Cody and W. Waite, SOFTWARE MANUAL FOR THE ELEMENTARY FUNCTIONS Prentice-Hall, 1980 -- Robert L. Knighten | knighten@ssd.intel.com Intel Supercomputer Systems Division | CO1-05 | 15201 N.W. Greenbrier Pkwy. | (503) 629-4315 Beaverton, Oregon 97006 | (503) 629-9147 [FAX] -- Tim Chow tycchow@math.mit.edu Where a calculator on the ENIAC is equipped with 18,000 vacuum tubes and weighs 30 tons, computers in the future may have only 1,000 vacuum tubes and weigh only 1 1/2 tons. ---Popular Mechanics, March 1949