CODEWITHSUNDEEP
coptimizationintegerbit-manipulationlogarithm
R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215287

Quick integer logarithm for special case

I have integer values ranging from 32-8191 which I want to map to a roughly logarithmic scale. If I were using base 2, I could just count the leading zero bits and map them into 8 slots, but this is too course-grained; I need 32 slots (and more would be better, but I need them to map to bits in a 32-bit value), which comes out to a base of roughly 1.18-1.20 for the logarithm. Anyone have some tricks for computing this value, or a reasonable approximation, very fast?

My intuition is to break the range down into 2 or 3 subranges with conditionals, and use a small lookup table for each, but I wonder if there's some trick I could do with count-leading-zeros then refining the result, especially since the results don't have to be exact but just roughly logarithmic.

Upvotes: 6

Views: 913

Answers (3)

R.. GitHub STOP HELPING ICE
R.. GitHub STOP HELPING ICE

Reputation: 215287

Answer I just came up with based in IEEE 754 floating point:

((union { float v; uint32_t r; }){ x }.r >> 21 & 127) - 16

It maps 32-8192 onto 0-31 roughly logarithmically (same as hwlau's answer).

Improved version (cut out useless bitwise and):

((union { float v; uint32_t r; }){ x }.r >> 21) - 528

Upvotes: 2

unsym
unsym

Reputation: 2200

Why not use the next two bits other than the leading bit. You can first partition the number into the 8 bin, and the next two bits to further divide each bin into four. In this case, you can use a simple shift operation which is very fast.

Edit: If you think using the logarithm is a viable solution. Here is the general algorithm:

Let a be the base of the logarithm, and the range is (b_min, b_max) = (32,8191). You can find the base using the formula:

log(b_max/b_min) / log(a) = 32 bin

which give you a~1.1892026. If you use this a as the base of the logarithm, you can map the range (b_min, b_max) into (log_a(b_min), log_a(b_max)) = (20.0004,52.0004).

Now you only need to subtract the all element by a 20.0004 to get the range (0,32). It guarantees all elements are logarithmically uniform. Done

Note: Either a element may fall out of range because of numerical error. You should calculate it yourself for the exact value.

Note2: log_a(b) = log(b)/log(a)

Upvotes: 4

Keith Randall
Keith Randall

Reputation: 23265

Table lookup is one option, that table isn't that big. If an 8K table is too big, and you have a count leading zeros instruction, you can use a table lookup on the top few bits.

nbits = 32 - count_leading_zeros(v)  # number of bits in number
highbits = v >> (nbits - 4)          # top 4 bits.  Top bit is always a 1.
log_base_2 = nbits + table[highbits & 0x7]

The table you populate with some approximation of log_2

table[i] = approx(log_2(1 + i/8.0))

If you want to stay in integer arithmetic, multiply the last line by a convenient factor.

Upvotes: 2

Related Questions