Artisinal integers, part 2

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.

2^53 is another practical limit, since that’s the biggest integer Javascript can handle (and then, only if you’re lucky). Sites can only generate about two million integers before hitting 2^53. That’s low enough to cause a real crisis in artisinal integers, particularly for the Node.js hipsters.

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. 

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),

for i in "0 2 5 9 14 20 27 35 44 54".split():
    print invCantor(int(i)),

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))