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.

"My goal is to get all these runs to synchronize, so I want to round N to a common value" sounds obscure to me, please would you clarify it? — giuliolunati, Nov 17 '17 at 09:25
@giuliolunati Concretely it is a tick count. In this code, a command line parameter is passed which sets a tick count to break at. However, that throws off the reproducibility of the tick count from the previous run. I want to reproducibly round up to a common value after the processing but I don't want to hardcode the tick number I round up to... — HostileFork says dont trust SE, Nov 17 '17 at 14:59

HostileFork says dont trust SE · Answer 1 · 2017-11-17T05:14:44.520

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

Uhm, I don't understand. Let be X=3 and B=1, so N can be 3 or 4. For N=3 R is 4 but for N=4 R is 8 — giuliolunati, Nov 16 '17 at 23:47
@giuliolunati Seems you are right, in that you can't look for the maximum value of H, but the possible values of H, which makes this impossible by definition. Proof of impossibility just means having to hardcode a number, and then assert if it's too small...but I wish it to be more clever than that, maybe you can think of something. :-/ An additional piece of information that can be captured is N's value before the deviation by bound, maybe what I'm thinking of is a similar rounding based on that delta. — HostileFork says dont trust SE, Nov 17 '17 at 16:05

Reproducible rounding up with hidden constant and known maximum deviation

1 Answers1