не удалось ввести большое целое число

Question

В последнее время я работаю над некоторым проектом. Проблемы Эйлера

Наименьшее кратное

Задача 5

2520 - это наименьшее число, которое можно разделить на каждое из чисел от 1 до10 без остатка.

Какое наименьшее положительное число, которое делится равномерно на все числа от 1 до 20?

Я написал свой код, он прекрасно работает

def factor_finder(n, j=2):

    factor_list = []

    if n == 2:
        return [2]
    elif n == 3:
        return [3]
    else:
        while n >= j * 2:
            while n % j == 0:
                n = int(n / j)
                factor_list.append(j)
            j += 1

    if n > 1:
        factor_list.append(n)

    return factor_list



def smallest_multiples(n):

    from functools import reduce

    factor_list = []
    final_list = []

    for i in range(2, n + 1):
        factor_list += factor_finder(i)
    # print(factor_list)

    for i in set(factor_list):
        l1 = []
        l2 = []
        for j in factor_list:
            if j == i:
                l1.append(j)
            else:
                if len(l1) > len(l2):
                    l2 = l1
                    l1 = []
                else:
                    l1 = []
        # print(l2)
        final_list += l2
    # print(final_list)

    return (
        np.array(final_list).cumprod()[-1],
        reduce((lambda x, y: x * y), final_list),
    )

Результат:

% времени

smalllest_multiples (1000)

Время ЦП: пользователь 5 мкс, sys: 0 нс, всего: 5 мкс Время стены:32,4 мкс

(- 4008056434385126912, 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000)

Мой вопрос: почему numpy.cumprod () не удалось получить правильный номер.Я думал, что NumPy это инструмент номер.Кто-нибудь может дать мне какую-то идею?

Answer 1

Проблема в том, что число достигло размера, что означало, что оно больше не может быть представлено целыми числами в Python.Если вы посмотрите здесь , вы увидите, что максимальный размер ints составляет около 19 цифр (то есть 2 ^ 63 из 63 бит + знаковый бит), а затем переходит в переполнение.Numpy основан на C, который использует фиксированную точность для гораздо более быстрых вычислений с компромиссом, который ограничен 64-битным целым числом и будет переполнен.Некоторые функции в numpy даже защищают от этого, конвертируя в числа с плавающей точкой для выполнения вычислений, которые могут содержать еще больше цифр.

Если вы скажете, что numpy использует «объект» в качестве типа данных, существует значительное время, но это 'Позвольте вам использовать произвольную точность, к которой вы привыкли в Python.Для вашего кода это будет выглядеть так:

return (
    np.cumprod(final_list, dtype="object")[-1],
    reduce((lambda x, y: x * y), final_list),
)

Подробнее о переполнении в numpy.

Answer 2

Численный анализ - это не теория чисел.Правильность - не единственная цель, но ее необходимо сопоставлять с эффективностью.Числа произвольной точности (например, большие целые числа) являются медленными, поэтому по умолчанию для numpy используются целые числа фиксированной длины.Они просто переполняются, когда они становятся слишком большими.Вы можете указать numpy использовать произвольные целые числа точности, но вы потеряете большую часть его скорости:

np.arange(1, 100).prod() # fast but wrong
# 0
np.arange(1, 100, dtype=object).prod() # slow but correct
# 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000