Re: HELP WANTED ON ALGORITHMS
Message #19 Posted by Eric Smith on 27 Apr 2013, 12:49 p.m.,
in response to message #18 by Eddie W. Shore
Usually CORDIC isn’t used for logs and exponentials, although it is possible to do so by using hyperbolic CORDIC. CORDIC is in the general class of shift-and-add algorithms, and there is a simpler one for logs and exponential first published in 1624, only ten years after the invention of logarithms by Napier. I’m not sure whether the HP 9100A (1968) used Briggs’ algorithm, but all of HP’s handheld and handheld-derived calculators from the HP-35 (1972) through the Saturn-based and Saturn-emulating calculators have used it. Recent HP-designed calculators such as the HP 10bII+, 20b, 30b, and 49gII apparently use a math library based on that from Saturn calculators, so they presumably also use Briggs’ algorithm.
There is a good description of Briggs’ algorithm on Jacques Laporte’s “Briggs and the HP35” web page.
Another excellent reference for algorithms for transcendental functions is Elementary Functions: Algorithms and Implementations by Jean-Michel Muller, second edition, which covers many classes of algorithms including shift-and-add (Briggs’, CORDIC, and others), and has especially good coverage of accurate argument range reduction algorithms.
It should be noted that the HP algorithms for sine and cosine use CORDIC, but not in the most basic method normally described. Instead, they compute the tangent (or cotangent), and use an identity to compute the sine (or cosine) from it. This avoids an issue with each CORDIC iteration effectively multiplying the resulting sine and cosine by a scale factor; by using tangent (or cotangent), these scale factors cancel out. In binary CORDIC, the number of CORDIC iteration is fixed, so the result can be multiplied by the inverse of the product of the scale factors, which is constant. In decimal CORDIC as implemented by HP, the number of CORDIC iterations is variable, so it would take more work to compensate for the non-constant product of the scale factors.
For specifics of the algorithms used by HP, see:
- “Algorithms and Accuracy in the HP-35 Scientific Calculator”, David S. Cochran, HP Journal, June 1972, pp. 10-11
- “The New Accuracy: Making 2^3 = 8”, Dennis W. Harms, HP Journal, November 1976, pp. 16-17
- “Personal Calculator Algorithms I: Square Roots”, William E. Egbert, HP Journal, May 1977, pp. 22-24
- “Personal Calculator Algorithms II: Trigonometric Functions”, William E. Egbert, HP Journal, June 1977, pp. 17-20
- “Personal Calculator Algorithms III: Inverse Trigonometric Functions”, William E. Egbert, HP Journal, November 1977, pp. 22-23
- “Personal Calculator Algorithms IV: Logarithmic Functions”, William E. Egbert, HP Journal, April 1978, pp. 29-32
Edited: 27 Apr 2013, 1:04 p.m.