Imprecise floats in Tupper's self-referential formula

Question

I am trying to make a Python program that plots Tupper's self-referential formula and I have run into some problems.

First my program couldn’t handle the big floats it had to handle so I decided to use BigFloats to sort out my problems. It worked, sort of. My problem is that I have a 540 digits long number that needs to be multiplied with a BigFloat and when I do that it rounds the number making it inexact which cause problems later. I have tried to raise the precision to 1000 and it still keeps rounding the variable.

The thing is that some of the numbers can be processed without BigFloat to the exact value but some numbers can neither be processed normally nor with BigFloat right now.

Here is one of the calculations that goes wrong (this one is able to be processed without BigFloat):

import bigfloat
y = 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719
x = 0
with bigfloat.precision(1000):
    (y//17 * bigfloat.pow(2,0)) % 2

That code should return 1 but instead it returns 0.

Is there a way to make BigFloat more accurate so I can use it in my program?

To the `bigfloat` problem: (1) don't use bigfloat; use gmpy2 instead, and (2) the precision in bigfloat is the number of *bits*, not the number of decimal digits. For 540 digits, you'd need about 1800 bits of precision. If you try with a precision of 2000, you'll see the `1` that you expect. — Mark Dickinson, Apr 23 '15 at 19:35

halex · Accepted Answer · 2015-04-22T19:30:39.033

You don't need any floating point math for Tupper's formula. The trick is that 2^-x is the same as 1/2^x so you only have to work with integers because you do not need to calculate the floating point number 2^-x and multiply it with an integer but instead calculate the integer 2^x and divide an other integer by this integer. Applied on Tupper's formula the 2^{-17*int(x) - int(y)%17} part becomes 1/2^{17*int(x) + int(y)%17}.

See the following version of Tupper's function that completely operates in integer domain (in case you do not know what ** is, it is Python's power operator):

def tuppers_formula(x, y):
    """Return True if point (x, y) (x and y both start at 0) is to be drawn black, False otherwise
    """
    k = 960939379918958884971672962127852754715004339660129306651505519271702802395266424689642842174350718121267153782770623355993237280874144307891325963941337723487857735749823926629715517173716995165232890538221612403238855866184013235585136048828693337902491454229288667081096184496091705183454067827731551705405381627380967602565625016981482083418783163849115590225610003652351370343874461848378737238198224849863465033159410054974700593138339226497249461751545728366702369745461014655997933798537483143786841806593422227898388722980000748404719
    return ((k + y)//17//2**(17*int(x) + int(y)%17))%2 > 0.5

You can test this function with the following code that "draws" the result of Tupper's formula into a text file.

import codecs
import os
with codecs.open("tupper.txt", "w", "utf-8") as f:
    values = [[tuppers_formula(x, y) for x in range(106)] for y in range(17)]
    for row in values:
        for value in row[::-1]: # x = 0 starts at the left so reverse the whole row
            if value:
                f.write("\u2588") # Write a block
            else:
                f.write(" ")
        f.write(os.linesep)

The result is the file tupper.txt with the content:

        █                   █                █ ██ █     █                █  █ █     █    █ ██ █      █   █
        █                   █ █      █       █  █ █     █                █  █ █     █    █  █ █      █   █
██      █                  █  █      █    ██ █  █ █ █ █ █ ██ ████  ███ ███ █  █ █ █ █    █  █  █      █  █
 █      █                  █  █  █ █ █       █ █  █  █  █    █ █ █ █ █ █ █ █  █ █ █ █    █ █   █      █  █
 █      █                  █  █  █ █ █       █ █  █ █ █ █    █ █ █ ███ ███ █  █  █  █    █ █   █      █  █
 █      █               █ █   █   █  █  ██        █     █                  █  █ █   █  █       █   ██  █ █
███   █ █               █ █   █  █   █ █  █       █     █                   █ █     █  █      █   █  █ █ █
     █  █ ██ █   ██   ███ █   █      █   █        ███ ███                   █ ███ ███ █       █     █  █ █
███ █   █ █ █ █ █  █ █  █ █   █ ████ █  █                                                          █   █ █
     █  █ █ █ █ █  █ █  █ █   █      █ █                                                          █    █ █
██    █ █ █ █ █  ██   ███ █   █ █ ██ █ ████                                                       ████ █ █
  █     █                 █   █ █  █ █                                                          █      █ █
 █      █                  █  █ █  █ █                                                          █     █  █
█       █                  █  █ █ █  █                                                         █      █  █
███     █                  █  █ █ █  █                                                                █  █
        █                   █ █      █                                                               █   █
        ███                 █ ███  ███                                                               █ ███

Thank you for your answer. I got my code to work (I already had a way of plotting the function). But there is still one thing that I can't understand about the formula. If y and x are always integers, then why do you need to take the floor of both of them ("2^-17*floor(x)-mod(floor(y),17")? — Alexander Simko, Apr 23 '15 at 18:48

Imprecise floats in Tupper's self-referential formula

1 Answers1