Now Reading
Demystifying Tupper’s formulation – Eli Bendersky’s web site

Demystifying Tupper’s formulation – Eli Bendersky’s web site

2023-05-22 21:51:13

A book I was recently reading talked about a
mathematical curiosity I have not seen earlier than – Tupper’s self-referential
formula
.
There are some sources about it on-line, however this submit is my try to
clarify the way it works – together with an interactive implementation you may strive
within the browser.

Tupper’s formulation

Right here is the formulation:

We wish to plot this formulation, however how?

For this goal, it is extra helpful to consider Tupper’s formulation not as a
operate however as a relation, within the mathematical sense. In Tupper’s paper
it is a relation on mathbb{R}, which means that it is a set of pairs
in that fulfill the inequality.

For our job we’ll use discrete indices for x and y, so the relation is
on . We’ll plot the relation by utilizing a darkish pixel (or
sq.) for a x,y coordinate the place the inequality holds and a light-weight pixel
for a coordinate the place it would not maintain.

The “mind-blowing” truth about Tupper’s formulation is that when plotted for
a sure vary of x and y, it produces this:

Tupper's formula own plot

Word that whereas x runs within the inclusive vary of 0-105 on the plot, y begins
at a mysterious Ok and ends at Ok+16. For the plot above, Ok must be:

4858450636189713423582095962494202044581400587983244549483
0930850619347047088099284506447698655243648499972470249151
1911041160573917740785691975432657185544205721044573588368
1829823754139634338225199452191651284348332905131193199953
5024137587652392648746133949068701305622958132194811136853
3953556529085002387509285689269455597428154638651073004910
6723058933586052544096664351265349363643957125565695936815
1843348576052669401612512669514215505395545191537854575257
5659074054015792900176596796548006442782913148854825991472
1248506352686630476300

The amazement subsides barely after we uncover that for a special Ok ,
we get a special plot:

Tupper's formula producing a pacman plot

And, in truth, this formulation can produce any 2D grid of 106×17 pixels, given the
proper coordinates. Because the formulation itself is so easy, it’s fairly obvious
that the worth of Ok is the important thing right here; these are enormous numbers with tons of of
digits, so clearly they encode the picture data one way or the other. Learn on to see
how this truly works.

A JavaScript demo

I’ve carried out a easy on-line demo of plotting the Tupper formulation – obtainable
at https://eliben.github.io/tupperformula/ (with source code on GitHub). It was used to supply the pictures
proven above. The code is pretty simple, so I am going to simply give attention to the
fascinating half.

The core of the code is a 2D grid that is plotted for x operating from 0 to
105 and y from Ok to Ok+16 (each ranges inclusive). The grid is populated
each time the quantity adjustments:

const GridWidth = 106;
const GridHeight = 17;
let Ok = BigInt(Knum.worth);

for (let x = 0; x < GridWidth; x++) {
    for (let y = 0; y < GridHeight; y++) {
        Grid.setCell(x, y, tupperFormula(BigInt(x), Ok + BigInt(y)));
    }
}

Word using JavaScript’s BigInt varieties right here – very helpful when dealing
with such enormous numbers. Right here is tupperFormula:

operate tupperFormula(x, y) {
    let d = (y / 17n) >> (17n * x + y % 17n);
    return d % 2n == 1n;
}

It appears to be like fairly completely different from the mathematical formulation on the prime of this submit;
why? As a result of – as talked about earlier than – whereas Tupper’s unique formulation works on
actual numbers, our program solely wants the discrete integer vary of
x in [0, 105] and y in [K, K+16]. Once we cope with discrete numbers,
the formulation might be simplified tremendously.

Let’s begin with the unique formulation and simplify it step-by-step:

Initially, since x and y are pure numbers, the ground operations on
them do not do something, so we will drop them (together with on the division by
17, if we simply assume integer division that rounds down by default):

Subsequent, since the results of the operation for a pure N is
both 0 or 1, the comparability to half is only a fancy means of claiming “equals 1”;
we will exchange the inequality by:

Word the destructive energy of two; multiplying by it’s the identical as dividing by its
constructive counterpart. One other strategy to categorical division by for pure
numbers is a bit shift proper by p bits. So we get the code of the
tupperFormula operate proven above:

let d = (y / 17n) >> (17n * x + y % 17n);
return d % 2n == 1n;

How the Tupper formulation works

The distillation of the Tupper to JS code already peels off a number of layers of
thriller. Let’s now take away the remainder of the curtain on its inside workings.

