# Histogram: logarithmic binning in O(1)?

This topic is 1877 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I need a histogram with a logarithmic X axis; that is, the bin size is logarithmic (say with ranges 0.1-1, 1-10, 10-100, etc.). I'm storing the histogram as a plain 1D array.

Given a value, to find the corresponding bin, code I've found online loops over the bins, calculating bin width and checking if x falls in it, else continuing. That's O(num_bins), which is awful. How do I calculate the bin/array index in O(1) as is done in the linear case? Surely there's a closed-form analytic formula.

Edited by Prune

##### Share on other sites

bin = floor(log10(x));

or am I not undertanding the question?

If it's not log10 base you can use natural logs to convert the ranges.

##### Share on other sites

$\text{bin}(x) = \left \lfloor \log_{10}\left ({\frac{x}{x_\text{min}}} \right ) \right \rfloor$

In your case, $$x_\text{min} = 0.1$$ and the bin numbering starts at zero. You can derive this by starting the histogram at the 1..10 bin and accounting for the smaller bins afterwards.

Thanks a lot!

##### Share on other sites

Actually, not quite there. When I said "say with ranges 0.1-1, 1-10, 10-100, etc." that was just an example. The formula above works when num_bins = log10(max_range). But I want num_bins to be a parameter that can be set independently of max_range.

##### Share on other sites

The general formula is:

bin = floor(N * (log(x) - log(min)) / (log(max) - log(min)))


The value of bin is the bin index such that there are N bins logaritmically spaced between min (inclusive) and max (exclusive).

Thanks again!

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 9
• 11
• 9
• 9
• ### Forum Statistics

• Total Topics
634135
• Total Posts
3015753
×