Teorema empat persegi Lagrange memberi tahu kita bilangan alami dapat direpresentasikan sebagai jumlah dari empat bilangan kuadrat. Tugas Anda adalah menulis program yang melakukan ini.

Input: Jumlah alami (di bawah 1 miliar)

Output: Empat angka yang kuadratnya berjumlah ke angka itu (urutan tidak masalah)

Catatan: Anda tidak perlu melakukan pencarian brute force! Detail di sini dan di sini . Jika ada fungsi yang meremehkan masalah ini (saya akan tentukan), itu tidak diizinkan. Fungsi utama otomatis dan root kuadrat diperbolehkan. Jika ada lebih dari satu representasi, semua orang akan baik-baik saja. Jika Anda memilih untuk melakukan kekerasan, itu harus berjalan dalam waktu yang wajar (3 menit)

input sampel

123456789

keluaran sampel (baik-baik saja)

10601 3328 2 0
10601 3328 2

CJam, 50 byte

li:NmF0=~2/#:J(_{;)__*N\-[{_mqJ/iJ*__*@\-}3*])}g+p

Jawaban ketiga (dan terakhir, saya berjanji). Pendekatan ini sangat didasarkan pada jawaban primo .

Cobalah online di juru bahasa CJam .

Pemakaian

$ cjam 4squares.cjam <<< 999999999
[189 31617 567 90]

Latar Belakang

1. Setelah melihat algoritma primo yang diperbarui, saya harus melihat bagaimana skor implementasi CJam:

   li{W):W;:N4md!}g;Nmqi)_{;(__*N\-[{_mqi__*@\-}3*])}g+2W#f*p
   

   Hanya 58 byte! Algoritma ini bekerja dalam waktu yang hampir konstan dan tidak menunjukkan banyak variasi untuk nilai yang berbeda N. Mari kita ubah itu ...

2. Alih-alih memulai floor(sqrt(N))dan mengurangi, kita bisa mulai 1dan menambah. Ini menghemat 4 byte.

   li{W):W;:N4md!}g;0_{;)__*N\-[{_mqi__*@\-}3*])}g+2W#f*p
   

3. Alih-alih menyatakan Nsebagai 4**a * b, kita dapat menyatakannya sebagai p**(2a) * b- di mana pfaktor prima terkecil N- untuk menyimpan 1 byte lebih.

   li_mF0=~2/#:J_*/:N!_{;)__*N\-[{_mqi__*@\-}3*])}g+Jf*p
   

4. Modifikasi sebelumnya memungkinkan kita untuk sedikit mengubah implementasi (tanpa menyentuh algoritme itu sendiri): Alih-alih membaginya Ndengan p**(2a)dan melipatgandakan solusinya p**a, kita dapat langsung membatasi solusi yang mungkin menjadi kelipatan p**a. Ini menghemat 2 byte lagi.

   li:NmF0=~2/#:J!_{;J+__*N\-[{_mqJ/iJ*__*@\-}3*])}g+`
   

5. Tidak membatasi integer pertama untuk p**amenyimpan banyak byte tambahan.

   li:NmF0=~2/#:J(_{;)__*N\-[{_mqJ/iJ*__*@\-}3*])}g+`
   

Algoritma terakhir

1. Temukan adan bsedemikian rupa N = p**(2a) * b, di mana bbukan kelipatan p**2dan pmerupakan faktor prima terkecil N.

2. Setel j = p**a.

3. Setel k = floor(sqrt(N - j**2) / A) * A.

4. Setel l = floor(sqrt(N - j**2 - k**2) / A) * A.

5. Setel m = floor(sqrt(N - j**2 - k**2 - l**2) / A) * A.

6. Jika N - j**2 - k**2 - l**2 - m**2 > 0, atur j = j + 1dan kembali ke langkah 3.

Ini dapat diimplementasikan sebagai berikut:

li:N          " Read an integer from STDIN and save it in “N”.                        ";
mF            " Push the factorization of “N”. Result: [ [ p1 a1 ] ... [ pn an ] ]    ";
0=~           " Push “p1” and “a1”. “p1” is the smallest prime divisor of “N”.        ";
2/#:J         " Compute p1**(a1/2) and save the result “J”.                           ";
(_            " Undo the first two instructions of the loop.                          ";
{             "                                                                       ";
  ;)_         " Pop and discard. Increment “J” and duplicate.                         ";
  _*N\-       " Compute N - J**2.                                                     ";
  [{          "                                                                       ";
    _mqJ/iJ*  " Compute K = floor(sqrt(N - J**2)/J)*J.                                ";
    __*@      " Duplicate, square and rotate. Result: K   K**2   N - J**2             ";
    \-        " Swap and subtract. Result: K   N - J**2 - K**2                        ";
  }3*]        " Do the above three times and collect in an array.                     ";
  )           " Pop the array. Result: N - J**2 - K**2 - L**2 - M**2                  ";
}g            " If the result is zero, break the loop.                                ";
+p            " Unshift “J” in [ K L M ] and print a string representation.           ";

Tolak ukur

Saya telah menjalankan semua 5 versi di atas semua bilangan bulat positif hingga 999.999.999 pada Intel Core i7-3770 saya, mengukur waktu eksekusi dan menghitung iterasi yang diperlukan untuk menemukan solusi.

Tabel berikut ini menunjukkan jumlah rata-rata iterasi dan waktu eksekusi untuk satu integer:

Version               |    1    |    2    |    3    |    4    |    5
----------------------+---------+---------+---------+---------+---------
Number of iterations  |  4.005  |  28.31  |  27.25  |  27.25  |  41.80
Execution time [µs]   |  6.586  |  39.69  |  55.10  |  63.99  |  88.81

1. Dengan hanya 4 iterasi dan 6,6 mikro per integer, algoritma primo sangat cepat.

