suma kwadratów - sprawa do rozwiązania

[Simpler]

przykładowo mamy liczbę: a = 65587840000,

którą należy rozłożyć na sumę dwóch kwadratów"

p^2 + q^2 = 65587840000


co daje:

7200^2 + 256000^2 = 65587840000
64768^2 + 247776^2 = 65587840000
78592^2 + 243744^2 = 65587840000
147840^2 + 209120^2 = 65587840000
159360^2 + 200480^2 = 65587840000

ma ktoś szybki algorytm na wyliczanie takich numerów?

[bartekltg]

Wiąże sie on niestety z faktoryzacją liczby, więć będzie miał taką samą
złożoność jak algoryt naiwny (przeszukanie wszytkich a<=sqrt(n) ).
O(sqrt(n))

W skrocie, faktoryzujesz liczbę n.
Patrzymy na czynniki.
2 = (1^2+1^2)

Czynniki pierwsze postaci p=4k+3 nie mają rozkładu na sumę kwadratów!
To samo, jeśli p występuje w nieparzystej potędze.
https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem
https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

Parzyste, p^2k, można rozłożyć na trywialną "sumę" 0^2 + (p^k)^2, też się przyda.

Czynniki pierwsze postaci mają jeden rozkład
https://en.wikipedia.org/wiki/Sum_of_squares_function#k_=_2

Włąściwie, w pierwsym z tych przypadków należałoby mówić o 4 przypadkach
(bo mozemy zamienic kolejność i znaki niezerwoego elementu) a wdrugiej
o 8 (kolejnosć x znaki kazdej z liczb).

p^k ma już tak liczonych 4*(k+1) dzielników (dla p == 1 mod 4)

Teraz gwóźdz programu, wzorek skroconego mnozenioa
https://en.wikipedia.org/wiki/Brahmagupta%E2%80%93Fibonacci_identity

w ten sposob, skoro znamy rozkład na sumę kwadratów czynników liczby n,
mozemy wygenerować rozkłady całej liczby.
Jeśli śledzimy wszystkie pary, włącznie z kombinacjami znaków, potrzebujemy
tylko jednej wersji wzorku.

Podsumowując, znajdujesz czynniki pierwsze i odpowiadajace mu wykłądniki,
każdemu generujesz zestaw rozkłądów na sumę kwadratów, a następnie
bierzesz wszystkie kombinacje.

Potem porządkujesz, aby odrzucić kombinacje z ujemnymi i powtorzenia przez zamianę koljeności.

Pewnie da się pozbyć roznych znaków w trzymanych parach przez zastosowanie
obu wzorków, ale musisz sprawdzic, czy nic sie wtedy nie pominie.

Wersja ze znakami się zgadza bo odtwarza wzor na liczbę rozkładów.

Pozostało jeszcze wygenerować rozkłąd dla p = 1 mod 3.
ale ten też jest opisany tu https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares

Jeśli szukasz rozkłądu konkretnej lczby, pewnie nie ma sensu uzywać tej metodt, ale
jeśli potrzebujesz rozkładu wszytkich liczb od 1 do n i masz pamiec na zobienie tabelki
dzielników, to będzie to znacznie szybciej (choc nadal pesymeistycznie, dla liczb
pierwszych, alg działa w czasie sqrt(n)).

Hmm, w sumie jak lecisz od 1 do n, to od razu można generować rozkłady na bazie
poprzednich wpisów. Takie trochę sito erastotenesa wychodzi.

A nie ma znanego znacznie lepszego algorytmu, inaczej faktoryzacja przynajmniej cześći
liczb byłaby łatwiejsza.
https://en.wikipedia.org/wiki/Euler%27s_factorization_method

bartekltg

[Simpler]

Bardzo fajnie opowiadasz... ale z tym sqrt(n) to... ballada sf!

Biorę np. 137, co jest typu 4n+1, zatem daje się rozłożyć na kwadraty -
jak to zrobić?

Proste: sqrt(137) = 11 po zaokrągleniu;
a dalej robimy taki numer:
137 - 11^2 = 137 - 121 = 16, no i tyle z tym roboty:
137 = 11^2 + 4^2

i to ma mieć złożoność sqrt(n) ? złożoność = 1!


A nawet jeśli to nie wypali, bo może się tak zdarzyć niekiedy (raczej sporadycznie),
wtedy pojadę z tym binarnie, co da złożoność log(n^0.5) w porywach, a nie n^0.5 !

log 1000000000 = 30 <<<<< sqrt = 30000, czujesz tę różnicę?

[Simpler]

kontrprzykład;
sqrt521 = 22,

521 - 22^2 = 37 , nie jest kwadratem!

521 - 20^2 = 11^2

zatem tu mamy 20 zamiast 22 -> jeden kroczek!

[bartekltg]

Hmm, to koncepcji takich jak złożoność pesymistyczna i średnia też nie ogarniasz? ;-)

I taka metoda zadziała z każdym?

rozłóż tak

2353937017
Zaczynając od a = ceil[sqrt[n]] i sprawdzając kolejne coraz mniejsze a, dojedziesz
dość daleko. ~30% sqrt[n]

Rozłoż też
2576450045

Tu rozwiązań jest 64 :)

> A nawet jeśli to nie wypali, bo może się tak zdarzyć niekiedy (raczej sporadycznie),
> wtedy pojadę z tym binarnie, co da złożoność log(n^0.5) w porywach, a nie n^0.5 !
>
> log 1000000000 = 30 <<<<< sqrt = 30000, czujesz tę różnicę?

Co pojedziesz binarnie?

Zastanów się 5 minut zanim napiszesz posta :)

bartekltg

[Simpler]

czwartek, 19 sierpnia 2021 o 00:28:31 UTC+2 bartekltg napisał(a):

> Hmm, to koncepcji takich jak złożoność pesymistyczna i średnia też nie ogarniasz? ;-)
>
> I taka metoda zadziała z każdym?
>
> rozłóż tak
>
> 2353937017
> Zaczynając od a = ceil[sqrt[n]] i sprawdzając kolejne coraz mniejsze a, dojedziesz
> dość daleko. ~30% sqrt[n]
>
> Rozłoż też
> 2576450045
>
> Tu rozwiązań jest 64 :)
> > A nawet jeśli to nie wypali, bo może się tak zdarzyć niekiedy (raczej sporadycznie),
> > wtedy pojadę z tym binarnie, co da złożoność log(n^0.5) w porywach, a nie n^0.5 !
> >
> > log 1000000000 = 30 <<<<< sqrt = 30000, czujesz tę różnicę?
> Co pojedziesz binarnie?

mówiłem pierwszych: 4p + 1, i tam jest algorytm o złożoności log(n).

Przy złożonych trzeba to najpierw rozłożyć... a potem przemnożyć te kwadraty. :)

[Simpler]

W sumie to jest bezużyteczne dla mnie, bo dla dużych liczb sqrt(n) to masakra.

Należałoby stworzyć nowy algorytm rozkładu na czynniki,
który pójdzie przynajmniej log(n).

A może robić to odwrotnie?
szukamy: a^2 + b^2 = n, co być może pójdzie łatwiej

i teraz mając a i b rozkładamy to n na czynniki,
bo z pewnością istnieje coś w stylu:

n = kl = jakaś funkcja(a, b),
i mamy drugie równanie:
n = a^2 + b^2

i jeszcze trzecie - z zespolonych:
zatem mamy 3 równania i 4 zmienne, co daje wynik w funkcji jednej zmiennej.