How does Tupper turn a number into a map?

February 2, 2007 5:37 AM

What's the binary encoding scheme (bitmap -> n) used in Tupper's Self-Referential Formula?

So I find Tupper's Self-Referential Formula pretty sweet. Wikipedia hints that Tupper created a formula that takes a binary bitmap encoded as a very large integer and returns 1/0s corresponding to the bitmap.

I feel like it shouldn't be too hard to figure out how to generate n from a given bitmap. I'm interested in being able to generate this n, additionally removing restrictions on the current dimensions of the bitmap by generalizing the formula. Unfortunately, I'm stuck as to how to do this, because I don't have a full grasp of how n -> bitmap. I'm seeing the obvious connection between the 17 rows in the y-dimension and the 17s that show up in the formula, but I'm not much beyond that.

Check out the Wikipedia article for more links and the original paper the formula was published in.

Also, here's some Matlab (R7.3) code, (requires the Symbolic toolbox), which generates the bitmap. It takes about 5 minutes to run on my new laptop.

n = vpa('960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719',600);
aMod = @(m,n) vpa(sym(m-n*floor(m/n)),600);
evalTupper = @(x,y) (floor(aMod(floor(y/17)*2^(-17*floor(x)-aMod(floor(y),17)),2)));
for i=1:106
x = vpa(i-1,600);
for j=1:17
y = vpa(n-1+j,600);
map(i,j) = evalTupper(x,y);
end
end

mm = logical(double(map));
imagesc(mm(end:-1:1,:)')
axis equal
colormap('flag')

posted by onalark to Science & Nature (7 answers total)

hrmm, I just plotted this and got this. Am I missing something?
posted by gadha at 7:16 AM on February 2, 2007

There really isn't a binary encoding scheme involved here. You're just determining if a given pair of numbers x and y, belong to a set based on an inequality.

(x,y) belongs in the set (and so gets lit up on the graph) if 1/2 < f(x,y)br>
It's the same kind of procedure that generates the Mandlebrot set fractal for instance (without colouring pixels according to how hard they were to remove from the set)

I'm not a mathematician but I see two things that worry me about extracting n from a given graph. First is the floor operator. The floor operator truncates everything to the right of the decimal point. So 3.00001 becomes 3 and 3.99999 also becomes 3. The second is the modulus operator though it seems like it would be less of an issue.
posted by substrate at 7:25 AM on February 2, 2007

The binary encoding scheme is binary multiplied by 17, as Wikipedia says. The whole formula is an elaborate way of reading bits from n.

- (-17*floor(x)-aMod(floor(y),17) creates an address from the x and y coordinates that can be used to select a particular bit from the data.
- floor(y/17)*2^address shifts the data to the right (note the negative above) such that the wanted binary digit is next to the decimal point.
- The rest reads that digit, providing a simple 0 or 1 to be plotted.

The first part indicates the encoding is column by column, and that each column is 17 bits long. I'm too lazy to figure out which direction the scanning is in (up or down, left or right).

The data is multiplied by 17 to ensure it doesn't change as it scans up each column (ie floor(y/17) always returns the same number)
posted by cillit bang at 7:34 AM on February 2, 2007 [1 favorite]

Best answer: If you take n and divide it by 17 and convert to binary, you get a very long number, the last few digits of which are:

000000100101000001100001000100001100111000000011100100001111111000001000000000000000011111111111111111

If you split that into groups of 17 digits:

000000100101000001100001000100001100111000000011100100001111111000001000000000000000011111111111111111

Replacing the zeroes with spaces:

      1  1 1     11    1   1    11  111       111  1    1111111     1                11111111111111111

That's the rightmost part of the formula, sideways. Here's the whole thing:

  11  1 1 1   1    1 1 1 1 11111    1  1  1 1                               1               1 1             1   1                       111111111111111111                1     1111                1             111                 1             111                                11              1  1             1  1              11                                11              1  1             1  1             111111                           1111111       111       111  11             11                 1111111111111111 1                1 11111 1                1 1 11     11  1 1  1     1   111 1   11   1                1111111111111111                        11  1            1 1  1           1  1 1           1   1   1                1                               11111                             11  1              111                          11111111         1                1  1 1               1            1  1 1           1                11111111                               1                1                               111                1              111                1              11                                111              1 1              111                               111              1 1              11111                            1111           11    11                          11111111         1                1 1 11              1             1   11           1                11111111                          1                 11                                  11111                             11  1              111                          11    11   1       1111      11                                  11  1            1 1  1           1  1 1     11    1   1    11  111       111  1    1111111     1                11111111111111111

So creating your own images is as simple as mapping them out as a long binary number and multiplying by 17 (the bc utility in Unix will do that for you).
posted by cillit bang at 8:06 AM on February 2, 2007

Oh my God cillit bang. It's full of stars.
posted by Plutor at 9:53 AM on February 2, 2007

Response by poster: Damn cillit, I couldn't make it happen when I was staring at it earlier. I'll play around and see if I can get that to show up. In the meantime, any reproducable shell code to translate a simple binary-encoded map into a new n would be welcome!
posted by onalark at 12:15 PM on February 2, 2007

Response by poster: gadha: Looks like some bad voodoo in the code, I was really tired when I posted this, you might want to try from the Wikipedia article's source and re-derive the expression.
posted by onalark at 12:21 PM on February 2, 2007