Announcing Trak, an alternative to TagTime

TagTime
11

Here’s the reference implementation!

UPDATE: I moved this here:

For posterity, here's the Perl version

First define some constants:

my $IA = 16807;          # constant used for RNG (see p37 of Simulation by Ross)
my $IM = 2147483647;     # constant used for RNG (2^31-1)
my $URPING = 1184083200; # ur-ping, ie, the birth of timepie/tagtime!

# $seed is a global variable that is really the state of the RNG
$seed = $initseed = 666;

$gap = 45*60; # 45 minutes between pings on average

And some helper functions:

# Return a random integer in [1,$IM-1]; changes $seed, ie, RNG state
# (This is ran0 from Numerical Recipes and has a period of ~2 billion)
sub ran0 { return $seed = $IA*$seed % $IM; }

# Return a U(0,1) random number
sub ran01 { return ran0()/$IM; }

# Return random number drawn from an exponential distribution with mean $gap
sub exprand { return -1 * $gap * log(ran01()); }

# Round to nearest integer
sub round1 { my($x) = @_; return int($x + .5 * ($x <=> 0)); }

Then define a function prevping that takes the current unixtime and returns the unixtime of the previous ping according to the universal ping schedule. Once you have that you can keep calling nextping() with the timestamp of the last ping to get the time of the next ping.

# Take previous ping time, return random next ping time (unixtime)
# NB: this has the side effect of changing the RNG state ($seed)
#     and so should only be called once per next ping to calculate,
#     after calling prevping.
sub nextping { my($prev)=@_; return max($prev+1,round1($prev+exprand())); }

# Compute the last scheduled ping time before time t
sub prevping {
  my($t) = @_;
  $seed = $initseed;
  # Starting at the beginning of time, walk forward computing next pings
  # until the next ping is >= t.
  my $nxtping = $URPING;
  my $lstping = $nxtping;
  my $lstseed = $seed;
  while($nxtping < $t) {
    $lstping = $nxtping;
    $lstseed = $seed;
    $nxtping = nextping($nxtping);
  }
  $seed = $lstseed;
  return $lstping;
}
For posterity, a totally different approach for a different universal ping schedule

Alice Monday (@alice) and I came up with this together but we’ve never actually used this.

The advantage of this version is you could throw away all the fancy math and it would make sense to anyone how and why it works. The disadvantage is it’s more computationally intensive. Also it requires picking a kind of arbitrary parameter for the granularity – how far apart pings in principle can be. I’d suggest .125 seconds since that’s a safe lower bound on human reaction time. (I think the only way this matters is if you want unbiased data on how much time you spend answering TagTime pings.)

Also let’s call an eighth of a second an octant even though that’s sort of an abuse of terminology. We can get the current unixtime measured in octants by multiplying normal unixtime by 8. Or if you get unixtime in milliseconds, multiply it by 8/1000.

On to this alternate algorithm for a different universal ping schedule:

Every single unixtime (in octants) either has a ping or not. The probability of a ping is just 1/(45*60*8) — the denominator being the number of octants in 45 minutes. To make it universal you use the unixtime itself as the seed for the RNG for deciding if that octant has a ping. So, using the ran0 function above, unixtime t has a ping if:

IA * t % IM / IM < 1/(45*60*8)

i.e.,

16807 * t % 2147483647 < 99421

So you can start computing it at any time without worrying about history at all. Of course you don’t want to be running a loop doing a calculation 8 times per second so you walk forward, checking each unixtime (measured in octants) with the above inequality till you find the next one a ping will happen at (on average that means checking the inequality 21,600 times) and just sleep till then.

On reflection, I think it’s inferior to the mathy approach. For one thing, I don’t know if feeding very similar seeds to the RNG spoils it. Seems like it might.

PS: The current universal ping schedule artificially pushes pings forward to ensure that they’re always at least 1 second apart. So probably this version could just do seconds instead of eighths of seconds. Which maybe makes it computationally no big deal. Question remains about whether similar seeds spoils the RNG.

UPDATE: Similar seeds totally does spoil the RNG so forget the idea of using current unixtime as the seed. We could salvage this approach by starting at the dawn of (tag)time and walking forward. We’d only have to do that once when first launching the app.

1 Like