Searching \ for 'better log 10' in subject line. () Help us get a faster server
FAQ page: piclist.com/techref/index.htm?key=better+log
Search entire site for: 'better log 10'.

Truncated match.
'better log 10'
1996\05\30@122815 by  I guess you guys were right.  I should have worked on it a bit more before
posting my log 10 approximation.  Luckily, I came up with another one. ;o

Give this one a whirl and give me some feedback.

(-1/sqrt(x+0.02) + 0.5) / ln(10)

It's a little less accurate around .5, but that's OK.  Take a look at the
plots of log10 and this approximation before you criticize too heavily.

It worked pretty well for me.  Anyone willing to share pseudo-code on how
to do a fast square root calculation?  I remember some discussion about it
a while ago, but I don't have those messages anymore.

Stuart Allman
studio halcyon.com  Lose the log(10) factor. (-1/sqrt(x+0.02) + 0.5) is pretty good,
(-1/sqrt(x+0.02) + 0.5) *0.95 is even better:
0 ++-----+------+-----+------+------+------+------+-----+------+-----++
+      +      +     +      +      +      +      +     +      +      +
|                                (-1/sqrt(x+0.02) + 0.5) *0.95#######
-1 ++                                         *************log(x)*******
|                            ***************                        |
|                    ********##                                     |
-2 ++             ******#                                             ++
|           ***#                                                    |
|       #***                                                        |
-3 ++    #**                                                          ++
|   #**                                                             |
|  #**                                                              |
-4 ++ *                                                               ++
| #*                                                                |
|#*                                                                 |
-5 +*                                                                 ++
|*                                                                  |
|*                                                                  |
-6 +*                                                                 ++
*                                                                   |
+      +      +     +      +      +      +      +     +      +      +
-7 ++-----+------+-----+------+------+------+------+-----+------+-----++
0    0.05    0.1  0.15    0.2   0.25    0.3   0.35   0.4   0.45    0.5

0 ++-----+------+-----+------+------+------+------+-----+------+-----++
+      +      +     +      +      +      +      +     +      +     **
-0.5 ++                           (-1/sqrt(x+0.02) + 0.5) / log(10)*****++
|                 **************                       #log(x)#######
-1 ++         *******                        #############            ++
|      ****                     ##########                          |
-1.5 ++   **                  ########                                  ++
|  **              #######                                          |
-2 ++*            #####                                               ++
|*          ###                                                     |
-2.5 +*       ###                                                       ++
-3 *+     ##                                                          ++
|    ##                                                             |
-3.5 ++  ##                                                             ++
|  #                                                                |
-4 ++ #                                                               ++
| #                                                                 |
-4.5 ++#                                                                ++
|#                                                                  |
-5 +#                                                                 ++
+#     +      +     +      +      +      +      +     +      +      +
-5.5 ++-----+------+-----+------+------+------+------+-----+------+-----++
0    0.05    0.1  0.15    0.2   0.25    0.3   0.35   0.4   0.45    0.5  At 04:46 PM 5/30/96 -0400, you wrote:
>Lose the log(10) factor. (-1/sqrt(x+0.02) + 0.5) is pretty good,
>(-1/sqrt(x+0.02) + 0.5) *0.95 is even better:

That was a division by the natural log of 10, not the base 10 log of 10.  My
approximation gives the base 10 log, not the natural log.

Try it again with the ln(10), which should be around 2.30258....  Although
not perfect, it's close enough for audio work.

The idea is that ln(x)/ln(10) = log10(x).  The 0.95 factor gave me more
error at  lower numbers.  Maybe I should check it out again.

Stuart Allman
Studio Sound Design
studio halcyon.com  For what it's worth, here is a C implementation of a log (to base 2)
routine.  Parameter x (unsigned 16bit integer) is converted to its
log to base 2 (8-bit unsigned int scaled up by 16 so that the most
significant 4 bits are the exponent and the least significant 4 bits
are the fraction).  Args approaching 65535 will cause an overflow so
watch out for this.  An arg of 0 returns 0.

The conversion from a base 2 log to a base 10 log is performed by
multiplying the result by log10(2) = 0.30102996... which, for our
low precision purposes may be approximated by 0.3.  The beauty of
0.3 is that the techniques in the parallel thread (regarding division
by 10) may be used: Multiply by 3 then divide by 10.

Anyway, for audio purposes it's often good enough to leave the result
in base 2 since a factor of 2 is very close to 3dB, which is convenient
for bar graph display etc.

The code should convert to PIC assembler in a straightforward manner.
The lookup table would obviously be hard-coded (all 17 entries if
LKP_BITS is 4).  The result accuracy is +1/16 to -1/32 - this is
skewed because of the simple-minded rounding technique.  Note that
the lookup table contains the following:

0:   0
1:   1
2:   3
3:   4
4:   5
5:   6
6:   7
7:   8
8:   9
9:  10
10:  11
11:  12
12:  13
13:  14
14:  15
15:  15
16:  16

which is so nearly linear that you could use code instead and perhaps save
a few words.

Regards,
SJH
Canberra, Australia

----Cut here----
#include <stdio.h>
#include <math.h>

typedef unsigned short word;    /* Input type */
typedef unsigned char byte;     /* Output type */

#define LKP_BITS 4            /* Number of bits (past leading 1 bit) to
use for indexing log lookup table */
#define LKP_ENT (1<<LKP_BITS) /* Corresponding table entries */
#define LKP_SCALE 16          /* Scale factor for lookup table.  Should
be power of 2 for quick mul/div */

