Beeminder Forum

Official Reference Implementation of the TagTime Universal Ping Schedule


#1

This was previously in another (other) thread but that thread morphed into a discussion about a possible new algorithm so this is now the official home of the official reference implementation of the official algorithm for the universal ping schedule. It’s really official, ok? Until we reach consensus in that other thread, this is the algorithm all TagTime clients should implement!

First some constants and global variables:

const GAP = 45*60         // Average gap between pings, in seconds
const URPING = 1184097393 // Ur-ping ie the birth of Timepie/TagTime! (unixtime)
const SEED   = 11193462   // Initial state of the random number generator
const IA = 16807          // =7^5: Multiplier for LCG random number generator
const IM = 2147483647     // =2^31-1: Modulus used for the RNG

// Above URPING is in 2007 and it's fine to jump to any later URPING/SEED pair
// like this one in 2018 -- URPING = 1532992625, SEED = 75570 -- without
// deviating from the universal ping schedule.

let pung = URPING // Global var with unixtime (in seconds) of last computed ping
let state = SEED  // Global variable that's the state of the RNG

Here are the functions for generating random numbers in general:

// Linear Congruential Generator, returns random integer in {1, ..., IM-1}.
// This is ran0 from Numerical Recipes and has a period of ~2 billion.
function lcg() { return state = IA * state % IM } // lcg()/IM is a U(0,1) R.V.

// Return a random number drawn from an exponential distribution with mean m
function exprand(m) { return -m * Math.log(lcg()/IM) }

Here’s the only other helper function we need:

// Every TagTime gap must be an integer number of seconds not less than 1
function gap() { return Math.max(1, Math.round(exprand(GAP))) }

And here are the functions to compute successive ping times:

// Return unixtime of the next ping. First call init(t) and then call this in
// succession to get all the pings starting with the first one after time t.
function nextping() { return pung += gap() }

// Start at the beginning of time and walk forward till we hit the first ping 
// strictly after time t. Then scooch the state back a step and return the first
// ping *before* (or equal to) t. Then we're ready to call nextping().
function init(t) {
  let p, s          // keep track of the previous values of the global variables
  [pung, state] = [URPING, SEED]                       // reset the global state
  for (; pung <= t; nextping()) { [p, s] = [pung, state] }       // walk forward
  [pung, state] = [p, s]                                        // rewind a step
  return pung                               // return most recent ping time <= t
}

Protypical usage is like so:

p = init(now)
print "Welcome to TagTime! Last ping would've been at time {p}."
repeat forever:
  p = nextping()
  while now < p: wait
  print "PING! What are you doing right now, at time {p}?"

Note that in Javascript you get current unixtime in seconds with Date.now()/1000 (just Date.now() returns it in milliseconds).

I have the above code running in Glitch here:

https://glitch.com/edit/#!/join/dba4e4c4-a19d-48a8-8ca0-8021ea7c90e8 (see pub/client.js)


Announcing Trak, an alternative to TagTime
Possible new TagTime universal ping algorithm
#2

Shall we collect implementations in other languages? Here’s Mathematica:

GAP = 45*60;
URPING = 1532992625;
SEED = 75570;
IA = 16807;
IM = 2147483647;
pung = URPING;
state = SEED;

lcg[] := (state = Mod[IA*state, IM])

exprand[m_] := -m*Log[lcg[]/IM]

gap[] := Max[1, Round[exprand[GAP]]]

nextping[] := (pung += gap[])

init[t_] := Module[{p, s},
  For[{pung, state} = {URPING, SEED}, pung <= t, nextping[], {p, s} = {pung, state}];
  {pung, state} = {p, s};
  pung]

#3

My app has an initial state of showing the output of prevping(now) for the initial input, otherwise the screen would be blank. I can get around not having it by doing init(), and a while() {jump()} loop, except there is now also no init with no parameters! Can I propose adding an init with no parameters to explicitly reset the random number state and pung = URPING? Other workarounds I can think of are ugly exposing the internals of the algorithm to the caller.


#4

Crap, you’re right. I’ll bring back a nicer way to get the previous ping.

http://dreev.commits.to/bring_back_prevping

PS: I did it, in a maybe highly overnerded way. Like instead of just remembering the previous ping from when we walked forward the first time, I worked out the way to rewind the random number generator from any point. Which was almost going to be super simple and elegant to do but then there was a math overflow problem and I had to pull in the multmod function. Which maybe is a nice thing to have anyway, if we wanted an RNG with longer period or something.

PPS: Ok, that was a ridiculous rationalization for a bunch of number theory and as fun as that was, the reference implementation should be as straightforward as possible and that means just remembering the previous ping from when we walk forward. So that’s what it’s doing again! Thanks for the catch, @dpangier!


#5

SWIFT (Updated to track revisions relating to prevping)

Since I have abstracted away the implementation for both the classic and the proposed new implementation I have used a protocol. I have also consciously chosen that the protocol represents the API exposed to the application, so should work with the higher level type of Date rather than the implementation detail of unix seconds.

This stops internal details leaking…

protocol PingTimes {
    init(t: Date)
    var current: Date { get }
    func nextping() -> Date
}

And, I have separated out the RNG…

class Random {
    let IA = 16807
    let IM = 2147483647
    
    let initseed = 26506
    var seed: Int
    var lastseed: Int!
    
    init() {
        seed = initseed
    }
    
    func rewind() {
        seed = lastseed!
        lastseed = nil
    }
    
    func ran0() -> Int {
        lastseed = seed
        seed = IA*seed % IM
        return seed
    }
    
    func ran01() -> Double {
        return Double(ran0()) / Double(IM)
    }
    
    func exprand(gap: Double) -> Double {
        return -gap * log(ran01())
    }
}

And finally, the algorithm itself…

class PingTimesClassic : PingTimes {
    let URPING = 1443641796
    let gap = 45.0*60.0
    fileprivate var random = Random()
    var pung: Int
    
    required init(t: Date) {
        pung = URPING
        var lastpung: Int!
        while (current < t) {
            lastpung = pung
            _ = nextping()
        }
        pung = lastpung!
        random.rewind()
    }

    var current: Date {
        get {
            return Date(timeIntervalSince1970: TimeInterval(pung))
        }
    }
    
    func nextping() -> Date {
        let expr = random.exprand(gap: gap).rounded()
        pung = max(pung+1, pung+Int(expr))
        return current
    }
}

This is still not quite as clean as I would like it (but it has no global state and is unit testable).