2. Mulai dengan floor(sqrt(N))lebih masuk akal, karena ini memberi kita nilai yang lebih kecil untuk jumlah dari tiga kuadrat yang tersisa. Seperti yang diharapkan, mulai dari 1 jauh lebih lambat.

3. Ini adalah contoh klasik dari ide bagus yang diterapkan dengan buruk. Untuk benar-benar mengurangi ukuran kode, kami bergantung pada mF, yang memengaruhi integer N. Meskipun versi 3 membutuhkan iterasi yang lebih sedikit daripada versi 2, ini jauh lebih lambat dalam praktiknya.

4. Meskipun algoritme tidak berubah, versi 4 jauh lebih lambat. Ini karena ia melakukan pembagian titik apung tambahan dan perkalian bilangan bulat di setiap iterasi.

5. Untuk input N = p**(2a) ** b, algoritma 5 akan membutuhkan (k - 1) * p**a + 1iterasi, di mana kjumlah algoritma iterasi 4 membutuhkan. Jika k = 1atau a = 0, ini tidak ada bedanya.

   Namun, setiap input formulir 4**a * (4**c * (8 * d + 7) + 1)mungkin berkinerja sangat buruk. Untuk nilai mulai j = p**a, N - 4**a = 4**(a + c) * (8 * d + 7), sehingga tidak dapat dinyatakan sebagai jumlah dari tiga kotak. Jadi, k > 1dan setidaknya p**adiperlukan iterasi.

   Untungnya, algoritma asli primo sangat cepat dan N < 1,000,000,000. Kasus terburuk yang bisa saya temukan dengan tangan adalah 265,289,728 = 4**10 * (4**1 * (7 * 8 + 7) + 1), yang membutuhkan 6.145 iterasi. Waktu eksekusi kurang dari 300 ms pada mesin saya. Rata-rata, versi ini 13,5 kali lebih lambat daripada penerapan algoritma primo.

FRACTRAN: 156 98 fraksi

Karena ini adalah masalah teori bilangan klasik, cara apa yang lebih baik untuk menyelesaikan ini daripada menggunakan angka!

37789/221 905293/11063 1961/533 2279/481 57293/16211 2279/611 53/559 1961/403 53/299 13/53 1/13 6557/262727 6059/284321 67/4307 67/4661 6059/3599 59/83 1/59 14279/871933 131/9701 102037079/8633 14017/673819 7729/10057 128886839/8989 13493/757301 7729/11303 89/131 1/89 31133/2603 542249/19043 2483/22879 561731/20413 2483/23701 581213/20687 2483/24523 587707/21509 2483/24797 137/191 1/137 6215941/579 6730777/965 7232447/1351 7947497/2123 193/227 31373/193 23533/37327 5401639/458 229/233 21449/229 55973/24823 55973/25787 6705901/52961 7145447/55973 251/269 24119/251 72217/27913 283/73903 281/283 293/281 293/28997 293/271 9320827/58307 9831643/75301 293/313 28213/293 103459/32651 347/104807 347/88631 337/347 349/337 349/33919 349/317 12566447/68753 13307053/107143 349/367 33197/349 135199/38419 389/137497 389/119113 389/100729 383/389 397/383 397/39911 397/373 1203/140141 2005/142523 2807/123467 4411/104411 802/94883 397/401 193/397 1227/47477 2045/47959 2863/50851 4499/53743 241/409 1/241 1/239

Mengambil input dari form 2 ⁿ × 193 dan output 3 ^a × 5 ^b × 7 ^c × 11 ^d . Dapat berjalan dalam 3 menit jika Anda memiliki juru bahasa yang sangat bagus. Mungkin.

... oke, tidak juga. Sepertinya ini masalah yang menyenangkan untuk dilakukan di FRACTRAN sehingga saya harus mencobanya. Jelas, ini bukan solusi yang tepat untuk pertanyaan karena tidak membuat persyaratan waktu (itu kasar) dan itu hampir tidak golf, tapi saya pikir saya akan memposting ini di sini karena tidak setiap hari pertanyaan Codegolf dapat dilakukan di FRACTRAN;)

Petunjuk

Kode ini setara dengan pseudo-Python berikut:

a, b, c, d = 0, 0, 0, 0

def square(n):
    # Returns n**2

def compare(a, b):
    # Returns (0, 0) if a==b, (1, 0) if a<b, (0, 1) if a>b

def foursquare(a, b, c, d):
    # Returns square(a) + square(b) + square(c) + square(d)

while compare(foursquare(a, b, c, d), n) != (0, 0):
    d += 1

    if compare(c, d) == (1, 0):
        c += 1
        d = 0

    if compare(b, c) == (1, 0):
        b += 1
        c = 0
        d = 0

    if compare(a, b) == (1, 0):
        a += 1
        b = 0
        c = 0
        d = 0

Mathematica 61 66 51

Tiga metode ditampilkan. Hanya pendekatan pertama yang memenuhi persyaratan waktu.

1-FindInstance (51 char)

Ini mengembalikan solusi tunggal persamaan.

