Неточные поплавки в самореферентной формуле Tupper

Question

Я пытаюсь сделать программу Python, которая отображает Tupper's self-referential formula, и у меня возникли некоторые проблемы.

Сначала моя программа не могла справиться с большими поплавками, с которыми ей приходилось обращаться, поэтому я решил использовать 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'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 

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

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 с содержанием:

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