How does Tupper turn a number into a map?
February 2, 2007 5:37 AM Subscribe
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')
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')
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
(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]
- (-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:
posted by cillit bang at 8:06 AM on February 2, 2007
000000100101000001100001000100001100111000000011100100001111111000001000000000000000011111111111111111
If you split that into groups of 17 digits:
000000100101000001100001000100001100111000000011100100001111111000001000000000000000011111111111111111Replacing the zeroes with spaces:
1 1 1 11 1 1 11 111 111 1 1111111 1 11111111111111111That'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 11111111111111111So 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
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
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
posted by onalark at 12:21 PM on February 2, 2007
This thread is closed to new comments.
posted by gadha at 7:16 AM on February 2, 2007