FindInstance[a^2 + b^2 + c^2 + d^2 == #, {a, b, c, d}, Integers] &

Contoh dan timing

FindInstance[a^2 + b^2 + c^2 + d^2 == 123456789, {a, b, c, d}, Integers] // AbsoluteTiming

{0,003584, {{a -> 2600, b -> 378, c -> 10468, d -> 2641}}}

FindInstance[a^2 + b^2 + c^2 + d^2 == #, {a, b, c, d}, Integers] &[805306368]

{0,004437, {{a -> 16384, b -> 16384, c -> 16384, d -> 0}}}

2-IntegerPartitions

Ini juga berfungsi, tetapi terlalu lambat untuk memenuhi persyaratan kecepatan.

f@n_ := Sqrt@IntegerPartitions[n, {4}, Range[0, Floor@Sqrt@n]^2, 1][[1]]

Range[0, Floor@Sqrt@n]^2adalah himpunan semua kuadrat kurang dari akar kuadrat (kuadrat nterbesar yang mungkin ada dalam partisi).

{4}membutuhkan partisi integer nterdiri dari 4 elemen dari set kuadrat yang disebutkan di atas.

1, dalam fungsi IntegerPartitionsmengembalikan solusi pertama.

[[1]]menghilangkan kawat gigi luar; solusi dikembalikan sebagai satu set elemen.

f[123456]

{348, 44, 20, 4}

3-PowerRepresentations

PowerRepresentations mengembalikan semua solusi ke masalah 4 kotak. Itu juga dapat memecahkan sejumlah kekuatan lain.

Representasi Powers kembali, dalam waktu kurang dari 5 detik, 181 cara untuk mengekspresikan 123456789 sebagai jumlah dari 4 kotak:

n= 123456;
PowersRepresentations[n, 4, 2] //AbsoluteTiming

Namun, ini terlalu lambat untuk jumlah lainnya.

Perl - 116 byte 87 byte (lihat pembaruan di bawah)

#!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"

Menghitung shebang sebagai satu byte, baris baru ditambahkan untuk kewarasan horisontal.

Sesuatu dari pengiriman kode-golf tercepat-kode kombinasi .

Kompleksitas kasus rata-rata (terburuk?) Tampaknya O (log n) O (n ^0,07 ) . Tidak ada yang saya temukan berjalan lebih lambat dari 0,001, dan saya telah memeriksa seluruh rentang dari 900000000 - 999999999 . Jika Anda menemukan sesuatu yang secara signifikan lebih lama dari itu, ~ 0,1s atau lebih, beri tahu saya.

Contoh Penggunaan

$ 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

Dua terakhir ini tampaknya merupakan kasus terburuk untuk kiriman lainnya. Dalam kedua contoh, solusi yang ditampilkan secara harfiah adalah hal pertama yang diperiksa. Sebab 123456789, ini yang kedua.

Jika Anda ingin menguji berbagai nilai, Anda dapat menggunakan skrip berikut:

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);

Terbaik saat disalurkan ke file. Rentang ini 1..1000000membutuhkan waktu sekitar 14 detik di komputer saya (nilai 71000 per detik), dan rentang 999000000..1000000000waktu sekitar 20 detik (nilai 50000 per detik), konsisten dengan kompleksitas rata-rata O (log n) .

Memperbarui

Sunting : Ternyata algoritma ini sangat mirip dengan yang telah digunakan oleh kalkulator mental selama setidaknya satu abad .

Sejak semula memposting, saya telah memeriksa setiap nilai pada kisaran dari 1..1000000000 . Perilaku 'kasus terburuk' ditunjukkan oleh nilai 699731569 , yang menguji total 190 kombinasi sebelum sampai pada solusi. Jika Anda menganggap 190 sebagai konstanta kecil - dan tentu saja saya lakukan - perilaku terburuk pada rentang yang diperlukan dapat dianggap O (1) . Artinya, secepat mencari solusi dari meja raksasa, dan rata-rata, sangat mungkin lebih cepat.

Satu hal lagi. Setelah 190 iterasi, apapun yang lebih besar dari 144400 bahkan belum berhasil melampaui pass pertama. Logika untuk lintas luas pertama tidak berharga - bahkan tidak digunakan. Kode di atas dapat disingkat sedikit:

#!perl -p
$.*=2,$_/=4until$_&3;
@a=map{$=-=$%*($%=$=**.5-$_);$%*$.}$j++,(0)x3while$=&&=$_;
$_="@a"

Yang hanya melakukan pass pertama pencarian. Kami perlu mengonfirmasi bahwa tidak ada nilai di bawah 144400 yang memerlukan pass kedua, meskipun:

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");
}

Singkatnya, untuk kisaran 1..1000000000 , solusi waktu hampir konstan ada, dan Anda sedang melihatnya.

Pembaruan yang Diperbarui

@Dennis dan saya telah membuat beberapa peningkatan pada algoritma ini. Anda dapat mengikuti kemajuan dalam komentar di bawah, dan diskusi selanjutnya, jika itu menarik minat Anda. Jumlah rata-rata iterasi untuk rentang yang diperlukan telah turun dari lebih dari 4 ke 1.229 , dan waktu yang dibutuhkan untuk menguji semua nilai untuk 1..1000000000 telah ditingkatkan dari 18m 54s, turun ke 2m 41s. Kasus terburuk yang sebelumnya membutuhkan 190 iterasi; kasus terburuk sekarang, 854382778 , hanya perlu 21 .

Kode Python terakhir adalah sebagai berikut:

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

Ini menggunakan dua tabel koreksi yang sudah dihitung sebelumnya, satu berukuran 10kb, yang lain 253kb. Kode di atas termasuk fungsi generator untuk tabel ini, meskipun ini mungkin harus dihitung pada waktu kompilasi.

Versi dengan tabel koreksi berukuran lebih sederhana dapat ditemukan di sini: http://codepad.org/1ebJC2OV Versi ini membutuhkan rata-rata 1,620 iterasi per istilah, dengan kasus terburuk 38 , dan seluruh rentang berjalan sekitar 3m 21d. Sedikit waktu dibuat, dengan menggunakan bitwise anduntuk koreksi b , daripada modulo.

Perbaikan

Bahkan nilai lebih cenderung menghasilkan solusi daripada nilai ganjil.
Artikel perhitungan mental yang ditautkan dengan catatan sebelumnya bahwa jika, setelah menghilangkan semua faktor empat, nilai yang akan didekomposisi adalah genap, nilai ini dapat dibagi dua, dan solusi direkonstruksi:

