Словарь и факториал больших чисел

Question

Для n запросов мне дано число x, и я должен напечатать его factorial по модулю 1000000007.

def fact_eff(n, d):

    if n in d:
        return d[n]
    else:
        ans=n*fact_eff(n-1,d)
        d[n]=ans
        return ans

d={0:1}
n=int(input())
while(n!=0):
    x=int(input())
    print(fact_eff(x, d)%1000000007)
    n=n-1

Проблема в том, что x может достигать 100000 и Я получаю ошибку времени выполнения для значений больше 3000, так как максимальная глубина рекурсии превышает. Я что-то упустил с оператором модуля?

Answer 1

Зачем вам в первую очередь использовать рекурсию для вычисления простого факториала? Вы можете проверить словарь в al oop. Или, лучше, начните с наивысшей действительной запомненной позиции и на go выше, создавая новые записи, когда вы go.

Чтобы сэкономить место, возможно, только записывайте n! каждые 32 итерации или что-то подобное, так для будущих звонков нужно не более 31 умножения. Тем не менее, O (1), но тратят некоторые вычисления на огромную экономию места.

Кроме того, работает ли это, чтобы применить модуль, прежде чем вы получите конечный огромный продукт? Как каждые несколько шагов умножения, чтобы числа были маленькими? Или каждый отдельный шаг, если эти числа достаточно малы для быстрого пути CPython. Я думаю (x * y) % n = ((x%n) * y) % n. (Но я не проверял это дважды.)

Если это так, вы могли бы объединить раннее по модулю с редким запоминанием, чтобы запоминать окончательный результат по модулю.

(Для чисел выше 2 ^ 30, Python Стоимость умножения BigInteger должна масштабироваться с количеством 2 ^ 30 кусков, необходимых для представления числа. К счастью, один из множителей всегда маленький, являясь счетчиком. Сохранение продукта маленьким покупает скорость, но деление дорого, так что это компромисс. И выполнение каких-либо дополнительных операций стоит Python накладных расходов интерпретатора, которые могут в любом случае просто доминировать, пока числа не станут действительно огромными.)