Simpler and slightly faster version of Otmar Oertl's idea for improving FastHistogram / HdrHistogram

HighDynamicRangeQuantile.java

public class HighDynamicRangeQuantile {
	private final long[] counts;
	private double minimum = Double.POSITIVE_INFINITY;
	private double maximum = Double.NEGATIVE_INFINITY;
	private long underFlowCount = 0;
	private long overFlowCount = 0;
	private final double factor;
	private final double offset;
	private final double minExpectedQuantileValue;
	
	public HighDynamicRangeQuantile(final double minExpectedQuantileValue, final double maxExpectedQuantileValue, final double maxRelativeError) {
		
		assert minExpectedQuantileValue >= Double.MIN_NORMAL; // bit operations below are not correct for subnormals
		// TODO range checks
		if (maxRelativeError < 1) {
		    maxRelativeError = 1 / maxRelativeError;
		}
		double epsilon = 1 / maxRelativeError;
		this.minExpectedQuantileValue = minExpectedQuantileValue;
                factor = Math.log(2) / Math.log(1 + epsilon) / 3;
                offset = getIndexHelper(factor, minExpectedQuantileValue);
		final int arraySize = getIndex(maxExpectedQuantileValue) + 1;
		counts = new long[arraySize];
	}
		
	int getIndex(final double value) {
		return (int) (getIndexHelper(value) - offset);
	}

	/**
	 * Approximates 3 * log2(value) by using the exponent bits of the floating point
	 * representation and applying a slight non-linearity to the mantissa. The non-
	 * linearity is achieved using a polynomial approximation of log2(m) that was
	 * derived by a linear fit over the range of interest.
	 *
	 * The reason that the result is 3 times the desired value is to avoid division
	 * by three in the polynomial. The idea is that division is slower than 
	 * multiplication.
	 */
	 
	double getIndexHelper(final double value) {
            final long valueBits = Double.doubleToRawLongBits(value);
            final long exponent = (valueBits & 0x7ff0000000000000L) >>> 52;
            final double m = Double.longBitsToDouble((valueBits & 0x800fffffffffffffL) | 0x3ff0000000000000L);
            return (m * (6 - m) + 3 * exponent) * factor;
	}

	public void add(final double value, final long count) {
		
		if (value >= minExpectedQuantileValue) {
			final int idx = getIndex(value);
			if (idx < counts.length) {
				counts[idx] += count;
			}
			else {
				overFlowCount += count;
			}
		}
		else {
			underFlowCount += count;
		}
		minimum = Math.min(minimum, value); 
		maximum = Math.max(maximum, value);
	}
	
	public long getCount() {
		long sum = underFlowCount + overFlowCount;
		for (final long c : counts) {
			sum += c;
		}
		return sum;
	}
}