Какие технические ограничения мешают вычислению числа Грэма в питоне?

Предполагая, что компьютер, на котором работает эта программа, имеет бесконечный объем памяти, меня интересует, где Python сломается при выполнении следующего:

Ради интереса я реализовал гипероператоры в python в виде модуля hyperop. Один из моих примеров — число Грэма:

def GrahamsNumber():
    # This may take awhile...
    g = 4
    for n in range(1,64+1):
        g = hyperop(g+2)(3,3)
    return g

Сокращенная версия класса hyperop выглядит так:

def __init__(self, n):
    self.n = n
    self.lower = hyperop(n - 1)

def _repeat(self, a, b):
    if self.n == 1:
        yield a

    i = 1
    while True:
        yield a
        if i == b:
            break
        i += 1

def __call__(self, a, b):
    return reduce(lambda x, y: self.lower(y, x), self._repeat(a, b))

По сути, библиотека представляет собой просто рекурсивную операцию сгиба вправо со специальным определением для базовый случай n=1. Первоначально __call__ красиво играл в гольф как:

return reduce(lambda x, y: self.lower(y, x), [a,]*b)

Однако оказывается, что вы можете не создавайте список с большим количеством элементов, чем размер C long. Это было забавное ограничение, с которым большинство программистов Python, вероятно, не сталкиваются в своей обычной повседневной жизни, и оно вызвало следующий вопрос.

Где, если вообще произойдет, расчет hyperop потерпит неудачу из-за технических ограничений Python (в частности, 2.7.10)?


person Hooked    schedule 21.02.2016    source источник
comment
Поскольку наблюдаемая Вселенная слишком мала, чтобы вместить обычное цифровое представление числа Грэма, я откажусь. Главный совет: если вы должны начать с это законный вопрос, вы, вероятно, ошибаетесь!   -  person jonrsharpe    schedule 22.02.2016
comment
Это вопрос об использовании yield и бесконечных последовательностей или что-то, что можно сформулировать более кратко?   -  person user2864740    schedule 22.02.2016
comment
Ограничение большего количества элементов, чем размер C long, упоминается только для Python 2....   -  person PascalVKooten    schedule 22.02.2016
comment
@jonrsharpe Мы должны предполагать бесконечный объем памяти. Я бы сказал, что это на самом деле законный вопрос.   -  person Stefan Pochmann    schedule 22.02.2016
comment
@Hooked Что ты имеешь в виду под Python? CPython? ПиПи? Другая? И какая версия?   -  person Stefan Pochmann    schedule 22.02.2016
comment
@StefanPochmann, на мой взгляд, еще менее законно. Зачем делать одно произвольное исключение, а затем строить предположения о других?   -  person jonrsharpe    schedule 22.02.2016
comment
@jonrsharpe, возможно, я был слишком весел с комментарием, что это законный вопрос. Я просто хотел установить, что вопрос соответствует критериям легитимности SO в том смысле, что он объективен (не основан на мнении), имеет конкретную цель и воспроизводим.   -  person Hooked    schedule 22.02.2016
comment
@jonrsharpe Память - очевидная причина, по которой это невозможно в реальности. Есть ли какие-либо другие причины, совершенно не очевидно, и я думаю, что это законный вопрос.   -  person Stefan Pochmann    schedule 22.02.2016
comment
@PascalvKooten Хороший вопрос, я думаю, мне нужно выбрать версию Python, чтобы конкретизировать этот вопрос. Давайте установим для этого вопроса, что я использую python 2.7.10, хотя мне были бы интересны любые ответы на python 3. Я отредактирую соответственно.   -  person Hooked    schedule 22.02.2016
comment
Возможно, вы захотите отредактировать заголовок своего вопроса, поскольку ответ на заголовок, который у вас есть сейчас, очевидно, нет. Поскольку ваш вопрос на самом деле не о числе Грэма, а о технических ограничениях Python, вы можете получить лучший ответ, если переформулируете свой вопрос, сосредоточившись на конкретных ограничениях, налагаемых Python, а не на цели вычисления числа Грэма. Возможно, у Python есть другие скрытые ограничения, подобные тому, которое вы нашли для длин списков, но ваша конкретная программа не будет соответствовать этим ограничениям.   -  person BrenBarn    schedule 22.02.2016
comment
@BrenBarn хорошие моменты, и спасибо, что помогли мне разобраться в сути вопроса. Я отредактировал вопрос/заголовок, но если вы хотите внести дополнительные разъяснения, пожалуйста, не стесняйтесь редактировать.   -  person Hooked    schedule 22.02.2016


Ответы (1)


Возможно, исходная версия гипероперации надежна и дает сбой по какой-то эзотерической причине, но этот точный код дает сбой, потому что конструктор гипероперации вызывает сам себя и вызывает RuntimeError с «превышением максимальной глубины рекурсии» (после sys.setrecursionlimit рекурсивных вызовов, который равен 1000 в 2.7. 10 по умолчанию наверное).

person peroksid    schedule 31.03.2016