• Create Account

# Histogram: logarithmic binning in O(1)?

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

6 replies to this topic

### #1Prune  Members   -  Reputation: 184

Like
0Likes
Like

Posted 29 November 2013 - 07:55 PM

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, 29 November 2013 - 07:56 PM.

"But who prays for Satan? Who, in eighteen centuries, has had the common humanity to pray for the one sinner that needed it most?" --Mark Twain

~~~~~~~~~~~~~~~Looking for a high-performance, easy to use, and lightweight math library? http://www.cmldev.net/ (note: I'm not associated with that project; just a user)

### #2Paradigm Shifter  Crossbones+   -  Reputation: 4746

Like
1Likes
Like

Posted 29 November 2013 - 08:03 PM

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.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

### #3Bacterius  Crossbones+   -  Reputation: 6492

Like
1Likes
Like

Posted 29 November 2013 - 08:05 PM

$\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.

"The best comment is a deleted comment."

### #4Prune  Members   -  Reputation: 184

Like
1Likes
Like

Posted 01 December 2013 - 06:28 PM

Thanks a lot!

"But who prays for Satan? Who, in eighteen centuries, has had the common humanity to pray for the one sinner that needed it most?" --Mark Twain

~~~~~~~~~~~~~~~Looking for a high-performance, easy to use, and lightweight math library? http://www.cmldev.net/ (note: I'm not associated with that project; just a user)

### #5Prune  Members   -  Reputation: 184

Like
0Likes
Like

Posted 02 December 2013 - 12:02 PM

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.

"But who prays for Satan? Who, in eighteen centuries, has had the common humanity to pray for the one sinner that needed it most?" --Mark Twain

~~~~~~~~~~~~~~~Looking for a high-performance, easy to use, and lightweight math library? http://www.cmldev.net/ (note: I'm not associated with that project; just a user)

### #6Brother Bob  Moderators   -  Reputation: 7137

Like
0Likes
Like

Posted 02 December 2013 - 12:57 PM

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).

### #7Prune  Members   -  Reputation: 184

Like
0Likes
Like

Posted 02 December 2013 - 02:44 PM

Thanks again!

"But who prays for Satan? Who, in eighteen centuries, has had the common humanity to pray for the one sinner that needed it most?" --Mark Twain

~~~~~~~~~~~~~~~Looking for a high-performance, easy to use, and lightweight math library? http://www.cmldev.net/ (note: I'm not associated with that project; just a user)

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS