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

Question

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

В данном коде на python у меня проходят все 8 тестов и 1 не проходит.

from typing import Tuple

def four_squares(n: int) -> Tuple[int, int, int, int]:
    for a in range(int(n**0.5) + 1):
        for b in range(int((n - a**2)**0.5) + 1):
            for c in range(int((n - a**2 - b**2)**0.5) + 1):
                d = int((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 0, 0, 0, 0



# Press the green button in the gutter to run the script.
if __name__ == '__main__':

    for i in [0, 1, 17, 33, 215, 333, 2**12-3, 1234567890, 106369249365575352836589875696130383747]:
        a, b, c, d = four_squares(i)
        error_msg = None
        if type(a) is not int: error_msg = "1st square is not of type int"
        if type(b) is not int: error_msg = "2nd square is not of type int"
        if type(c) is not int: error_msg = "3rd square is not of type int"
        if type(d) is not int: error_msg = "4th square is not of type int"
        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("Решение принято")

Comments

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

GNUBack, Нужно доработать код чтобы в данном алгоритме обработалось такое число 106369249365575352836589875696130383747

[Elvis]

Андрей Прохоренко, если нужно доработать - дорабатывать, или просите на фрилансе

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

https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D...
данный код писался по этому алгоритму

Answer 1

[GavriKos]

Потому что там огромное количество операций. Надо менять алгоритм

Comments

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

https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D... данный код писался по этой теореме

[GavriKos]

Андрей Прохоренко, И что? Ну вон там сложность N2logn - это очень много. У вас просто не успевает это посчитать комп.

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

GavriKos, Нужно не методом перебора а по методу теоремы Лагранжа математическим методом. Перебор не хватит не каких мощностей. Возможно только квантовый компьютер но думаю и это не поможет. Только по теореме Лагранжа.
я даже использовал еще и декоратор @lru_cache(maxsize=256) чтобы кэшировать и библиотека Numba оказывается только поддерживает не более 1 000 000 000 итераций в python

Answer 2

[mayton2019]

Андрей Прохоренко, попробуй использовать библиотеку Numpy.

Но самые сильные оптимизации мы можем сделать только поняв суть алгоритма.
Поэтому для общей пользы было бы полезно нам всем узнать настоящую цель.

Comments

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

https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D... данный код писался по этой теореме

[mayton2019]

Андрей Прохоренко,

давай упростим задачу. Я введу простую функцию с одним циклом которая проще твоей.
и при вот этом значении аргумента x = 106369249365575352836589875696130383747
она будет работать недопустимо долго.

Смотри квадратный корень из x будет

>>> int(106369249365575352836589875696130383747**0.5)
10313546885799053312

Я специально поставлю разделители классов.

10_313_546_885_799_053_312

Я даже не могу придумать название этому числу. Что там... 885 миллиард 546 триллионов и далее идут
кажется квинтиллионы септиллионы...

Это число - больше чем 64 бит. Я не смог его записать в int64 переменную. И скорее всего
самый первый цикл по нему не закончится никогда. Он просто не успеет делать инкремент
за разумное время.

def four_squares(n: int) -> Tuple[int, int, int, int]:
    for a in range(int(n**0.5) + 1):
        // body

Вот такая простая функция вышла транс-вычислительной. Я боюсь что всех датацентров
планеты земля тебе уже не хватит чтобы закончить первый внешний цикл который
ничего не делает а только считает инкремент.

Вот такие дла.

[Lapita12]

from decimal import Decimal, getcontext
from typing import Tuple

getcontext().prec = 100

def lagrange(n: int) -> Tuple[int, int, int, int]:
    for i in range(int(Decimal(n).sqrt()) + 1):
        if i * i > n:
            break
        for j in range(int((Decimal(n) - Decimal(i * i)).sqrt()) + 1):
            if i * i + j * j > n:
                break
            for k in range(int((Decimal(n) - Decimal(i * i) - Decimal(j * j)).sqrt()) + 1):
                if i * i + j * j + k * k > n:
                    break
                l = int((Decimal(n) - Decimal(i * i) - Decimal(j * j) - Decimal(k * k)).sqrt())
                if i * i + j * j + k * k + l * l == n:
                    return (i, j, k, l)
    return (0, 0, 0, 0)

if __name__ == '__main__':
    result = lagrange(106369249365575352836589875696130383747)
    print(result)

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

Нужно не методом перебора а по методу теоремы Лагранжа математическим методом. Перебор не хватит не каких мощностей. Возможно только квантовый компьютер но думаю и это не поможет. Только по теореме Лагранжа.
я даже использовал еще и декоратор @lru_cache(maxsize=256) чтобы кэшировать и библиотека Numba и все таки проблема как раз в Это число - больше чем 64 бит.

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

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, 1_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()

данный код выполнился быстро но как только добавляю последний 0 уже проблема и проблема не в быстродействии как раз даже а как раз - Это число - больше чем 64 бит.

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

Answer 3

[bituke]

пожалуйста, меньше if'оф

from typing import Tuple

def four_squares(n: int) -> Tuple[int, int, int, int]:
    for a in range(int(n**0.5) + 1):
        a_sqr = a ** 2
        for b in range(int((n - a_sqr)**0.5) + 1):
            b_sqr = b ** 2
            for c in range(int((n - a_sqr - b_sqr)**0.5) + 1):
                c_sqr = c ** 2
                d_sqr = n - a_sqr - b_sqr - c_sqr
                d = int(d_sqr ** 0.5)
                if a_sqr + b_sqr + c_sqr + d_sqr == n:
                    return a, b, c, d
    return 0, 0, 0, 0


if __name__ == '__main__':
    test_cases = [0, 1, 17, 33, 215, 333, 2**12-3, 1234567890, 106369249365575352836589875696130383747]
    for i in test_cases:
        a, b, c, d = four_squares(i)
        squares = [a, b, c, d]
        if not all(isinstance(s, int) for s in squares):
            print(f"Error: squares are not of type int for n = {i}")
        elif sum(s**2 for s in squares) != i:
            print(f"Error: incorrect sum for n = {i}. Squares: {squares}")
        else:
            print(f"Solution accepted for n = {i}")