Possible new TagTime universal ping algorithm

TagTime
31

If I did this right then here’s a graph with the amount of time you spend answering pings on the x-axis and the amount of time that each algorithm (blue = continuous, orange = discrete with 1-second granularity) will tell you you spent:

image
image.png814×510 12.9 KB

And here’s the same thing but with 0.1-second granularity:

image
image.png812×509 13.7 KB

(The probability of getting pung in s seconds after the last ping is 1-exp(-s/g) in the continuous case and 1-(1-d/g)^floor(s/d) in the discrete case, where d is the granularity, eg, 1 for seconds or 1/10 for deciseconds, and g is the mean gap in seconds.)

So I guess we can call that justification for using deciseconds in the new algorithm (if we actually want a new algorithm). Since I got seriously nerdsniped, I implemented it in Javascript. The RNG below has a period of 109 years in deciseconds. And it does the fancy fast-forwarding.

First, constants:

const GAP = 45*60       // Average gap between pings, in seconds

const URPING = 15338120000 // Birth of the new TagTime algorithm in deciseconds
const SEED = 20180809     // Initial state of the random number generator (RNG)
const IA = 3125        // (5^5) Multiplier used for LCG RNG
const IM = 34359738337 // (2^35-31) Modulus used for RNG (assumes 36-bit ints)

// Each decisecond has probability 1/(GAP*10) of being a ping, where GAP is the 
// average time between pings in seconds. The LCG random number generator
// returns a random integer uniformly in {1,...,IM-1} so LCG/IM is a U(0,1) 
// random variable and there's a ping iff 
//   LCG/IM < 1/(GAP*10) => LCG < IM/(GAP*10)
// so we define a constant for the RHS to compare to.
const THRESH = IM/(GAP*10)

Global variables:

let state = SEED // Global variable that's the state of the RNG
let lastping = URPING // Global var with decisecond of last ping

Random number generator, with fast-forwarding:

// Return a random integer in [1,IM-1]; changes the RNG state.
// wikipedia.org/wiki/Linear_congruential_generator
function lcg() { return state = IA * state % IM }

// Compute a*b % m when a*b might overflow
function multmod(a, b, m) {
  if (b === 0)   { return 0 }
  if (b%2 === 0) { return multmod(a*2%m, b/2, m) % m }
  else           { return (a + multmod(a, b-1, m)) % m }
}

// Efficiently compute a^n % m -- wikipedia.org/wiki/Modular_exponentiation
function powmod(a, n, m) {
  if (n === 0)   { return 1 }
  let x
  if (n%2 === 0) { x = powmod(a, n/2, m); return multmod(x, x, m) }
  else           { x = powmod(a, n-1, m); return multmod(a, x, m) }
}

// Fast-forward the RNG by doing i steps at once
function powlcg(i) { return state = multmod(powmod(IA, i, IM), state, IM) }

And finally, the function to get the time of the next ping, from any starting time:

// Current unixtime in deciseconds
function decinow() { return round(Date.now()/100) }

// Given unixtime in deciseconds, t, start checking at t+1 and return the first
// time we come to with a ping, which becomes the new lastping time.
function nextping(t) {
  if (t < lastping) { return 0 }            // going back in time not allowed!
  if (t > lastping) { powlcg(t-lastping) }  // fast-forward the RNG up thru t
  lastping = t+1
  while (lcg() >= THRESH) { lastping += 1 }
  return lastping
}

For example, nextping(decinow()) efficiently gives the next upcoming ping time (in deciseconds) and then you just keep calling nextping with the previous ping time to get the next.

Feel free to play with the code on Glitch.

Btw, I realized that we can’t use the nifty fast-forwarding in the original algorithm because we don’t know the exact number of times the the RNG will have been called in the past.

1 Like