static byte lookup[LKP_ENT+1];

static void init_lkp()
{
int i;

printf("Lookup table:\n");
for (i=0; i <= LKP_ENT; i++)
{
lookup[i] = LKP_SCALE * log2(1.0 + (float)i/LKP_ENT) + 0.5;
printf("%2d: %3d\n", i, lookup[i]);
}
printf("\n");
}

static byte alog(word x)
{
byte p2;

if (!x)
return 0;  /* Punish for taking log(0) - return log(1) instead */

/* Shift left until MSB == 1, count power of 2 */
for (p2 = 15; !(x & 0x8000); x <<= 1, p2--);
/* Scale up p2 to match lookup scale factor */
p2 *= LKP_SCALE;
/* Use the most sig. LKP_BITS to compute the fractional part of log2.
Mask out MSB since it is assumed to be 1. */
x &= 0x7FFF;
#define SYMM_ERROR
#ifdef SYMM_ERROR
/* Test LSB and round up if 1.  Makes error symmetrical. */
x = ((x >> (14-LKP_BITS)) + 1) >> 1;
#else
/* Otherwise error is asymmetric and twice as bad, but saves some
fooling around */
x >>= 15-LKP_BITS;
#endif
return (p2 + lookup[x]);
}

int main(int argc, char ** argv)
{
float fx, flogx, falogx;
word x;
byte alogx;

init_lkp();

for (fx = 4095; fx <= 8192; fx += 4096/64)
{
x = fx;
flogx = log2((float)x);   /* Compute 'exact' */
alogx = alog(x);   /* Compute int approx */
falogx = (float)alogx/LKP_SCALE;  /* Rescale, and convert to float */
printf("x = %5d  log10(x) = %-10.5g  alog(x) = %-10.5g  diff = %-10.5g\n",
x, flogx, falogx, flogx-falogx);
}
return 0;
}
----Cut here----  Whoops, apply following corrections:

Error should have been -1/16 to +1/32.

Final printf says log10(x) - should have been log2(x)

SJH   Stuart Allman wrote:

>
> Give this one a whirl and give me some feedback.
>
> (-1/sqrt(x+0.02) + 0.5) / ln(10)
>
> It's a little less accurate around .5, but that's OK.  Take a look at the
> plots of log10 and this approximation before you criticize too heavily.
>

A few months ago I picked up a book called "Dead Reckoning: Calculating
Without Instruments", by Ronald W. Doerfler. I recalled seeing something
about logarithm calculations and decided to look it up again last night. I came
across formula very similar to Stuart's:

6*(x - 1)             1
log(x) ~ ------------------ * ------
x + 1 + 4*sqrt(x)    ln(10)

This is called Borchardt's Algorithm. Doerfler discusses briefly how it is
derived. He also says that there is an extrapolation method called Richardson's
extrapolation that can be used to get a more accurate expression. However,
for .7 < x < 1.3, this approximation is accurate to 7 significant figures. It is
still quite accurate for the 0 < x < .5 range Stuart originally requested:

x      log(x)    Borchardt's Approximation     error
--------------------------------------------------------------
.1     -1           -0.99166                     0.83%
.2     -0.69897     -0.69746                     0.22%
.3     -0.52288     -0.52251                     0.071%
.4     -0.39794     -0.39785                     0.023%
.5     -0.30103     -0.30101                     0.000%
1.5      0.17609      0.17609                     0.000%
2.0      0.30103      0.30101                     0.000%
10.0      1            0.99166                    -0.83%

Maybe Przemek will be kind enough to plot another one of those fancy ASCII
plots.

Incidently, Doerfler's book has a bunch of interesting stuff (that is, if you
posess that certain geek mentality). He discusses many techniques for fast
arithmetic, roots, powers, logarithms, inverse logs, trig functions etc. His
objective is more towards mental computation and not computer algorithms.
However,
often times the most optimum technique for one is also the most optimum for the
other.

Scott  I came across formula very similar to Stuart's:

6*(x - 1)             1
log(x) ~ ------------------ * ------
x + 1 + 4*sqrt(x)    ln(10)

...
Maybe Przemek will be kind enough to plot another one of those fancy ASCII
plots.

(Przemek Obliges)
(BTW, this is done using the 'dumb' terminal output driver in Gnuplot).

-2 ++------------+------------+-------------+------------+------------++
+             +            +             +            +        ******
-2.5 ++                               6*(x - 1)/(x + 1 + 4*sqrt(x))*****++
|                                     ************#     log(x) #### |
-3 ++                            *********##                          ++
|                      *******##                                    |
-3.5 ++               ******###                                         ++
|           *****###                                                |
-4 ++        ***###                                                   ++
|      ***###                                                       |
-4.5 ++   ** ##                                                         ++
|  ** ##                                                            |
| ** #                                                              |
-5 +*  #                                                              ++
|* #                                                                |
-5.5 +* #                                                               ++
* #                                                                 |
-6 *+#                                                                ++
|#                                                                  |
-6.5 +#                                                                 ++
+#            +            +             +            +             +
-7 +#------------+------------+-------------+------------+------------++
0           0.02         0.04          0.06         0.08           0.1

Pretty good, pretty good. In the interval [0.1, 0.5] the difference is
imperceptible.

Now if someone would come up with an approximation of sqrt() using only