Very fast log2 for Atmega328P

[Teleno]

Input: 16bit unsigned integer.
Output: Q8.8. fixed point (log2 accurate to +- 0.005).

Execution time: 2.13us - 12.38us

How it works:
1) Integer part "n" of log2 is the rank of the highest set bit. A fast table lokup is used.
2) Fractional part: The input is normalized to (1 + x) where 0 <= x < 1. This is done dividing by 2^n (shifted right n times, input extended to 24 bits).
Te least significant bits are the index for the second LUT containing the precalculated log2(1 + x).

Benchmark at 16 MHz
Estimate log(3.00): 1.582
True val log(3.00): 1.585
Timer count: 34
Time lapsed us: 2.13
Estimate log(18.00): 4.168
True val log(18.00): 4.170
Timer count: 52
Time lapsed us: 3.25
Estimate log(108.00): 6.754
True val log(108.00): 6.755
Timer count: 64
Time lapsed us: 4.00
Estimate log(648.00): 9.340
True val log(648.00): 9.340
Timer count: 168
Time lapsed us: 10.50
Estimate log(3888.00): 11.922
True val log(3888.00): 11.925
Timer count: 96
Time lapsed us: 6.00
Estimate log(23328.00): 14.504
True val log(23328.00): 14.510
Timer count: 198
Time lapsed us: 12.38​

log_2_table_8bit_asm.zip

[Teleno]

An update that's 3 x faster. Max. 4.13 us

Benchmark at 16 MHz

Estimate log(3.00): 1.586
True val log(3.00): 1.585
Timer count: 36
Time lapsed us: 2.25
Estimate log(18.00): 4.172
True val log(18.00): 4.170
Timer count: 51
Time lapsed us: 3.19
Estimate log(108.00): 6.754
True val log(108.00): 6.755
Timer count: 61
Time lapsed us: 3.81
Estimate log(648.00): 9.340
True val log(648.00): 9.340
Timer count: 41
Time lapsed us: 2.56
Estimate log(3888.00): 11.926
True val log(3888.00): 11.925
Timer count: 51
Time lapsed us: 3.19
Estimate log(23328.00): 14.508
True val log(23328.00): 14.510
Timer count: 66
Time lapsed us: 4.13​

log_2_table_8bit_asm.zip

[Teleno]

It can be done even faster by doing some shift operations in blocks of 8 with the "mov" instruction and blocks of 4 with the "swap" instruction and so reducing the number bit shift loops.

New update with max. exec. time of 3.25us and max. error of 0.007

log(3):
Estim 1.586
True: 1.585
Time: 2.44 us

log(1):
Estim 4.172
True: 4.170
Time: 2.56 us

log(10):
Estim 6.754
True: 6.755
Time: 3.06 us

log(64):
Estim 9.340
True: 9.340
Time: 2.56 us

log(38):
Estim 11.926
True: 11.925
Time: 2.88 us

log(2332):
Estim 14.508
True: 14.510
Time: 3.19 us

Max time: 3.25 us
for number: 32768
Max err: 0.007

log_2_table_8bit_asm.zip

[Altra]

Hi Teleno, how are you applying this towards metal detector applications? I want to try it on my lcd target strength bargraph.

[Teleno]

Hi Teleno, how are you applying this towards metal detector applications? I want to try it on my lcd target strength bargraph.

I'm applying it to the sound of my PI to generate a frequency that increases logarithmically with the target signal.




Where N is the bit resolution of the signal.

After doing the product with the log value returned by this code, the result must be shifted right by PRECISION places: result >> PRECISION

for example:

#define F_MIN   300UL
#define F_MAX  2000UL
#define N 14   // Signal resolution in bits

uint16_t signal = 2130;
uint16_t freq;

uint32_t temp = do_log(signal) * (uint32_t) (F_MAX - F_MIN ) / N;
freq = F_MIN + (uint16_t) (temp >> PRECISION);

[Altra]

Thanks, my signal strength would correlate with the audio, so the same goal as you

[Teleno]

Thanks, my signal strength would correlate with the audio, so the same goal as you

Just remove the timer statements that I used for the benchnark in the .inc file.

[Altra]

I'll have to rework your code because I am using a dspic33 and a dedicated pwm to generate the audio. Microchip's assembly is different than Atmel's. But thanks, you have provided enough information for me to work it out.