In which segment a given floating point number lies in?

Question

Suppose to have n (integer) contiguous segments of length l (floating point). That is:

Segment 0 = [0, l)
Segment 1 = [l, 2*l)
Segment 2 = [2*l, 3*l)
... 
Segment (n-1) = [(n-1)*l, n*l)

Given a number x (floating point), I want to write a function

int getSegmentId(double x, double l, int n)

which returns the id of the segment where x lies.

I would like to do this in O(1), not O(log(n)) by checking if x lies in each interval.

I think this is a very general and common problem and I guess there is one solution for this. Have you any hint for me?

Addendum

The question is not about a particular implementation of this algorithm like in the previous question based on floating point operations. I'm just asking which is ~~the best~~ a good and robust way to implement this.

Would `lround()`'ing the double before adding it to the int do what you want? — Jesper Juhl, Jun 29 '16 at 17:58
*"I'm just asking which is the **best way** to implement this"* that's too opinionated for this site. — Kevin B, Jun 29 '16 at 19:54
@KevinB changed "best way" to "good and robust way". Is it better? — the_candyman, Jun 29 '16 at 19:57
If the only thing that makes your question different from the duplicate is you want the best, or a good, way of doing it, I don't think that's enough of a difference to make it not a dupe. What makes your question different, that's what you need to explain within your question. — Kevin B, Jun 29 '16 at 19:59
@KevinB ok, but my [previous question](http://stackoverflow.com/questions/38096660/in-which-segment-a-given-number-lies-in) was marked as duplicate because I was asking how to solve the problem using floating point math. Now, I'm asking how to solve the problem, not necessarily using floating point math. — the_candyman, Jun 29 '16 at 20:01
you already have *an* answer to that, explain why you are looking for more ways to do it or why that way won't work for you. — Kevin B, Jun 29 '16 at 20:01
@KevinB I'm looking for more ways because if I use something like (int)floor(x / l), I can sometimes obtain ambiguous results as remarked in my [previous question](http://stackoverflow.com/questions/38096660/in-which-segment-a-given-number-lies-in). — the_candyman, Jun 29 '16 at 20:03
If 'l' would be a decimal (with decimal places) and `n*l` a decimal, then it becomes a different question. However your query is `int getSegmentId(double x, double l, int n)` and not `int getSegmentId(double x, decimal l, int n)` — , Jun 29 '16 at 20:06
@DieterLücking it seems it has become a philosophical problem about number representations... It sounds strange to me that this kind of problem has never been tackled and solved. I give up. — the_candyman, Jun 29 '16 at 20:21

score 2 · Answer 1 · answered Jun 29 '16 at 17:59

2

I don't see the problem, if each segment starts at i*l and ends at (i+1)*l then

int s = static_cast<int>(std::floor(x / l));

should be enough.

answered Jun 29 '16 at 17:59

Jack

131,802
30
241
343

is it enough? Don't think it always works. See [this](http://stackoverflow.com/questions/38096660/in-which-segment-a-given-number-lies-in) and [this](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) – the_candyman Jun 29 '16 at 18:03

score 1 · Accepted Answer · answered Jun 29 '16 at 18:05

1

int getSegmentId(double x, double l, double n)
{
    if(x>=n*l){
        //cout>> "Not in any segments! ";
        return -1;
    else
        return (int) x/l ;
}

answered Jun 29 '16 at 18:05

Apoorva K H

111
5

In which segment a given floating point number lies in?

2 Answers2