Неточные значения в формуле Таппера

Question

Я пытаюсь создать программу на Python, которая построит самореференциальную формулу Таппера, и я столкнулся с некоторыми проблемами.

Сначала моя программа не могла обрабатывать большие поплавки, поэтому пришлось использовать BigFloats разобраться в моих проблемах. Это сработало, вроде. Моя проблема в том, что у меня есть 540-значный длинный номер, который нужно умножить на BigFloat и когда я делаю это, оно округляет число, делая его неточным, что вызывает проблемы позже. Я пытался поднять precision до 1000, и он все еще продолжает округлять переменную.

Дело в том, что некоторые числа могут быть обработаны без BigFloat до точного значения, но некоторые числа не могут быть обработаны ни нормально, ни с BigFloat прямо сейчас.

Вот один из расчетов, который идет не так (этот может быть обработан без BigFloat):

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

Этот код должен возвращать 1, но вместо этого он возвращает 0.

Есть ли способ сделать BigFloat точнее, чтобы я мог использовать его в своей программе?

Answer 1

Вам не нужна математика с плавающей точкой для формулы Таппера. Хитрость в том, что 2-^x такой же, как 1/2^x, поэтому вам нужно работать только с целыми числами, потому что вам не нужно вычислять число с плавающей точкой 2^-x и умножать его на целое число, а вместо этого вычислять целое число 2^x и разделите другое целое число на это целое число. Применительно к формуле Таппера часть 2^{-17 * int (x) - int (y)% 17} становится 1/2^{17 * int (x) + int (y)% 17}.

Смотрите следующую версию функции Таппера, которая полностью работает в целочисленной области (если вы не знаете, что ** это оператор питания Python):

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

Вы можете проверить эту функцию с помощью следующего кода, который "рисует" результат формулы Таппера в текстовый файл.

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)

Результатом является файл tupper.txt с содержанием:

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