В функции four_squares программа выдает ошибку как только обращается, и почему не проходит тест с этим числом 106369249365575352836589875696130383747?

Question

[Андрей Прохоренко]

И как исправить эту ошибку
Мне нужен ответ как исправить а что за ошибка я уже вкурсе.

import numba
from numba import njit, prange
from typing import Tuple
import numpy as np
from functools import lru_cache


@lru_cache(maxsize=256)
@numba.njit(parallel=True, fastmath=True, error_model='numpy')
def four_squares(n: np.int64) -> Tuple[np.int64, np.int64, np.int64, np.float64]:
    for a in prange(np.float64(n**0.5) + 1):
        for b in prange(np.float64((n - a**2)**0.5) + 1):
            for c in prange(np.float64((n - a**2 - b**2)**0.5) + 1):
                d = np.float64(np.round((n - a**2 - b**2 - c**2)**0.5))
                if a**2 + b**2 + c**2 + d**2 == n:
                    return a, b, c, d
    return np.int64(0), np.int64(0), np.int64(0), np.float64(0)


def main() -> None:
    for i in [0, 1, 17, 33, 215, 333, 2**12-3, 1234567890, 10_313_546_885_799_053_312]:
        a, b, c, d = four_squares(i)
        error_msg = None
        s = a * a + b * b + c * c + d * d
        if s != i:
            error_msg = f"Incorrect sum.\nSquares: [{a}, {b}, {c}, {d}]\nActual: {
                a * a + b * b + c * c + d * d}\nExpected: {i}"
        if error_msg is not None:
            print(error_msg)
        else:
            print("Решение принято")


if __name__ == "__main__":
    main()

Возникает ошибка

Traceback (most recent call last):
  File "c:\tradesignals\main22.py", line 35, in <module>
    main()
  File "c:\tradesignals\main22.py", line 22, in main
    a, b, c, d = four_squares(i)
                 ^^^^^^^^^^^^^^^
OverflowError: int too big to convert

c числом 1_313_546_885_799_053_312 все тесты проходят быстро

Answer 1

[Vindicar]

В питоне встроенный int поддерживает длинную арифметику, поэтому с ним можно выполнять операции даже если операнды превышают 64 бита. Но это, разумеется, медленнее, чем аппаратно-поддерживаемое число.

Comments

[Андрей Прохоренко]

Допустим я сделаю но у меня этих иттераций - 8 227 278(это только для числа 1_313_546_885_799_053_312 только а там еще в 10 больше) уже и когда буду использовать медленный int оно выполняться вечность без низкоуровнего ускорения. Я так и делал как ты предлагаешь ранее, но мой код работал медленно очень.. А тут в моем коде низкоуровневый ускоритель с отключенным интерпретатором, который не поддерживает встроенный int

[Vindicar]

Андрей Прохоренко, я не удивлюсь, если тесты для задачи подобраны именно так, чтобы срубить такие "прямолинейные" решения. Значит, нужно искать алгоритмические оптимизации.

Например, твой вариант сначала проверит 0**2 + 0**2 + 0**2 + d**2 = n, что заведомо невыполнимо для большинства n. Аналогично, будет ряд ситуаций когда ты проверяешь сначала случай a=0, b=0, c=1, потом a=0, b=1, c=0, потом a=1, b=0, c=0, хотя все эти случаи равноценны.

Мне кажется, чтобы ускорить процесс, нужно гарантировать или a > b > c, или a < b < c.
Первое проще всего гарантировать, если делать перебор вариантов в обратном порядке, к нулю. Но можно и просто вести перебор b и c не до оставшегося максимума, а до a и b соответственно.

Answer 2

[Довольный Айтишникъ]

int too big to convert

Это сообщение вам ни о чем не говорит? В int это число просто не помещается, используйте float, long или что-то подобное.

Comments

[Андрей Прохоренко]

Что за сообщение я знаю как раз уже
А как избавиться от сообщения есть ли какие то решения чтоб выполнить с этим числом
выше чем float64 уже так float128 уже нет типа такого и long тоже такого нету

[Довольный Айтишникъ]

Андрей Прохоренко, нуу, судя по этой странице есть еще long, complex https://tedboy.github.io/python_stdlib/05_builtin_...

[Андрей Прохоренко]

Довольный Айтишникъ, Это тоже пробовал complex и long как с numpy так и без numpy и не помогло ничего и лучше не просто ссылки а чтобы они были подтвержденные кодом что этот тип поддерживает большее число

[Влад Григорьев]

Андрей Прохоренко, ну можешь попробовать с обычным int - встроенным, в него все войдет.
но будет медленнее

[Андрей Прохоренко]

Влад Григорьев, Допустим я сделаю но у меня этих иттераций - 8 227 278(это только для числа 1_313_546_885_799_053_312 только а там еще в 10 больше) уже и когда буду использовать медленный int оно выполняться вечность без низкоуровнего ускорения