PIC Microcontoller Basic Math Power Methods

Calculating x^y, 2^x, etc.

Code:

• X^Y16 Bit x^y Logarithm ruler approach 800 cycles and about 220 words by Nikolai Golovchenko
• 2^x 16 Bit 2^x 139...291 cycles 121 words by Nikolai Golovchenko
• Scott Dattalo implemented log2(x) in PIC assembly language.

Theory:

x^y

If y is an integer, we can repeatedly multiply (or use even faster algorithms that repeatedly square and multiply).

If y is not an integer, we generally make the substitution

  x^y = e^(y ln( x ))
or
  x^y = 2^(y log2( x ))

and use some subroutine to calculate ln(x) and e^b -- or, alternatively, calculate log2(x) and 2^b.

(Is there a page somewhere on massmind describing logarithms and exponentials? Move the following text there.)

• The traditional method for calculating logarithms and exponentials is to scale to a number between 0 and 1, then use rational Chebyshev expansions.
• Feynman's Power Algorithm. "The algorithm is described in a homework problem in chapter 1 of Knuth's "The Art of Computer Programming: Fundamental Algorithms". BTW, if you don't have the three volumes of Knuth's books, then get them! -- Scott Dattalo

  "Richard Feynman and The Connection Machine" by W. Daniel Hillis 1989 briefly describes Richard Feyman and the algorithm:

  An Algorithm For Logarithms

  Feynman worked out ... the subroutine for computing logarithms. I mention it here not only because it is a clever algorithm, but also because it is a specific contribution Richard made to the mainstream of computer science. He invented it at Los Alamos.

  Consider the problem of finding the logarithm of a fractional number between 1.0 and 2.0 (the algorithm can be generalized without too much difficulty). Feynman observed that any such number can be uniquely represented as a product of numbers of the form 1 + 2-k, where k is an integer. Testing each of these factors in a binary number representation is simply a matter of a shift and a subtraction. Once the factors are determined, the logarithm can be computed by adding together the precomputed logarithms of the factors. The algorithm fit especially well on the Connection Machine.... The entire computation took less time than division.

  Scott Dattalo has written a far more detailed explanation of Feynman's log2(x) algorithm, with worked-out examples .

Questions:

• hi, i need to implement y=e^x in PIC. where x=0 to 30 (a floating point value).
  
  If we use a table and then, If an intermediate(in-between) value is encountered, how to interpolate it???
  -vivek
  gvivek2004@gmail.com James Newton replies: There is very little support for floating point math in the PIC. See this page for some possible resources: http://www.piclist.com/techref/microchip/math/fp.htm+

  +

  .