The connoisseurs of fine artisinal integers discovered my blog post about Cantor pairing and asked some questions. Apparently there’s a sudden interest in creating more foundries and my proposal for allowing an infinite number of sequences thanks to the magic of infinity got some reading. However, taking advantage of that infinity requires an O(n^2) generator algorithm, a bit impractical. How impractical?
One reasonable question is “when do we generate integers bigger than 2^64?”, since that’s such an awkward number for our 64-fingered CPUs. With the current simple even/odd split for two foundries, we can generate 2^63 integers before running out of room, so many it’s hard to call them artisinal really. But with the Cantor numbering we hit 2^64 much sooner: it will be site #3,327,948,883 generating its 2,746,052,116th number that is 2^64. Or to put it in plain English, every foundry gets to generate about two billion integers before hitting the limit.
I submit the practical solution is to pick a large fixed number of integer foundries, say 1000, and simply have each foundry agree to generate numbers in the sequence (eg) 1003, 2003, 3003, 4003. It lacks elegance but is probably sufficient to meet demand. It also sets up a perfect excuse for a hipster sellout should the demand for artisinal foundries explode and the number boffins need to start paying for their fixed gear bicycles and ironic bottled beers; simply start charging for those last few valuable foundry IDs. Scarcity is the business model’s best friend.
#!/usr/bin/env python # Cantor pairing function, a bijection from Z*Z to Z. # https://nelsonslog.wordpress.com/2012/07/29/artisinal-integers/ # http://en.wikipedia.org/wiki/Cantor_pairing_function#Cantor_pairing_function import math def cantor(x, y): return (x + y) * (x + y + 1) / 2 + y # could cache calculations for efficiency def _w(z): n = math.sqrt(8*z + 1) return int(math.floor((n-1)/2)) def _t(z): w = _w(z) return (w*w + w) / 2 def invCantor(z): t = _t(z) w = _w(z) y = z - t x = w - y return (x, y) for i in range(0,10): print cantor(0, i), print for i in "0 2 5 9 14 20 27 35 44 54".split(): print invCantor(int(i)), print print cantor(18225714/2, 1) print invCantor(41522085907653) for power in 64, 43: biggy = 2L ** power x, y = invCantor(biggy) print biggy, (x, y), (math.log(x, 2), math.log(y, 2))