Meskipun ini mungkin masuk akal untuk perhitungan mental (nilai yang lebih kecil cenderung lebih mudah untuk dihitung), itu tidak masuk akal secara algoritmik. Jika Anda mengambil 256 acak 4- tupel, dan memeriksa jumlah modulo 8 kotak , Anda akan menemukan bahwa nilai 1 , 3 , 5 , dan 7 masing-masing mencapai rata-rata 32 kali. Namun, nilai 2 dan 6 masing-masing mencapai 48 kali. Mengalikan nilai aneh dengan 2 akan menemukan solusi, rata-rata, dalam iterasi 33% lebih sedikit. Rekonstruksi adalah sebagai berikut:

Harus diperhatikan bahwa a dan b memiliki paritas yang sama, serta c dan d , tetapi jika solusi ditemukan sama sekali, pemesanan yang tepat dijamin ada.

Jalur yang tidak mungkin tidak perlu diperiksa.
Setelah memilih nilai kedua, b , mungkin sudah tidak mungkin untuk solusi ada, mengingat kemungkinan residu kuadratik untuk setiap modulo yang diberikan. Alih-alih memeriksa, atau beralih ke iterasi berikutnya, nilai b dapat 'dikoreksi' dengan menurunkannya dengan jumlah terkecil yang mungkin mengarah pada solusi. Dua tabel koreksi menyimpan nilai-nilai ini, satu untuk b , dan yang lainnya untuk c . Menggunakan modulo yang lebih tinggi (lebih akurat, menggunakan modulo dengan residu kuadratik yang relatif lebih sedikit) akan menghasilkan peningkatan yang lebih baik. Nilai a tidak perlu koreksi apa pun; dengan memodifikasi n menjadi genap, semua nilaia valid.

Python 3 (177)

N=int(input())
k=1
while N%4<1:N//=4;k*=2
n=int(N**.5)
R=range(int(2*n**.5)+1)
print([(a*k,b*k,c*k,d*k)for d in R for c in R for b in R for a in[n,n-1]if a*a+b*b+c*c+d*d==N][0])

Setelah kita mengurangi input Nagar tidak habis dibagi 4, itu harus dapat diekspresikan sebagai jumlah empat kotak di mana salah satunya adalah nilai terbesar yang mungkin a=int(N**0.5)atau kurang dari itu, hanya menyisakan sisa kecil untuk jumlah dari tiga kotak lainnya untuk mengurus. Ini sangat mengurangi ruang pencarian.

Inilah buktinya nanti kode ini selalu menemukan solusinya. Kami ingin menemukan asehingga n-a^2adalah jumlah dari tiga kotak. Dari Teorema Tiga-Persegi Legendre , angka adalah jumlah dari tiga kuadrat kecuali jika itu adalah bentuk 4^j(8*k+7). Khususnya, angka-angka tersebut adalah 0 atau 3 (modulo 4).

Kami menunjukkan bahwa tidak ada dua berturut a- turut dapat membuat jumlah sisa N-a^2memiliki bentuk seperti itu untuk kedua nilai berturut-turut .. Kami dapat melakukannya dengan hanya membuat tabel adan Nmodulo 4, mencatat bahwa N%4!=0karena kami telah mengekstraksi semua kekuatan 4 dari N.

  a%4= 0123
      +----
     1|1010
N%4= 2|2121  <- (N-a*a)%4
     3|3232

Karena tidak ada dua berturut-turut amemberi (N-a*a)%4 in [0,3], salah satunya adalah aman untuk digunakan. Jadi, kami dengan rakus menggunakan kemungkinan terbesar ndengan n^2<=N, dan n-1. Karena N<(n+1)^2, sisanya N-a^2untuk diwakili sebagai jumlah tiga kotak paling banyak (n+1)^2 -(n-1)^2, yang sama dengan 4*n. Jadi, cukup untuk memeriksa hanya nilai hingga 2*sqrt(n), yang merupakan kisaran sebenarnya R.

Seseorang dapat lebih lanjut mengoptimalkan waktu berjalan dengan berhenti setelah satu solusi, menghitung daripada mengulangi nilai terakhir d, dan hanya mencari di antara nilai-nilai b<=c<=d. Tetapi, bahkan tanpa optimasi ini, contoh terburuk yang dapat saya temukan selesai dalam 45 detik pada mesin saya.

Rantai "untuk x dalam R" sangat disayangkan. Ini mungkin dapat dipersingkat dengan penggantian string atau penggantian dengan mengulangi indeks tunggal yang mengkodekan (a, b, c, d). Mengimpor itertools ternyata tidak sepadan.

Sunting: Diubah ke int(2*n**.5)+1dari 2*int(n**.5)+2untuk menjadikan argumen lebih bersih, jumlah karakter yang sama.

CJam , 91 90 74 71 byte