I am going to begin by explaining the right way to take a picture we would like the formulation
to supply and encode it into Ok. Listed here are the primary three columns of the
Tupper formulation plot:

Closeup of tupper plot with encoding of pixels

Every pixel within the plot is transformed to a bit (0 for mild, 1 for darkish). We
begin on the backside left nook (x=0 and y=Ok), which is the LSB
(least-significant bit) and transfer up by means of the primary column; after we attain the
prime (x=0 and y=Ok+16), we proceed from the underside of the subsequent column
(x=1 and y=Ok). Within the instance above, the primary bits (from lowest to highest)
of the quantity are:

00110010101000100 00101010101111100 ...

As soon as we’re finished with the entire quantity (106×17 = 1802 bits), we convert it to
decimal – let’s name this quantity IMG, and multiply by 17. The result’s Ok.

Now again to tupperFormula, the way it decodes the picture again from
x and y (recall that y runs from Ok to Ok+16). Let’s work by means of
the primary coordinate intimately:

See Also

For x=0 and y=Ok, in tupperFormula we get:

d = (y/17) >> (17x + ypercent17)
...
substitute x=0, y=Ok (and recall that Ok = IMG * 17)
...
d = IMG >> 0

In different phrases, d is the bottom little bit of IMG – the bottom little bit of our picture!
We will proceed for x=0 and y=Ok+1:

d = (y/17) >> (17x + ypercent17)
...
substitute x=0, y=Ok+1 (and recall that Ok = IMG * 17)
...
d = IMG >> 1

Right here d is the second lowest little bit of IMG. The sample ought to be clear by now.

d = (y/17) >> (17x + ypercent17)
...
x=0  y=Ok+2:  IMG >> (0 + 2)
x=0  y=Ok+3:  IMG >> (0 + 3)
...
x=0  y=Ok+16  IMG >> (0 + 16)
x=1  y=Ok:    IMG >> (17 + 0)
x=1  y=Ok+1:  IMG >> (17 + 1)
x=1  y=Ok+2:  IMG >> (17 + 2)

The formulation merely calculates the proper little bit of IMG given x and y, utilizing
a modular arithmetic trick to “fold” the 2D x and y right into a 1D
sequence (that is simply customary column-major layout).

Because of this the formulation can plot any 106×17 grid, given the appropriate Ok. Within the
formulation, 17 shouldn’t be some piece of magic – it is simply the peak of the grid. As an
train, you may modify the formulation and code to plot bigger or smaller grids.

As a bonus, the JavaScript demo can even encode a grid again to its
consultant Ok; this is the code for it:

// Calculate Ok worth from the grid.
operate encodeGridToK() {
    let kval = BigInt(0);

    // Construct up Ok from MSB to LSB, scanning from the top-right nook down and
    // then transferring left by column.
    for (let x = GridWidth - 1; x >= 0; x--) {
        for (let y = GridHeight - 1; y >= 0; y--) {
            kval = 2n * kval + BigInt(Grid.getCell(x, y));
        }
    }
    return kval * 17n;
}

It constructs Ok beginning with the MSB, however in any other case the code is
simple to observe.

Background

The formulation was first describe by Jeff Tupper in a 2001 paper titled
“Dependable Two-Dimensional Graphing Strategies for Mathematical Formulae with Two
Free Variables”. The paper itself focuses on strategies of exactly graphing
relations and presents a number of algorithms to take action. This formulation is described
in passing in part 12, and introduced as follows:

Screenshot from Tupper's paper describing the formula

And Determine 13 is:

Screenshot from Tupper's paper showing the formula itself

Curiously, the Ok supplied by Tupper’s paper renders the formulation flipped
on each the x and y axes utilizing the usual grid used on this submit .
Because of this my JavaScript demo has flip toggles that allow you to flip the axes of any
plot.


1445202489708975828479425373371945674812777822151507024797
1881396854908873568298734888825132090576643817888323197692
3440016667764749242125128995265907053708020473915320841631
7920255490054180047686572016997304663833949016013743197155
2099618114524978194501906835950051065780432564080119786755
6863142280259694206254096081665642417367403946384170774537
4273196064438999230103793989386750257869294552344763192918
6095761834543224800492172803334941981620674985447203819393
9738513848960476759782673313437697051994580681869819330446
336774047268864

Source Link

What's Your Reaction?
Excited
0
Happy
0
In Love
0
Not Sure
0
Silly
0
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top