Re: RPN, transcendentals, reverseengineering, etc Message #4 Posted by Bill Wiese on 26 Dec 2002, 2:59 p.m., in response to message #3 by Glen Kilpatrick
Hi..
>[Glen Kilpatrick wrote:]
>It's not conceivable that contemporary engineering
>would be needing manuals in order to reverseengineer
>RPN. There are still too many "examples" already extant
>(although I've always wondered if HP used Chebyshev
>polynomials to calculate transendental functions, some >references to internal specs, *not* in manuals, but HP
>probably has the originals, might clarify exactly the
>methods used*
Yes, whether the calc is RPN or Algebraic is independent of the algorithms used for log/trig functions. And any mildly competent programmer can create an RPNlike shell, etc in the C language. The orig challenge in doing the orig HP or even TI calcs was to do a whole calc  including log/trig funcs  in about 12 Kwords of ROM. (As I recall, roughly equivalent functionality TI calcs took more ROM space than
similar HPs becuase TI used a kludgy 4bit microcontroller, while HP's instruction set was designed from the outset to save code space for calc applications.)
Even today, I'd say that a lot of Asian calc mfgrs don't necessarily know a whole lot about their algorithms.
HP, at least thru the 41 series, seems to use CORDIC shift/add algorithms for higherorder functions (not square root  that is done via an algorithm that roughly looks like division). Between some pre and postprocessing steps the CORDIC algorithm delivers one digit of the result (within the internal processing domain) per iteration. There may be range reduction/scaling issues ("unwinding the circle" for trig functions for example), and some postprocessing (say, deriving one trig function from another or change of bases of logs) before the *actual* result is returned. When later calcs (42,32,48, etc) came out that supported a higher dynamic range (+/9.9E+/499 instead of +/9.9E+/99) there could've been some algorithmic changes. But I don't think so  I think fundamental algorithms have had enough time spent on them, modelling them, testing, etc that a co like HP would be loath to change them. CORDIC was suitable for log/trig functions on older/slow calcs because it wasn't that much more complex than division.
Other methods do exist: rational function approximation and Chebyshev (and other) polynomials. Some of these require use of division. And contrary to what you learned in calculus class, Taylor's/McLaurin's series aren't that useful for accurate & efficient function approximations.
These involve approximating the function under question over a VERY LIMITED RANGE and pre/postprocessing results.
X86 and other CPUs with floatingpoint engines have changed design over time. The 80x87 NPU chip, and its onboard derivatives up thru the 486, used CORDIC methods for log/trig functions: they were controllable algorithms with predictable error behavior and didn't take much microcode space on these NPUs.
However CORDIC is essentially serial in nature: you're delivering one bit, hex or BCD digit per iteration. [I believe, IIRC, if you try to speed things up taking bigger "chunks" (say, 4 digits at a time) there is no gain in internal behavior becuase, well, "if you bite off too much" on one iteration, you may often "have to spit some back".] And then internal tables of shifted input values that drive CORDIC would have to be large too.
To have faster results  when fast hardware multiply and divide are available, then nonCORDIC methods may be superior (in terms of speed; error behavior may need some real modelling and analysis). Also some processing steps of these nonCORDIC methods could be parallelized (with additional hardware) if desired. The real art of these designs is to take a system that has an Nbit register set and deliver N bits of result  instead of, say, N2 result bits with the last 2 bits being "slop". AMD, Intel and Cyrix all have differing methods of doing their transcendentals. There are some papers out there about how Cyrix did theirs, as I recall.
Bill Wiese
San Jose, CA