q~{W):W;:N4md!}gmqi257:B_**_{;)_[Bmd\Bmd]_N\{_*-}/mq_i@+\1%}g{2W#*}%`\;

Ringkas, tapi lebih lambat dari pendekatan saya yang lain.

Cobalah online! Tempel Kode , ketik bilangan bulat yang diinginkan di Input dan klik Run .

Latar Belakang

Posting ini dimulai sebagai jawaban GolfScript 99 byte . Sementara masih ada ruang untuk perbaikan, GolfScript tidak memiliki fungsi sqrt bawaan. Saya menyimpan versi GolfScript hingga revisi 5 , karena sangat mirip dengan versi CJam.

Namun, pengoptimalan sejak revisi 6 membutuhkan operator yang tidak tersedia di GolfScript, jadi alih-alih memposting penjelasan terpisah untuk kedua bahasa, saya memutuskan untuk menghentikan versi yang kurang kompetitif (dan jauh lebih lambat).

Algoritma yang diimplementasikan menghitung angka dengan brute force:

1. Untuk input m, cari Ndan Wsemacamnya m = 4**W * N.

2. Setel i = 257**2 * floor(sqrt(N/4)).

3. Setel i = i + 1.

4. Temukan bilangan bulat j, k, lsedemikian rupa sehingga i = 257**2 * j + 257 * k + l, di mana k, l < 257.

5. Periksa apakah d = N - j**2 - k**2 - l**2kuadrat sempurna.

6. Jika tidak, dan kembali ke langkah 3.

7. Cetak 2**W * j, 2**W * k, 2**W * l, 2**W * sqrt(m).

Contohnya

$ TIME='\n%e s' time cjam lagrange.cjam <<< 999999999
[27385 103 15813 14]
0.46 s
$ TIME='\n%e s' time cjam lagrange.cjam <<< 805306368
[16384 16384 0 16384]
0.23 s

Pengaturan waktu sesuai dengan Intel Core i7-4700MQ.

Bagaimana itu bekerja

q~              " Read and interpret the input. ";
{
  W):W;         " Increment “W” (initially -1). ";
  :N            " Save the integer on the stack in “N”. ';
  4md!          " Push N / 4 and !(N % 4). ";
}g              " If N / 4 is an integer, repeat the loop.
mqi             " Compute floor(sqrt(N/4)). ";
257:B_**        " Compute i = floor(sqrt(N)) * 257**2. ";
_               " Duplicate “i” (dummy value). ";
{               " ";
  ;)_           " Pop and discard. Increment “i”. ";
  [Bmd\Bmd]     " Push [ j k l ], where i = 257**2 * j + 257 * k + l and k, l < 257. ";
  _N\           " Push “N” and swap it with a copy of [ j k l ]. ";
  {_*-}/        " Compute m = N - j**2 - k**2 - l**2. ";
  mq            " Compute sqrt(m). ";
  _i            " Duplicate sqrt(m) and compute floor(sqrt(m)). ";
  @+\           " Form [ j k l floor(sqrt(m)) ] and swap it with sqrt(m). ";
  1%            " Check if sqrt(m) is an integer. ";
}g              " If it is, we have a solution; break the loop. ";
{2W#*}%         " Push 2**W * [ j k l sqrt(m) ]. ";
`\;             " Convert the array into a string and discard “i”. ";

C, 228

Ini didasarkan pada algoritma pada halaman Wikipedia, yang merupakan kekuatan brutal O (n).

n,*l,x,y,i;main(){scanf("%d",&n);l=calloc(n+1,8);
for(x=0;2*x*x<=n;x++)for(y=x;(i=x*x+y*y)<=n;y++)l[2*i]=x,l[2*i+1]=y;
for(x=0,y=n;;x++,y--)if(!x|l[2*x+1]&&l[2*y+1]){
printf("%d %d %d %d\n",l[2*x],l[2*x+1],l[2*y],l[2*y+1]);break;}}

GolfScript, 133 130 129 byte

~{.[4*{4/..4%1$!|!}do])\}:r~,(2\?:f;{{..*}:^~4-1??n*,}:v~)..
{;;(.^3$\-r;)8%!}do-1...{;;;)..252/@252%^@^@+4$\-v^@-}do 5$]{f*}%-4>`

Cepat, tapi panjang. Baris baru dapat dihapus.

Cobalah online. Perhatikan bahwa penerjemah online memiliki batas waktu 5 detik, jadi itu mungkin tidak berfungsi untuk semua angka.

Latar Belakang

Algoritma mengambil keuntungan dari teorema tiga-persegi Legendre , yang menyatakan bahwa setiap bilangan alami n yang bukan dari bentuk

dapat dinyatakan sebagai jumlah dari tiga kotak.

Algoritme melakukan hal berikut:

1. Nyatakan nomor sebagai 4**i * j.

2. Temukan bilangan bulat terbesar ksehingga k**2 <= jdan j - k**2memenuhi hipotesis teorema tiga-persegi Legendre.

3. Setel i = 0.

4. Periksa apakah j - k**2 - (i / 252)**2 - (i % 252)**2kuadrat sempurna.

5. Jika tidak, tambahkan idan kembali ke langkah 4.

Contohnya

$ TIME='%e s' time golfscript legendre.gs <<< 0
[0 0 0 0]
0.02 s
$ TIME='%e s' time golfscript legendre.gs <<< 123456789
[32 0 38 11111]
0.02 s
$ TIME='%e s' time golfscript legendre.gs <<< 999999999
[45 1 217 31622]
0.03 s
$ TIME='%e s' time golfscript legendre.gs <<< 805306368
[16384 0 16384 16384]
0.02 s

Pengaturan waktu sesuai dengan Intel Core i7-4700MQ.

Bagaimana itu bekerja

~              # Interpret the input string. Result: “n”
{              #
  .            # Duplicate the topmost stack item.
  [            #
    4*         # Multiply it by four.
    {          #
      4/       # Divide by four.
      ..       # Duplicate twice.
      4%1$     # Compute the modulus and duplicate the number.
      !|!      # Push 1 if both are truthy.
    }do        # Repeat if the number is divisible by four and non-zero.
  ]            # Collect the pushed values (one per iteration) into an array.
  )\           # Pop the last element from the array and swap it with the array.
}:r~           # Save this code block as “r” and execute it.
,(2\?          # Get the length of the array, decrement it and exponentiate.
:f;            # Save the result in “f”.
               # The topmost item on the stack is now “j”, which is not divisible by 
               # four and satisfies that n = f**2 * j.
{              #
  {..*}:^~     # Save a code block to square a number in “^” and execute it.
  4-1??        # Raise the previous number to the power of 1/4.
               # The two previous lines compute (x**2)**(1/4), which is sqrt(abs(x)).
  n*,          # Repeat the string "\n" that many times and compute its length.
               # This casts to integer. (GolfScript doesn't officially support Rationals.)
}:v~           # Save the above code block in “v” and execute it.
)..            # Undo the first three instructions of the loop.
{              #
   ;;(         # Discard two items from the stack and decrement.
   .^3$\-      # Square and subtract from “n”.
   r;)8%!      # Check if the result satisfies the hypothesis of the three-square theorem.
}do            # If it doesn't, repeat the loop.
-1...          # Push 0 (“i”) and undo the first four instructions of the loop.
{              #
  ;;;)         # Discard two items from the stack and increment “i”.
  ..252/@252%  # Push the digits of “i” in base 252.
  ^@^@+4$\-    # Square both, add and subtract the result 
  v^@-         # Take square root, square and compare.
}do            # If the difference is a perfect square, break the loop.
5$]            # Duplicate the difference an collect the entire stack into an array.
{f*}%          # Multiply very element of the array by “f”.
-4>            # Reduce the array to its four last elements (the four numbers).
`              # Convert the result into a string.

Wah 1: C, 190

a,z,m;short s[15<<26];p(){m=s[a=z-a];printf("%d %f ",m,sqrt(a-m*m));}
main(){m=31727;for(a=m*m;--a;s[z<m*m?z:m*m]=a%m)z=a/m*(a/m)+a%m*(a%m);scanf("%d",&z);for(;a*!s[a]||!s[z-a];a++);p();p();}

Ini bahkan lebih haus ingatan daripada rev 0. Prinsip yang sama: buat tabel dengan nilai positif untuk semua jumlah yang mungkin dari 2 kotak (dan nol untuk angka-angka yang bukan jumlah dari dua kotak), kemudian cari.

Dalam rev ini gunakan array shortalih - alih charuntuk menyimpan hit, jadi saya bisa menyimpan root dari salah satu dari pasangan kotak di tabel, bukan hanya sebuah bendera. Ini menyederhanakan fungsi p(untuk decoding jumlah 2 kuadrat) karena tidak perlu untuk loop.

Windows memiliki batas 2GB pada array. Saya bisa mendapatkan yang dengan short s[15<<26]array 1006632960 elemen, cukup untuk memenuhi spesifikasi. Sayangnya, total ukuran program runtime masih lebih 2GB dan (meskipun tweaking pengaturan OS) saya belum dapat menjalankan lebih ukuran ini (meskipun secara teoritis mungkin.) Yang terbaik yang bisa saya lakukan adalah short s[14<<26](939.524.096 elemen.) m*mHarus benar-benar kurang dari ini (30651 ^ 2 = 939483801.) Namun demikian, program ini berjalan dengan sempurna dan harus bekerja pada OS apa pun yang tidak memiliki batasan ini.

Kode tidak dikunci

a,z,m;
short s[15<<26];     
p(){m=s[a=z-a];printf("%d %f ",m,sqrt(a-m*m));}      
main(){       
 m=31727;             
 for(a=m*m;--a;s[z<m*m?z:m*m]=a%m)   //assignment to s[] moved inside for() is executed after the following statement. In this rev excessively large values are thrown away to s[m*m].
   z=a/m*(a/m)+a%m*(a%m);            //split a into high and low half, calculate h^2+l^2.                                  
 scanf("%d",&z); 
 for(;a*!s[a]||!s[z-a];a++);         //loop until s[a] and s[z-a] both contain an entry. s[0] requires special handling as s[0]==0, therefore a* is included to break out of the loop when a=0 and s[z] contains the sum of 2 squares.
 p();                                //print the squares for the first sum of 2 squares 
 p();}                               //print the squares for the 2nd sum of 2 squares (every time p() is called it does a=z-a so the two sums are exchanged.) 

Rev 0 C, 219

a,z,i,m;double t;char s[1<<30];p(){for(i=t=.1;(m=t)-t;i++)t=sqrt(a-i*i);printf("%d %f ",i-1,t);}
main(){m=1<<15;for(a=m*m;--a;){z=a/m*(a/m)+a%m*(a%m);s[z<m*m?z:0]=1;}scanf("%d",&z);for(;1-s[a]*s[z-a];a++);p();a=z-a;p();}

Ini adalah binatang yang haus akan ingatan. Dibutuhkan array 1GB, menghitung semua jumlah yang mungkin dari 2 kotak dan menyimpan bendera untuk masing-masing dalam array. Kemudian untuk input pengguna z, ia mencari array untuk dua jumlah 2 kuadrat a dan za.

fungsi pmaka reconsitutes kotak asli yang digunakan untuk membuat jumlah dari 2 kotak adan z-adan mencetak mereka, yang pertama dari masing-masing pasangan sebagai integer, yang kedua sebagai ganda (jika memiliki untuk menjadi semua bilangan bulat dua karakter yang dibutuhkan, t> m=t.)

Program ini memakan waktu beberapa menit untuk membangun tabel jumlah kuadrat (saya pikir ini adalah karena masalah manajemen memori, saya melihat alokasi memori naik perlahan-lahan daripada melompat seperti yang mungkin diharapkan.) Namun begitu itu dilakukan menghasilkan jawaban dengan sangat cepat (jika beberapa angka harus dihitung, program dari scanfseterusnya dapat dimasukkan dalam satu lingkaran.

kode yang tidak dipisahkan

a,z,i,m;
double t;
char s[1<<30];                              //handle numbers 0 up to 1073741823
p(){
 for(i=t=.1;(m=t)-t;i++)t=sqrt(a-i*i);      //where a contains the sum of 2 squares, search until the roots are found
 printf("%d %f ",i-1,t);}                   //and print them. m=t is used to evaluate the integer part of t. 

main(){       
 m=1<<15;                                   //max root we need is sqrt(1<<30);
 for(a=m*m;--a;)                            //loop m*m-1 down to 1, leave 0 in a
   {z=a/m*(a/m)+a%m*(a%m);s[z<m*m?z:0]=1;}  //split a into high and low half, calculate h^2+l^2. If under m*m, store flag, otherwise throw away flag to s[0]
 scanf("%d",&z);
 for(;1-s[a]*s[z-a];a++);                   //starting at a=0 (see above) loop until flags are found for sum of 2 squares of both (a) and (z-a)
 p();                                       //reconsitute and print the squares composing (a)
 a=z-a;                                     //assign (z-a) to a in order to...
 p();}                                      //reconsitute and print the squares composing (z-a)  

Contoh output

Yang pertama adalah per pertanyaan. Yang kedua dipilih sebagai yang sulit untuk dicari. Dalam hal ini program harus mencari sejauh 8192 ^ 2 + 8192 ^ 2 = 134217728, tetapi hanya membutuhkan beberapa detik setelah tabel dibangun.

123456789
0 2.000000 3328 10601.000000

805306368
8192 8192.000000 8192 24576.000000

Mathematica, 138 karakter

Jadi ternyata ini menghasilkan hasil negatif dan imajiner untuk input tertentu seperti yang ditunjukkan oleh edc65 (misalnya, 805306368), jadi ini bukan solusi yang valid. Saya akan meninggalkannya untuk saat ini, dan mungkin, jika saya benar-benar membenci waktu saya, saya akan kembali dan mencoba memperbaikinya.

S[n_]:=Module[{a,b,c,d},G=Floor@Sqrt@#&;a=G@n;b:=G[n-a^2];c:=G[n-a^2-b^2];d:=G[n-a^2-b^2-c^2];While[Total[{a,b,c,d}^2]!=n,a-=1];{a,b,c,d}]

Atau, tidak berpengalaman:

S[n_] := Module[{a, b, c, d}, G = Floor@Sqrt@# &;
 a = G@n;
 b := G[n - a^2];
 c := G[n - a^2 - b^2];
 d := G[n - a^2 - b^2 - c^2];
 While[Total[{a, b, c, d}^2] != n, a -= 1];
 {a, b, c, d}
]

Saya tidak melihat terlalu keras pada algoritma, tetapi saya berharap ini adalah ide yang sama. Saya baru saja datang dengan solusi yang jelas dan men-tweak itu sampai berhasil. Saya mengujinya untuk semua angka antara 1 dan satu miliar dan ... itu berhasil. Tes hanya membutuhkan sekitar 100 detik pada mesin saya.

Yang menyenangkan tentang ini adalah karena b, c, dan d didefinisikan dengan penugasan yang tertunda :=, mereka tidak harus didefinisikan ulang ketika a dikurangi. Ini menyelamatkan beberapa baris tambahan yang saya miliki sebelumnya. Saya mungkin bermain golf lebih jauh dan menyarang bagian-bagian yang berlebihan, tapi inilah konsep pertama.

Oh, dan Anda menjalankannya S@123456789dan Anda dapat mengujinya dengan {S@#, Total[(S@#)^2]} & @ 123456789atau # == Total[(S@#)^2]&[123456789]. Tes lengkap adalah

n=0;
AbsoluteTiming@ParallelDo[If[e != Total[(S@e)^2], n=e; Abort[]] &, {e, 1, 1000000000}]
n

Saya menggunakan pernyataan Print [] sebelumnya tetapi itu banyak memperlambatnya, meskipun tidak pernah dipanggil. Sosok pergi.

Haskell 123 + 3 = 126

main=getLine>>=print.f.read
f n=head[map(floor.sqrt)[a,b,c,d]|a<-r,b<-r,c<-r,d<-r,a+b+c+d==n]where r=[x^2|x<-[0..n],n>=x^2]

Gaya kasar sederhana di atas kotak yang sudah dihitung sebelumnya.

Perlu -Oopsi kompilasi (saya menambahkan 3 karakter untuk ini). Dibutuhkan kurang dari 1 menit untuk kasus terburuk 999950883.

Hanya diuji pada GHC.

C: 198 karakter

Saya mungkin bisa memerasnya menjadi lebih dari 100 karakter. Apa yang saya sukai dari solusi ini adalah jumlah minimal sampah, hanya for-loop biasa, melakukan apa yang harus dilakukan untuk-loop (yang gila).

i,a,b,c,d;main(n){for(scanf("%d",&n);a*a+b*b-n?a|!b?a*a>n|a<b?(--a,b=1):b?++b:++a:(a=b=0,--n,++i):c*c+d*d-i?c|!d?c*c>i|c<d?(--c,d=1):d?++d:++c:(a=b=c=d=0,--n,++i):0;);printf("%d %d %d %d",a,b,c,d);}

Dan sangat cantik:

#include <stdio.h>

int n, i, a, b, c, d;

int main() {
    for (
        scanf("%d", &n);
        a*a + b*b - n
            ? a | !b
                ? a*a > n | a < b
                    ? (--a, b = 1)
                    : b
                        ? ++b
                        : ++a
                : (a = b = 0, --n, ++i)
            : c*c + d*d - i
                ? c | !d
                    ? c*c > i | c < d
                        ? (--c, d = 1)
                        : d
                            ? ++d
                            : ++c
                    : (a = b = c = d = 0, --n, ++i)
                : 0;
    );
    printf("%d %d %d %d\n", a, b, c, d);
    return 0;
}

Sunting: Tidak cukup cepat untuk semua input, tetapi saya akan kembali dengan solusi lain. Aku akan membiarkan kekacauan operasi ternary ini tetap seperti sekarang.

Rev B: C, 179

a,b,c,d,m=1,n,q,r;main(){for(scanf("%d",&n);n%4<1;n/=4)m*=2;
for(a=sqrt(n),a-=(3+n-a*a)%4/2;r=n-a*a-b*b-c*c,d=sqrt(r),d*d-r;c=q%256)b=++q>>8;
printf("%d %d %d %d",a*m,b*m,c*m,d*m);}

Terima kasih kepada @Dennis untuk perbaikannya. Sisa jawaban di bawah ini tidak diperbarui dari rev A.

Rev A: C, 195

a,b,c,d,n,m,q;double r=.1;main(){scanf("%d",&n);for(m=1;!(n%4);n/=4)m*=2;a=sqrt(n);a-=(3+n-a*a)%4/2;
for(;(d=r)-r;q++){b=q>>8;c=q%256;r=sqrt(n-a*a-b*b-c*c);}printf("%d %d %d %d ",a*m,b*m,c*m,d*m);}

Jauh lebih cepat daripada jawaban saya yang lain dan dengan memori yang jauh lebih sedikit!

Ini menggunakan http://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem . Nomor apa pun yang bukan dari formulir berikut ini dapat dinyatakan sebagai jumlah dari 3 kotak (Saya menyebutnya formulir terlarang):

4^a*(8b+7), or equivalently 4^a*(8b-1)

Perhatikan bahwa semua angka kuadrat aneh adalah bentuk (8b+1)dan semua angka kuadrat genap bentuk 4b. Namun ini menyembunyikan fakta bahwa semua bilangan genap adalah bentuk 4^a*(odd square)==4^a*(8b+1). Akibatnya 2^x-(any square number < 2^(x-1))untuk ganjil xakan selalu dalam bentuk terlarang. Karenanya angka-angka ini dan kelipatannya adalah kasus yang sulit, itulah sebabnya mengapa banyak program di sini membagi 4 kekuatan sebagai langkah pertama.

Sebagaimana dinyatakan dalam jawaban @ xnor, N-a*atidak dapat berupa formulir terlarang untuk 2 nilai berturut-turut dari a. Di bawah ini saya menyajikan bentuk mejanya yang disederhanakan. Selain fakta bahwa setelah pembagian dengan 4 N%4tidak dapat sama dengan 0, perhatikan bahwa hanya ada 2 nilai yang mungkin untuk (a*a)%4.

(a*a)%4= 01
        +--
       1|10
  N%4= 2|21  <- (N-a*a)%4
       3|32

Jadi, kami ingin menghindari nilai-nilai (N-a*a)yang mungkin dari bentuk terlarang, yaitu yang mana (N-a*a)%4adalah 3 atau 0. Seperti dapat dilihat ini tidak dapat terjadi untuk hal yang sama Ndengan ganjil dan genap (a*a).

Jadi, algoritma saya berfungsi seperti ini:

1. Divide out powers of 4
2. Set a=int(sqrt(N)), the largest possible square
3. If (N-a*a)%4= 0 or 3, decrement a (only once)
4. Search for b and c such that N-a*a-b*b-c*c is a perfect square

Saya terutama menyukai cara saya melakukan langkah 3. Saya menambahkan 3 N, sehingga pengurangan diperlukan jika (3+N-a*a)%4 =3 atau 2. (tetapi tidak 1 atau 0.) Bagi ini dengan 2 dan seluruh pekerjaan dapat dilakukan dengan ekspresi yang cukup sederhana .

Kode tidak dikunci

Perhatikan forloop tunggal qdan gunakan pembagian / modulo untuk mendapatkan nilai dari bdan cdari itu. Saya mencoba menggunakan asebagai pembagi bukan 256 untuk menghemat byte, tetapi kadang-kadang nilai atidak benar dan program digantung, mungkin tanpa batas. 256 adalah kompromi terbaik yang bisa saya gunakan >>8alih-alih /256untuk divisi.

a,b,c,d,n,m,q;double r=.1;
main(){
  scanf("%d",&n);
  for(m=1;!(n%4);n/=4)m*=2;
  a=sqrt(n);
  a-=(3+n-a*a)%4/2;
  for(;(d=r)-r;q++){b=q>>8;c=q%256;r=sqrt(n-a*a-b*b-c*c);}
  printf("%d %d %d %d ",a*m,b*m,c*m,d*m);}

Keluaran

Sebuah kekhasan yang menarik adalah bahwa jika Anda memasukkan angka kuadrat, N-(a*a)= 0. Tetapi program mendeteksi bahwa 0%4= 0 dan penurunan ke persegi berikutnya ke bawah. Akibatnya, input bilangan persegi selalu didekomposisi menjadi sekelompok kotak yang lebih kecil kecuali jika mereka berbentuk 4^x.

999999999
31621 1 161 294

805306368
16384 0 16384 16384

999950883
31621 1 120 221

1
0 0 0 1

2
1 0 0 1

5
2 0 0 1

9
2 0 1 2

25
4 0 0 3

36
4 0 2 4

49
6 0 2 3

81
8 0 1 4

121
10 1 2 4

JavaScript - 175 191 176 173 karakter

Kekuatan kasar, tapi cepat.

Edit Cepat tetapi tidak cukup untuk beberapa input yang tidak menyenangkan. Saya harus menambahkan langkah pertama pengurangan dengan mengalikan 4.

Sunting 2 Singkirkan fungsi, keluaran di dalam loop lalu paksa keluar kontisi

Sunting 3 0 bukan input yang valid

v=(p=prompt)();for(m=1;!(v%4);m+=m)v/=4;for(a=-~(q=Math.sqrt)(v);a--;)for(w=v-a*a,b=-~q(w);b--;)for(x=w-b*b,c=-~q(x);c--;)(d=q(x-c*c))==~~d&&p([m*a, m*b, m*c, m*d],a=b=c='')

Tidak Disatukan:

v = prompt();

for (m = 1; ! (v % 4); m += m) 
{
  v /= 4;
}
for (a = - ~Math.sqrt(v); a--;) /* ~ force to negative integer, changing sign lead to original value + 1 */
{
  for ( w = v - a*a, b = - ~Math.sqrt(w); b--;)
  {
    for ( x = w - b*b, c = - ~Math.sqrt(x); c--;)
    {
      (d = Math.sqrt(x-c*c)) == ~~d && prompt([m*a, m*b, m*c, m*d], a=b=c='') /* 0s a,b,c to exit loop */
    }
  }
}

Contoh output

123456789
11111,48,10,8

805306368
16384,16384,16384,0