Perl - 116 bajtów 87 bajtów (patrz aktualizacja poniżej)
#!perl -p
$.<<=1,$_>>=2until$_&3;
{$n=$_;@a=map{$n-=$a*($a-=$_%($b=1|($a=0|sqrt$n)>>1));$_/=$b;$a*$.}($j++)x4;$n&&redo}
$_="@a"
Licząc shebang jako jeden bajt, dodano nowe znaki dla poziomego zdrowia psychicznego.
Coś z kombinacji kodu-kodu najszybszego kodu .
Średnia (najgorsza?) Złożoność przypadku wydaje się być O (log n) O (n 0,07 ) . Nic, co znalazłem, działa wolniej niż 0,001s i sprawdziłem cały zakres od 900000000 do 999999999 . Jeśli znajdziesz coś, co trwa znacznie dłużej, około 0,1 s lub więcej, daj mi znać.
Przykładowe użycie
$ echo 123456789 | timeit perl four-squares.pl
11110 157 6 2
Elapsed Time: 0:00:00.000
$ echo 1879048192 | timeit perl four-squares.pl
32768 16384 16384 16384
Elapsed Time: 0:00:00.000
$ echo 999950883 | timeit perl four-squares.pl
31621 251 15 4
Elapsed Time: 0:00:00.000
Ostatnie dwa z nich wydają się najgorszym scenariuszem dla innych wniosków. W obu przypadkach pokazane rozwiązanie jest dosłownie pierwszą sprawdzoną rzeczą. Bo 123456789to drugi.
Jeśli chcesz przetestować zakres wartości, możesz użyć następującego skryptu:
use Time::HiRes qw(time);
$t0 = time();
# enter a range, or comma separated list here
for (1..1000000) {
$t1 = time();
$initial = $_;
$j = 0; $i = 1;
$i<<=1,$_>>=2until$_&3;
{$n=$_;@a=map{$n-=$a*($a-=$_%($b=1|($a=0|sqrt$n)>>1));$_/=$b;$a*$i}($j++)x4;$n&&redo}
printf("%d: @a, %f\n", $initial, time()-$t1)
}
printf('total time: %f', time()-$t0);
Najlepiej gdy jest przesyłany do pliku. Zakres 1..1000000zajmuje około 14 sekund na moim komputerze (71000 wartości na sekundę), a zakres 999000000..1000000000zajmuje około 20 sekund (50000 wartości na sekundę), zgodnie ze średnią złożonością O (log n) .
Aktualizacja
Edycja : Okazuje się, że ten algorytm jest bardzo podobny do tego, który jest używany przez kalkulatory umysłowe od co najmniej stulecia .
Od czasu pierwotnego opublikowania sprawdziłem każdą wartość z zakresu od 1..1000000000 . Zachowanie „najgorszego przypadku” wykazało wartość 699731569 , która przetestowała w sumie 190 kombinacji przed znalezieniem rozwiązania. Jeśli uważasz 190 za małą stałą - a ja na pewno tak - najgorsze zachowanie w wymaganym zakresie można uznać za O (1) . Oznacza to, że tak szybko, jak wyszukiwanie rozwiązania z gigantycznego stołu, i średnio całkiem możliwe, że szybciej.
Ale inna sprawa. Po 190 iteracjach cokolwiek większego niż 144400 nawet nie przekroczyło pierwszego przejścia. Logika pierwszego przejścia jest bezwartościowa - nawet nie jest używana. Powyższy kod można nieco skrócić:
#!perl -p
$.*=2,$_/=4until$_&3;
@a=map{$=-=$%*($%=$=**.5-$_);$%*$.}$j++,(0)x3while$=&&=$_;
$_="@a"
Który wykonuje tylko pierwszy przebieg wyszukiwania. Musimy jednak potwierdzić, że nie ma żadnych wartości poniżej 144400, które wymagałyby drugiego przejścia:
for (1..144400) {
$initial = $_;
# reset defaults
$.=1;$j=undef;$==60;
$.*=2,$_/=4until$_&3;
@a=map{$=-=$%*($%=$=**.5-$_);$%*$.}$j++,(0)x3while$=&&=$_;
# make sure the answer is correct
$t=0; $t+=$_*$_ for @a;
$t == $initial or die("answer for $initial invalid: @a");
}
Krótko mówiąc, dla zakresu 1..1000000000 istnieje rozwiązanie o prawie stałym czasie i na to patrzysz.
Zaktualizowana aktualizacja
@Dennis i ja wprowadziliśmy kilka ulepszeń tego algorytmu. Możesz śledzić postępy w komentarzach poniżej i późniejszą dyskusję, jeśli Cię to interesuje. Średnia liczba iteracji dla wymaganego zakresu spadła z nieco ponad 4 do 1,229 , a czas potrzebny do przetestowania wszystkich wartości dla 1..1000000000 został skrócony z 18m 54s do 2m 41s. Najgorszy przypadek wymagał wcześniej 190 iteracji; najgorszy teraz, 854382778 , potrzebuje tylko 21 .
Ostateczny kod Pythona jest następujący:
from math import sqrt
# the following two tables can, and should be pre-computed
qqr_144 = set([ 0, 1, 2, 4, 5, 8, 9, 10, 13,
16, 17, 18, 20, 25, 26, 29, 32, 34,
36, 37, 40, 41, 45, 49, 50, 52, 53,
56, 58, 61, 64, 65, 68, 72, 73, 74,
77, 80, 81, 82, 85, 88, 89, 90, 97,
98, 100, 101, 104, 106, 109, 112, 113, 116,
117, 121, 122, 125, 128, 130, 133, 136, 137])
# 10kb, should fit entirely in L1 cache
Db = []
for r in range(72):
S = bytearray(144)
for n in range(144):
c = r
while True:
v = n - c * c
if v%144 in qqr_144: break
if r - c >= 12: c = r; break
c -= 1
S[n] = r - c
Db.append(S)
qr_720 = set([ 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121,
144, 145, 160, 169, 180, 196, 225, 241, 244, 256, 265, 289,
304, 324, 340, 361, 369, 385, 400, 409, 436, 441, 481, 484,
496, 505, 529, 544, 576, 580, 585, 601, 625, 640, 649, 676])
# 253kb, just barely fits in L2 of most modern processors
Dc = []
for r in range(360):
S = bytearray(720)
for n in range(720):
c = r
while True:
v = n - c * c
if v%720 in qr_720: break
if r - c >= 48: c = r; break
c -= 1
S[n] = r - c
Dc.append(S)
def four_squares(n):
k = 1
while not n&3:
n >>= 2; k <<= 1
odd = n&1
n <<= odd
a = int(sqrt(n))
n -= a * a
while True:
b = int(sqrt(n))
b -= Db[b%72][n%144]
v = n - b * b
c = int(sqrt(v))
c -= Dc[c%360][v%720]
if c >= 0:
v -= c * c
d = int(sqrt(v))
if v == d * d: break
n += (a<<1) - 1
a -= 1
if odd:
if (a^b)&1:
if (a^c)&1:
b, c, d = d, b, c
else:
b, c = c, b
a, b, c, d = (a+b)>>1, (a-b)>>1, (c+d)>>1, (c-d)>>1
a *= k; b *= k; c *= k; d *= k
return a, b, c, d
Wykorzystuje dwie wstępnie obliczone tabele korekcji, jedna o wielkości 10 kb, druga 253 kb. Powyższy kod zawiera funkcje generatora dla tych tabel, chociaż prawdopodobnie powinny one zostać obliczone w czasie kompilacji.
Wersję ze skromniejszymi tabelami korekcji można znaleźć tutaj: http://codepad.org/1ebJC2OV Ta wersja wymaga średnio 1.620 iteracji na semestr, w najgorszym przypadku 38 , a cały zakres trwa około 3m 21s. Trochę czasu składa się na, za pomocą bitowego anddla b korekty, zamiast modulo.
Ulepszenia
Nawet wartości parzyste częściej dają rozwiązanie niż nieparzyste.
Artykuł dotyczący obliczeń mentalnych powiązany z wcześniejszymi uwagami stwierdza, że jeśli po usunięciu wszystkich czterech czynników wartość do rozkładu jest parzysta, wartość tę można podzielić na dwa, a rozwiązanie odtworzyć:
Chociaż może to mieć sens w obliczeniach umysłowych (mniejsze wartości wydają się być łatwiejsze do obliczenia), nie ma to większego sensu algorytmicznego. Jeśli weźmiesz 256 losowych 4- kropek i zbadasz sumę kwadratów modulo 8 , przekonasz się, że wartości 1 , 3 , 5 i 7 są osiągane średnio 32 razy. Jednak wartości 2 i 6 są osiągane 48 razy. Pomnożenie nieparzystych wartości przez 2 znajdzie rozwiązanie średnio w 33% mniej iteracji. Rekonstrukcja jest następująca:
Należy zwrócić szczególną uwagę na to, i b mają taką samą parzystości oraz C i D , ale jeśli roztwór został znaleziony w wszystkim właściwej kolejności gwarantuje istnieć.
Niemożliwe ścieżki nie muszą być sprawdzane.
Po wybraniu drugiej wartości, b , rozwiązanie może już być niemożliwe, biorąc pod uwagę możliwe reszty kwadratowe dla dowolnego danego modułu. Zamiast sprawdzania i tak dalej lub przechodzenia do następnej iteracji, wartość b można „skorygować”, zmniejszając ją o najmniejszą wartość, która może doprowadzić do rozwiązania. Dwie tabele korekcji przechowują te wartości, jedną dla b , a drugą dla c . Użycie wyższego modułu (dokładniej, użycie modułu z relatywnie mniejszą liczbą reszt kwadratowych) spowoduje lepszą poprawę. Wartość a nie wymaga korekty; przez zmianę n na parzystą, wszystkie wartościa są ważne.
