Numba делает вычислительные ошибки

Question

Я недавно узнал про библиотеку Numba для ЯП Python, чтобы ускорять программу за счёт компиляции функций. Как только я установил её, я сразу решил опробовать код, который вычисляет факториал 999.

from numba import njit, prange

@njit(parallel=True)
def main():
    s = 1
    for i in prange(1, 1000):
        s *= i
    print(s)
main()

Однако, на выходе я неожиданно получал 0! Я попробовал с 99 - та же история. Решил с 9 и всё нормально. По идее, данный код должен более чем работать (никаких структур, которые Numba не понимает нету), однако, результат неадекватен от слова совсем. Пожалуйста, объясните, что могло пойти не так. Кроме ЯП Python, так уж вышло, я не знаю, поэтому если проблема связана со стороны C, распишите так, чтобы было понятно тому, кто никогда не сталкивался с низкоуровневыми конструкциями. Спасибо!

Answer 1

У вас переполняется тип Int64 (его размер во всех языках программирования примерно одинаковый). Причём, происходит это гораздо раньше, в чём можно убедиться благодаря следующему коду:

from numba import njit, prange

@njit(parallel=True)
def main(n):
    s = 1
    for i in prange(1, n + 1):
        s *= i
    return s

flag = True
for i in range(1, 1000):
    s = main(i)
    if (s < 0 and flag) or s == 0:
        print(f'{i-1}! = {main(i-1)}\n{i}! = {main(i)}')
        if not flag:
            break
        flag = False

Вывод:

20! = 2432902008176640000
21! = -4249290049419214848
65! = -9223372036854775808
66! = 0

То есть фактически переполнение произошло уже на 21! и произведение превратилось в отрицательное, дальше его ещё сколько-то поколбасило, но в один момент заколбасило так удачно, что произведение превратилось в 0 и дальше уже понятно, ноль можно умножать сколько угодно, дальше ничего не поменяется.

Почему такого не происходит в "обычном" питоне? Потому что в обычном питоне тип int фактически бесконечный. Он из-за этого работает несколько более медленно, но зато не имеет таких ограничений.

Забавно, что если сделать s числом с плавающей точкой, то эффект будет другой:

    s = 1.0
    ...
    if (s < 0 and flag) or s == 0 or s == float('inf'):
        print(f'{i-1}! = {main(i-1)}\n{i}! = {main(i)}')
        if not flag or s == float('inf'):
            ...

Вывод:

170! = 7.257415615307999e+306
171! = inf

Таким образом, переполнение типа с плавающей точкой происходит позже и более корректно - число превращается в бесконечность.

В общем, вам нужно почитать про типы данных и про переполнение, если хотите разобраться в вопросе. Но вообще факториал растёт очень быстро с каждым шагом и на практике такие большие числа обычно просто не используются.

Answer 2

Хм, а вы представляете себе, что 999! которое вы пытаетесь вычислить - это число с 2565 десятичными цифрами. И даже 99! - имеет в своем представлении 154 цифры. Рискну его здесь записать:

9426890448883247745626185743057242473809693764078951663494238777294707070023223798882976159207729119823605850588608460429412647567360000000000000000000000

Такое число в компьютере "просто так" представить невозможно, а уж работать и подавно. Да, в базовом Python теоретически можно представить целое число с (почти) неограниченным числом десятичных цифр, вот только другие пакеты с такими числами работать не будут.

БЛОГ НА HUSL

Numba делает вычислительные ошибки

Ответы (2 шт):