Stuart Allman <PICLIST@MITVMA.MIT.EDU> wrote:

> I need to calculate the base 10 log of a 16 bit number in the range
> of 0 to 64k.  Does anyone know a good approximation method?

Stuart:

Here's one... It requires a short lookup table and isn't
extraordinarily accurate for small numbers, but it only requires
shifts, addition, and subtraction.  I'm doing this from memory, but I
think it's accurate.

To find y = log10(x):

    Make a table, thusly:

        t(1) = log10(2/1)
        t(2) = log10(4/3)
        t(3) = log10(8/7)
             ....
        t(n) = log10(2**n/2**n-1)

        [" ** " is my preferred notation for "raised to the power";
        you may prefer " ^ ".]

    The length of the table is dependent upon the precision that you
    want; pick a level of precision and just keep adding entries to
    the table until you get to one that, at your level of precision,
    is equal to 0.  For instance, if you only needed three or four
    (decimal) digits of precision, I think eight eight-bit entries
    would be enough.

    Ok.  Now do this:

    n = 1
    y = 0
    z = (x >> 1)

    while x > 1,
    {
        if x - z < 1 then n = n + 1, z = (z >> 2).
        otherwise, x = x - z, z = (x >> n), y = y + table(n).
    }

    ["a >> b" means "shift 'a' rightward 'b' positions"]

When the routine completes, y will be (approximately, to the level of
precision you've chosen) equal to log10(x).

The table can be very small... 8 entries should be enough for 1%
accuracy over nearly the entire range [1-65535].  Note that the
accuracy will be worst at the low end of the range.

-Andy

P.S.  If you happen to have tables of ln(x) and log2(x), you can
      also, surprisingly enough, calculate a really close
      approximation of log10(x) like this:

          log10(x) = log2(x) - ln(x)

      Cool, huh?

Andrew Warren - fastfwd@ix.netcom.com
Fast Forward Engineering, Vista, California
http://www.geocities.com/SiliconValley/2499