Finding resolution ranges for lists of floating point numbers

Question

I have a sorted list of sample numbers, e.g.:

0.1, 0.2, 0.4, 0.5, 0.8, 0.9, 1.0, 1.5, 2.0, 4.0, 4.5, 5.0, 10.0, 15.0, 20.0

I need to find the resolution of the samples and the ranges in which those resolutions hold. The restriction is that once you go to a lower resolution (higher delta between the numbers), you cannot go back.

The correct output for the example should then be:

From 0.1 to 1.0, resolution is 0.1
From 1.0 to 5.0, resolution is 0.5
From 5.0 to 20.0, resolution is 5.0

I tried going over the numbers and taking their difference as the resolution, and extending the range as long as that resolution holds, but I'm having difficulty with cases such as between 0.2 and 0.4 where the resolution could be 0.2, which is then invalidated with the next sample of 0.5.

Can anyone help me find an algorithm that can accomplish this? I'm using c++, with the numbers having a precision of 3 decimal places, if that makes any difference.

Lajos Arpad Lajos Arpad · Accepted Answer · 2017-03-01T12:39:21

You need to find the smallest difference in subsets of the array. Pseudo-code

function smallestDifference(input, index)
    min <- -1
    while index + 1 < input.length
        difference = input[index + 1] - input[index]
        if min = -1 or min > difference then
            min <- difference
        end if
        index <- index + 1
    end while
    return min
end function

The function will find the resolution of the input for the index. If you do this for the very last element, -1 will be returned, otherwise the exact value you need.

Test it like:

i <- 0
while i < input.length
    print smallestDifference(input, i)
    i <- i + 1
end while

Finding resolution ranges for lists of floating point numbers

1 Answers