Discussione PROGRAMMING CHALLENGE {x^2 + y^2 = z^2} ∈ ℕ

[St3ve]

Facendo dei test ho notato che la velocità si avvicina molto a quella di @St3ve, vorrei avere un riscontro anche vostro.

Su input anche solo leggermente più grandi ci mette molto di più del mio vecchio codice e anche molto più del tuo vecchio codice, il problema è che hai sbagliato la condizione del for interno: sostituisci for(int j = i; j < x; ++j) con for(int j = i; j < max; ++j) e quello che ottieni è la traduzione in C del codice postato da nullptr. Aggiungerei anche di fare un cast a unsigned int sulla z all'interno della printf, perché così com'è le stampe sono tutte sbagliate.

0.041 sec(senza stampa a console), 0.39 sec(stampa senza newline), 0.67 sec(stampa con newline)

La stampa può essere velocizzata parecchio usando funzioni diverse da printf e usando un buffer abbastanza grande: meglio scrivere tanto testo in un colpo solo che poco testo un po' per volta. Io non mi sono preoccupato di farlo perché secondo me la parte interessante è l'algoritmo in sé e non la stampa però, come hai visto tu stesso, se sei interessato solo al tempo anche queste modifiche ti portano a miglioramenti considerevoli.

Se tolgo la stampa (e metto un counter) dal mio ultimo codice, arrivo a trovare:

• input 2000, 1981 terne, 12 nanosecondi;
• input 65535, 101364 tern, 248 nanosecondi (i.e., 0.000248 secondi);
• input 1000000000 (1 miliardo), 3080075432 (~3 miliardi 80 milioni) terne, ~3.5 secondi; e
• con input più grandi (facendo attenzione agli overflow) arriva facilmente a calcolare anche 20-30 miliardi di terne in poche decine di secondi, stando praticamente sempre sotto al minuto.

Quindi anche il mio ultimo codice può essere facilmente migliorato semplicemente sostituendo quelle printf con qualcosa di più intelligente, è che mi sembra poco interessante perché è un difetto completamente slegato dal problema che andiamo a risolvere.