Reproducible rounding up with hidden constant and known maximum deviation

Question

I am running a system with an unknown constant X and a known boundary B over several iterations. N is the value I get, which is X + (0...B). Here is an example of several runs of this system where B = 5:

N = 10
N = 13
N = 12
N = 14
N = 12
N = 15

My goal is to get all these runs to synchronize, so I want to round N to a common value, let's call it R. I'll pick 100, seems safe enough.

But can I generalize this to do better, surviving arbitrary changes to X if B stays constant? Let's say the system gets edited and might tomorrow give me:

N = 10010
N = 10013
N = 10012
N = 10014
N = 10012
N = 10015

I don't need it to give a compatible R value with the previous system. It just needs to be compatible with these numbers. Clearly, R at 100 will no longer do after this change. :-/

e.g. though X is fixed, I'm only receiving on each run a value N, which you know is equal to a value between X and X + B (so B is an upper bound on N's deviation from this unknown-but-fixed X)

Without knowing what X is, I wish to conservatively round N up in such a way that regardless of whether it's actually X or any value up to X + B, it will yield the same value R. The rounding should be reproducible enough to account for all deviations across B and give some larger constant number that all runs can agree on.

If you had the missing piece of information in my first case above...that X is 10...you could have all the cases just round to X + B and get R = 15. And if you had the missing piece of information in my second case...that X is 10010, you could have that always round to 10015. But again, you don't know X--you just know B, and N is coming in at all kinds of values.

Is there a formula for a minimal calculation of R in terms of N and B that you can feel assured will be a reproducible round-up to produce the same R across the spread of N?

Other than saying "well, it seems you can bound this and get a reproducible R, even if it winds up being big" I don't know how to pick R precisely as a function of B and N.

Answer 1

$$R = 2^{(ceil(\log_2 (N)))} + B - 1$$

Possibly minimal? Rationale:

---

This kind of problem is usually easier to see patterns in with binary. Introduce a new value H, as the hypothetical legal values of N for an observed N. Also introduce D, number of binary digits in the input.

Now choose R as the maximum value of H that occurs in the digit group for that N.

Let's make a table for some cases with B = 1

  N (D)             H                R
----------------------------------------
  0 (0) ->    0 or   1          ->     1
  1 (1) ->    0 or   1 or   10  ->    10
 10 (2) ->    1 or  10 or   11  ->   100
 11 (2) ->   10 or  11 or  100  ->   100
100 (3) ->   11 or 100 or  101  ->  1000
101 (3) ->  100 or 101 or  110  ->  1000
110 (3) ->  101 or 110 or  111  ->  1000
111 (3) ->  110 or 111 or 1000  ->  1000

It's pretty easy to see that the only value of H we're interested in for this calculation is the maximum value of H. Call that M, as N + B...and just pick R as the largest value of M that occurs in the digit group for that N.

Let's try that with B = 10 (again, in binary)

   N (D)        M         R
---------------------------
   0 (0) ->    10  ->    10
   1 (1) ->    11  ->    11
  10 (2) ->   100  ->   101
  11 (2) ->   101  ->   101
 100 (3) ->   110  ->  1001
 101 (3) ->   111  ->  1001
 110 (3) ->  1000  ->  1001
 111 (3) ->  1001  ->  1001  
1000 (4) ->  1011  -> 10001
1001 (4) ->  1011  -> 10001
1010 (4) ->  1100  -> 10001
1011 (4) ->  1101  -> 10001
1100 (4) ->  1110  -> 10001
1101 (4) ->  1111  -> 10001
1110 (4) -> 10000  -> 10001
1111 (4) -> 10001  -> 10001

If you're willing to say 0 has 0 digits, you'd be covered if you count the number of binary digits in N, then get the next power of 2 after that and add in B - 1.

How much rounding-up are we talking about here? Well, for my sample case where N was something like decimal 10015 and B is 5, you'll be jumping to a synchronization of 16388.