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

[roothunter]

Salve, dato il momento storico e la noia nei giorni che avanza, ho pensato a una bella sfida da fare con voi in ambito programmazione.

Il problema
Calcolare le equazioni del tipo x^2 + y^2 = z^2, semplice vero?
La sfida sta proprio qui, impostare un equazione comune di riferimento da calcolare nel minor tempo possibile, anche non essendo un algoritmo molto difficile da pensare/progettare, la vera difficoltà della sfida sta tutta nell'ottimizzazione..

Spoiler: EQUAZIONE DI RIFERIMENTO

1937664 + 1943236 = 3880900  (1392^2 + 1394^2 = 1970^2)

Naturalmente so benissimo che in base al calcolatore su cui gira il programma si avranno tempi diversi di esecuzione.. per questo invito ognuno a pubblicare come può il proprio codice così da poterlo mettere a confronto con gli altri...

Uno dei concetti fondamentali da seguire nella sfida è porre una N di range massima su cui far iterare le tre variabili {x,y,z}, quindi l'EQUAZIONE DI RIFERIMENTO deve comprarire tra i risultati generati dai valori n^2 appartente a ℕ.

Esempio:
n = 50

########################################################################
RICERCA FINO AD UN MASSIMO DEL QUADRATO DI 50
########################################################################
EQUAZIONE TROVATA 9 + 16 = 25  (3^2 + 4^2 = 5^2)
EQUAZIONE TROVATA 25 + 144 = 169  (5^2 + 12^2 = 13^2)
EQUAZIONE TROVATA 36 + 64 = 100  (6^2 + 8^2 = 10^2)
EQUAZIONE TROVATA 49 + 576 = 625  (7^2 + 24^2 = 25^2)
EQUAZIONE TROVATA 64 + 225 = 289  (8^2 + 15^2 = 17^2)
EQUAZIONE TROVATA 81 + 144 = 225  (9^2 + 12^2 = 15^2)
EQUAZIONE TROVATA 81 + 1600 = 1681  (9^2 + 40^2 = 41^2)
EQUAZIONE TROVATA 100 + 576 = 676  (10^2 + 24^2 = 26^2)
EQUAZIONE TROVATA 144 + 256 = 400  (12^2 + 16^2 = 20^2)
EQUAZIONE TROVATA 144 + 1225 = 1369  (12^2 + 35^2 = 37^2)
EQUAZIONE TROVATA 196 + 2304 = 2500  (14^2 + 48^2 = 50^2)
EQUAZIONE TROVATA 225 + 400 = 625  (15^2 + 20^2 = 25^2)
EQUAZIONE TROVATA 225 + 1296 = 1521  (15^2 + 36^2 = 39^2)
EQUAZIONE TROVATA 256 + 900 = 1156  (16^2 + 30^2 = 34^2)
EQUAZIONE TROVATA 324 + 576 = 900  (18^2 + 24^2 = 30^2)
EQUAZIONE TROVATA 400 + 441 = 841  (20^2 + 21^2 = 29^2)
EQUAZIONE TROVATA 441 + 784 = 1225  (21^2 + 28^2 = 35^2)
EQUAZIONE TROVATA 576 + 1024 = 1600  (24^2 + 32^2 = 40^2)
EQUAZIONE TROVATA 729 + 1296 = 2025  (27^2 + 36^2 = 45^2)
EQUAZIONE TROVATA 900 + 1600 = 2500  (30^2 + 40^2 = 50^2)
NUMERO EQUAZIONI TROVATE = 21

(possibile output del file .txt)
Quindi ogni x,y,z sarà compresa nel range di {1,..,n^2}

FONDAMENTALE: x,y,z devono appartenere ai numeri NATURALI.
FONDAMENTALE: il programma non potrà usare file d'appoggio(tranne il file con l'output), tutti i calcoli sono da fare in RAM.


Linee guida
//Si va a discretizzare l'insieme di equazioni possibili dando una base massima comune alle tre variabili//
//In fase di pubblicazione del risultato si condividerà la base massima delle variabili x,y,z(n), grazie alla quale si arriva a calcolare l'EQUAZIONE DI RIFERIMENTO//
//Quindi tutte le equazioni precedenti trovate dovranno appartenere a tale insieme//
Consigliato escludere dall'output coppie, del tipo:

1. a^2 + b^2 = c^2
2. b^ 2 + a^2 = c^2

(Lasciando una sola fra le due, così da non falsare il numero di equazioni trovate)

Requisiti
Il programma dovrà:

1. Calcolare il maggior numero di equazioni del tipo x^2 + y^2 = z^2.
2. Ottimizzare il proprio algoritmo di base per rendere l'esecuzione del programma il più veloce possibile
3. Salvare tutte le equazioni trovare su un file di tipo .txt(anche il tempo di salvataggio su file deve far parte del programma)
4. Il programma potrà essere scritto in qualsiasi linguaggio di programmazione conosciuto dal partecipante(o combinazione di questi)
5. Il tempo considerato valido sarà quello impiegato per arrivare a calcolare l'EQUAZIONE DI RIFERIMENTO

Requisiti Minimi
Il programma dovrà:

• Almeno arrivare a calcolare [ 1937664 + 1943236 = 3880900 (1392^2 + 1394^2 = 1970^2) ] (EQUAZIONE DI RIFERIMENTO)
• Nel caso dell'EQUAZIONE DI RIFERIMENTO la base massima è 2000
• Il partecipante dovrà condividere il proprio codice e i tempi di esecuzione del programma sul proprio calcolatore, se previsto, il limite di calcolo del programma(EQUAZIONE LIMITE).

Quando si vince?
Oltre che avvire una discussione sull'argomento(davvero interessante a mio parere), questa sfida, servirà a trovare questo fativico "programma migliore", cosa si intende per migliore ?... nel caso di questa sfida il miglior programma è quello che impiega meno tempo per calcolare il risultato richiesto dai punti precedenti.


A breve pubblicherò il mio punteggio.
Per chi avesse dubbi o consigli sulla sfida, fate sapere con un commento
sudo bash ./roothunter.sh -m "Good Luck"

 

[roothunter]

Questo è il progetto, riesce ad arrivare all'equazione di riferimento in 1.3 secondi indicativamente(In base alla macchina su cui gira), fatemi sapere come va a voi

LINGUAGGIO: C
TEMPO DI ESECUZIONE: 1.3 sec
BASE MASSIMA: 2000
EQ TROVATE: 1981

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>


#include <sys/time.h>

#define MAX 2000
#define S_MAX MAX*MAX
#define MAX_ARR (MAX*MAX)/2
#define MAX_ELEMENT MAX

#define FILE_NAME "output.txt"

unsigned int cnt_eq = 0;



typedef struct{
    unsigned long long int x;
    unsigned long long int y;
    unsigned long long int z;
}equazione;



unsigned long long int fermat_final(equazione *eq);
void add_element(equazione *x, unsigned int *cnt);
void insert_eq(equazione *t, unsigned long long int *x, unsigned long long int *y, unsigned long long int *z, bool controll);
void stampa_iniziale();
bool check_coppie_eq(equazione *t,unsigned long long int *x, unsigned long long int *y);
void stampa(equazione *eq,unsigned long int  *cont);



void main(){
    struct timeval start, end;

    gettimeofday(&start, NULL);

    equazione *eq = (equazione*)calloc(MAX*2, sizeof(equazione));
    stampa_iniziale();
    unsigned long int c = fermat_final(eq);
    stampa(eq, &c);
    free(eq);

    gettimeofday(&end, NULL);

    double time_taken;
    time_taken = (end.tv_sec - start.tv_sec) * 1e6;
    time_taken = (time_taken + (end.tv_usec -
                              start.tv_usec)) * 1e-6;

    printf("\nTEMPO DI ESECUZIONE = %lf SEC\n", time_taken);
    system("pause");
}


void add_element(equazione *x, unsigned int *cnt){
    *cnt += 1;
    x = realloc(x, sizeof(equazione));

    x[*cnt].x = 0;
    x[*cnt].y = 0;
    x[*cnt].z = 0;
}


void insert_eq(equazione *t,unsigned long long int *x, unsigned long long int *y, unsigned long long int *z, bool controll){
    t[cnt_eq].x = *x;
    t[cnt_eq].y = *y;
    t[cnt_eq].z = *z;

    ++cnt_eq;

}


void stampa_iniziale(){
    FILE *tmp = fopen(FILE_NAME, "a");

    fprintf(tmp,"########################################################################\n");
    fprintf(tmp, "RICERCA FINO AD UN MASSIMO DEL QUADRATO DI %d\n", MAX);
    fprintf(tmp,"########################################################################\n");

    fclose(tmp);
}

bool check_coppie_eq(equazione *t,unsigned long long int *x, unsigned long long int *y){
    for(unsigned long int i = 0; i < cnt_eq; ++i){
        if((t[i].x == *x && t[i].y == *y) || (t[i].x == *y && t[i].y == *x)){
            return true;
        }
    }
    return false;
}

unsigned long long int fermat_final(equazione *eq){
    unsigned long long int x = 0;
    unsigned long long int y = 0;
    unsigned long long int z = 0;

    unsigned long long int cont = 0;

        for(unsigned long int i = 1; i <= MAX; ++i ){
            x = i*i;

        if(x+1 < S_MAX){
            for(unsigned long int j = 1; j <= MAX; ++j){
                y = j*j;
                z = x + y;

                if(z > S_MAX){
                    continue;
                }

                double sqz = sqrt(z);

                if(sqz - (unsigned long long int)sqz != 0){
                    continue;
                }

                if(check_coppie_eq(eq, &x, &y)){
                    continue;
                }
                //////////////////////////////////////////////////////////
                ++cont;
            if(z<= S_MAX){
                for(unsigned long int k = 1; k < z && sqz >= k; ++k){
                    ++cont;
                    if(sqz == k){
                        printf("TROVATA EQUAZIONE %llu + %llu = %llu\n", x,y,z);
                        insert_eq(eq, &x, &y, &z, true);
                        break;
                    }
                }
            }
        }
    }
    }



    return cont;
}

void stampa(equazione *eq,unsigned long int  *cont){
    FILE *fp = fopen(FILE_NAME, "a");

    for(unsigned long int i = 0; i < cnt_eq; ++i){
        fprintf(fp,"EQUAZIONE TROVATA %llu + %llu = %llu  (%.0lf^2 + %.0lf^2 = %.0lf^2)\n", eq[i].x,eq[i].y,eq[i].z, sqrt(eq[i].x), sqrt(eq[i].y),sqrt(eq[i].z));
    }


    printf("CONTO FINALE = %lu", *cont);
    fprintf(fp,"NUMERO EQUAZIONI TROVATE = %u", cnt_eq);
    fprintf(fp, "\nITERAZIONE EFFETTUATE = %u\n", *cont);

    fclose(fp);

}

 

[Kode]

Sposto nella sezione corretta.

 

[roothunter]

Sposto nella sezione corretta.

Grazie, però la sfida non è solo in ambito C/C++

 

[Kode]

Ok, provvedo a comunicare lo spostamento in sezione generica allora

 

[St3ve]

Forse era implicito, ma aggiungerei anche x, y > 0 altrimenti abbiamo infinite soluzioni banali nella forma 0^2 + y^2 = y^2.

Il tempo considerato valido sarà quello impiegato per arrivare a calcolare l'EQUAZIONE DI RIFERIMENTO

Secondo me anche questo punto è un po' da rivedere in quanto stai in qualche modo assumendo che per arrivare a trovare l'equazione di riferimento sia necessario trovare le precedenti. Anche fissare la base è un po' limitante: devo essere veloce a calcolarne poche? devo necessariamente calcolare tutte le equazioni entro una certa base o per far prima posso tralasciarne qualcuna? se le devo trovare tutte, c'è modo (e.g., una formula) di sapere quante ce ne sono entro un certo limite?

Per adesso sono a tipo 267734 equazioni trovate in circa 3.4 secondi, ma il codice è ancora da sistemare e probabilmente mi sto perdendo qualcosa per strada. Uno di questi giorni me lo riguardo... il codice lo posterò dopo aver sistemato un po' di roba.

 

[roothunter]

Forse era implicito, ma aggiungerei anche x, y > 0 altrimenti abbiamo infinite soluzioni banali nella forma 0^2 + y^2 = y^2.

Secondo me anche questo punto è un po' da rivedere in quanto stai in qualche modo assumendo che per arrivare a trovare l'equazione di riferimento sia necessario trovare le precedenti. Anche fissare la base è un po' limitante: devo essere veloce a calcolarne poche? devo necessariamente calcolare tutte le equazioni entro una certa base o per far prima posso tralasciarne qualcuna? se le devo trovare tutte, c'è modo (e.g., una formula) di sapere quante ce ne sono entro un certo limite?

Per adesso sono a tipo 267734 equazioni trovate in circa 3.4 secondi, ma il codice è ancora da sistemare e probabilmente mi sto perdendo qualcosa per strada. Uno di questi giorni me lo riguardo... il codice lo posterò dopo aver sistemato un po' di roba.

Io penso che per la prima affermazione basti il fatto che ho specificato più volte l'insieme dei naturali, quindi si.. non ci possono essere negativi, per lo 0 alla fine è libero il discorso, però pensavo fosse scontato x,y>0
Fissare la base serve allo scopo della sfida, non ho chiesto la quantità delle equazioni, ma che rispettassero un determinato range, ovvero x,y,z devono appartenere al range {1,..., base^2} quindi dovrebbe essere implicito che l'insieme di equazioni risultante in questo modo è discretizzato..e no, delle equazioni del tipo x^2 + y^2 = z^2 nel range della base non ne puoi saltare una.
Grazie delle ossorvazioni, non vedo l'ora di vedere il tuo codice allora


Diciamo che la sfida almeno come l'ho vista io.. era ottimizzare un brute force(riuscendo a far saltare un insieme sempre più grande di equazioni errate), poi se qualcuno riesce per altre vie bene, però il numero di equazioni a parità di base deve essere lo stesso.

sudo bash ./roothunter.sh -m "Bye"

 

[St3ve]

Quindi come faccio a verificare se le ho trovate tutte? Assumendo una base significativamente più grande di 2000.
Ad esempio, le 267734 che ho trovato sono con 0 < x < y < 65536. Sono tutte?

 

[roothunter]

Quindi come faccio a verificare se le ho trovate tutte? Assumendo una base significativamente più grande di 2000.
Ad esempio, le 267734 che ho trovato sono con 0 < x < y < 65536. Sono tutte?

Per avere la certezza matematica del numero di equazioni che rispettano un range devi iterare x,y,z in 3 cicli, così detto brute force, poi avendo i numeri veri da quello.. anche se penso che non ti convenga partire con base 2000 vedi se ottimizzando rispetti sempre il numero.. a quel punto sai che anche dopo l'ottimizzazione rispetterai il vero range di equazioni del tipo x^2 + y^2 = z^2 dove x,y,z hanno una base massima comune.

Attento pure alle coppie da elminare:

• 3^2 + 4^2 = 5^2
• 4^2 + 3^2 = 5^2

naturalmente nel caso del brute force totale troverai anche queste.. però ottimizzando andrai a tagliare il range di risultati

 

[St3ve]

Per avere la certezza matematica del numero di equazioni che rispettano un range devi iterare x,y,z in 3 cicli, così detto brute force, poi avendo i numeri veri da quello.. anche se penso che non ti convenga partire con base 2000 vedi se ottimizzando rispetti sempre il numero.. a quel punto sai che anche dopo l'ottimizzazione rispetterai il vero range di equazioni del tipo x^2 + y^2 = z^2 dove x,y,z hanno una base massima comune.

Vabbé certo, fin li ci arrivo anch'io Speravo in un modo un po' più immediato, qualcosa che non mi richiedesse di attendere a lungo per sapere il risultato. Con base 2000 ne trovo quante ne hai trovate tu in meno di 0.1 secondi, ma con numeri più alti la completezza non è così scontata. Comunque vabbé, quando rimetterò mano al codice vedrò di pensarci su un po' meglio e andare un po' meno a tentativi per certe cose... risolverò.

 

[roothunter]

Per avere la certezza matematica del numero di equazioni che rispettano un range devi iterare x,y,z in 3 cicli, così detto brute force, poi avendo i numeri veri da quello.. anche se penso che non ti convenga partire con base 2000 vedi se ottimizzando rispetti sempre il numero.. a quel punto sai che anche dopo l'ottimizzazione rispetterai il vero range di equazioni del tipo x^2 + y^2 = z^2 dove x,y,z hanno una base massima comune

Vabbé certo, fin li ci arrivo anch'io Speravo in un modo un po' più immediato, qualcosa che non mi richiedesse di attendere a lungo per sapere il risultato. Con base 2000 ne trovo quante ne hai trovate tu in meno di 0.1 secondi, ma con numeri più alti la completezza non è così scontata. Comunque vabbé, quando rimetterò mano al codice vedo di pensarci su un po' meglio e andare un po' meno a tentativi per certe cose... risolverò.

Allora complimenti per il programma

Messaggio unito automaticamente: 3 Novembre 2020

Mi fa piacere avere un confronto sull'argomento, io pure continuerò ad ottimizzare il mio codice

 

[St3ve]

Nella mia soluzione ho preferito usare i minori stretti, quindi per avere i risultati che hai tu con 2000 devi inserire 2001 come input. L'output è in stdout e la misurazione del tempo non è integrata nel codice. Ho preferito mantenere il codice snello (31 righe comprese quelle vuote) per massimizzare la leggibilità qui sul forum. Idem per altri dettagli implementativi, preferisco scrivere codice leggibile.

Linguaggio: C
Tempo di esecuzione: inferiore a 0.04s (su un laptop di 5 anni fa)
Base massima comune: 2000 (input 2001)
Modalità d'uso: time ./nomeprog base+1 > filename.txt
Conteggio delle equazioni trovate: wc -l filename.txt (confermo che sono 1981)

#include <stdio.h>
#include <stdlib.h>

unsigned long zero_or_sqrt(unsigned long x, unsigned long y) {
  unsigned long s = x * x + y * y;
  unsigned long r = y + (x >> 1);

  while (1) {
    if (r * r == s) return r;
    if ((r - 1) * (r - 1) < s && s < (r + 1) * (r + 1)) return 0;
    r = (r + s / r) >> 1;
  }
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("usage: time %s LIMIT > FILENAME.txt\n", argv[0]);
    exit(1);
  }

  unsigned long n = strtoul(argv[1], NULL, 0);

  for (unsigned long x = 1; x != n; x++) {
    for (unsigned long y = x; y != n; y++) {
      unsigned long z = zero_or_sqrt(x, y);
      if (0 < z && z < n) printf("%lu^2 + %lu^2 = %lu^2\n", x, y, z);
    }
  }

  return 0;
}

Avevo scritto anche un codice in CUDA C che calcolava le 101364 equazioni con base massima 65535 in 1.3s (contro i ~35s del codice che ho postato), ma su base massima 2000 è significativamente più lento del codice seriale: non ci sono abbastanza calcoli da fare per giustificare il tempo necessario a svegliare la GPU e trasferire i dati al suo interno. L'algoritmo era lo stesso, cambiavano solo i vari fronzoli necessari per avere il parallelismo. Avevo aggiunto coordinate bidimensionali per distribuire i vari valori di x e y sui vari threads e avevo usato uno step per dare un minimo di carico ad ognuno di essi (32 test per ogni thread invece che solo uno). Era ottimizzabilissimo pure quello ma se il limite è 2000 il parallelismo è del tutto insensato, come si vede dal codice che ho postato.

L'algoritmo effettua una ricerca dicotomica per cercare la radice:

1. se r^2 == x^2 + y^2 allora r è la radice;
2. se (r-1)^2 < x^2 + y^2 < (r+1)^2 allora non esiste una radice intera;
3. altrimenti aggiusto r usando la formula di newton, r = (r + (x^2 + y^2)/r) / 2.

Parto da r = max(x,y) + min(x,y)/2 che è un approssimazione. Si può dimostrare che zero_or_sqrt gira in tempo logaritmico, che per intenderci vuol dire che quel while termina in 3-4 iterazioni al massimo: si può migliorare l'ipotesi di partenza (i.e., provare un altro bound per l'r di partenza), ma considerando che il while termina in un pugno di cicli non aspettatevi cambiamenti sostanziali.

Se volete fare benchmark seri aggiungete la fprintf e la misurazione del tempo all'interno del programma, qualcosa si guadagna.

 

[roothunter]

Questo codice è un KO tecnico ahah
Una qualità di programmazione davvero elevata, quando hai parlato della versione in CUDA C ho capito che il problema ti ha interessato parecchio.. non posso dirti altro che top player, a questo punto si potrebbe raggiungere un secondo step per chi ha un programma che gira sotto i 2 secondi, che comprende raggiungere una certa quantità di equazioni trovate (magari 101364) il più veloce ecc.. però per il momento sei tu il vincitore, vedremo se qualcun'altrò posterà qualcos'altro..

Fatemi sapere se l'aggiunta di un livello più hardcore della sfida potrebbe piacere

sudo bash ./roothunter.sh -m "Bye"

Messaggio unito automaticamente: 4 Novembre 2020

Sono riuscito a scendere sotto il secondo però la strada per fare meno di 0.5 è davvero lunga, mi sa che mi riscriverò l'algoritmo, posso confermare che il tuo programma è ancora 3 volte più veloce del mio, questa sfida mi sta davvero piacendo.. (il tuo programma a me gira in 0.17 - 0.21 sec)

 

[nullptr]

Rust:

use std::env;

fn searchSquare(n: u64) {
    //let n = 2000;
    for i in 2..n { // ottimizzo partendo da 2 e non da 1
            for j in i..n {
                let r = i*i + j*j;
                let sqrt = (r as f64).sqrt() as u64;

                if (sqrt > n) {
                    break;
                }

                // con sqrt * sqrt == r controllo se è una radice quadrata perfetta
                if sqrt * sqrt == r {
                    println!("{}^2 + {}^2 = {}^2", i, j, sqrt);
                }
            }
    }
}

fn main() {
    let args: Vec<_> = env::args().collect();
    if args.len() > 1 {
        let num = &args[1];
        let number: u64 = match num.parse() {
                Ok(n) => {
                    n
                },
                Err(_) => {
                    println!("error: second argument not an integer");
                    return;
                },
        };
        searchSquare(number);
    }
}

compilazione ed utilizzo:

~ $ rustc searchsquare.rs
~ $ ./searchsquare [limit]

Per temporizzare il comando:

~ $ time ./searchsquare 2000 > squares.txt # stdout nel file

real 0m0,115s
user 0m0,115s
sys 0m0,000s

~ $ time ./searchsquare 2000

real 0m0,115s
user 0m0,113s
sys 0m0,000s

Premetto che il mio algoritmo è diverso da quello di St3ve, in quanto ha utilizzato la ricerca binaria.

 

[roothunter]

Rust:

use std::env;

fn searchSquare(n: u64) {
    //let n = 2000;
    for i in 2..n { // ottimizzo partendo da 2 e non da 1
            for j in i..n {
                let r = i*i + j*j;
                let sqrt = (r as f64).sqrt() as u64;

                if (sqrt > n) {
                    break;
                }

                // con sqrt * sqrt == r controllo se è una radice quadrata perfetta
                if sqrt * sqrt == r {
                    println!("{}^2 + {}^2 = {}^2", i, j, sqrt);
                }
            }
    }
}

fn main() {
    let args: Vec<_> = env::args().collect();
    if args.len() > 1 {
        let num = &args[1];
        let number: u64 = match num.parse() {
                Ok(n) => {
                    n
                },
                Err(_) => {
                    println!("error: second argument not an integer");
                    return;
                },
        };
        searchSquare(number);
    }
}

compilazione ed utilizzo:

~ $ rustc searchsquare.rs
~ $ ./searchsquare [limit]

Per temporizzare il comando:

~ $ time ./searchsquare 2000 > squares.txt # stdout nel file

real 0m0,115s
user 0m0,115s
sys 0m0,000s

~ $ time ./searchsquare 2000

real 0m0,115s
user 0m0,113s
sys 0m0,000s

Premetto che il mio algoritmo è diverso da quello di St3ve, in quanto ha utilizzato la ricerca binaria.

Non vedevo l'ora di avere un confronto su un linguaggio che non conosco, sicuramente mi hai battuto ahah, mi sapresti dire cosa ti ha portato a scegliere Rust come linguaggio per la sfida

 

[nullptr]

Non vedevo l'ora di avere un confronto su un linguaggio che non conosco, sicuramente mi hai battuto ahah, mi sapresti dire cosa ti ha portato a scegliere Rust come linguaggio per la sfida

Ho scelto Rust per non scegliere il C e particolarizzare un po' la discussione. Comunque St3ve ha implementato l'algoritmo mio da Rust in C e ha sperimentato che il mio è più veloce del suo (non avevo testato).
Ciò che faccio io è utilizzare due cicli for in esecuzione fino a prendere la radice quadrata di n, e ogni volta controllo se la somma dei quadrati di entrambi i numeri sono uguali a n.

PS. Non ho adocchiato il tuo codice, ma sicuramente è migliorabile.

 

[St3ve]

Quello di @nullptr è più veloce del mio. Pare che usare sqrt della libreria standard sia più veloce del mio sqrt_or_zero che fa una ricerca dicotomica. Non avevo verificato perché è lo stesso approccio usato da @roothunter e davo per scontato che fosse più lento in quanto anche molto più preciso (i.e., fai calcoli in virgola mobile).

 

[roothunter]

Ho scelto Rust per non scegliere il C e particolarizzare un po' la discussione. Comunque St3ve ha implementato l'algoritmo mio da Rust in C e ha sperimentato che il mio è più veloce del suo (non avevo testato).
Ciò che faccio io è utilizzare due cicli for in esecuzione fino a prendere la radice quadrata di n, e ogni volta controllo se la somma dei quadrati di entrambi i numeri sono uguali a n.

PS. Non ho adocchiato il tuo codice, ma sicuramente è migliorabile.

Ottima scelta allora !
In questi giorni rimetterò le mani sul codice e darò un ottimizzata(in tutti i sensi, anche di leggibilità), nel frattempo torno a studiare un pò di Reti di Calcolatori che non fa mai male ahah, sperando di avvicinarmi ai vostri risultati

 

[St3ve]

È più veloce perché viene compilato come

0000000000401f20 <__ieee754_sqrt>:
  401f20:       f3 0f 1e fa             endbr64 
  401f24:       f2 0f 51 c0             sqrtsd %xmm0,%xmm0
  401f28:       c3                      retq   
  401f29:       0f 1f 80 00 00 00 00    nopl   0x0(%rax)

quindi pare che ci sia un'istruzione assembly chiamata sqrtsd che calcola la radice quadrata usando un'implementazione hardware. Poco sorprendente che batta il mio sqrt_or_zero.

 

[roothunter]

Quello di @nullptr è più veloce del mio. Pare che usare sqrt della libreria standard sia più veloce del mio sqrt_or_zero che fa una ricerca dicotomica. Non avevo verificato perché è lo stesso approccio usato da @roothunter e davo per scontato che fosse più lento in quanto anche molto più preciso (i.e., fai calcoli in virgola mobile).

Io sono ancora curioso della versione in CUDA C di cui parlavi, mi ha aperto un mondo, non ho mai pensato di spostare la computazione sulla GPU(avendo solo quella integrata nella CPU) però la cosa mi stuzzica, dato che utilizzare gli array di processori presenti nella GPU potrebbe velocizzare un sacco calcoli su variabili vettoriali, a volte programmando ad altissimo livello(Python) ci si scorda di tutte le possibilità che ci vengono nasconte da un così alto livello di astrazione, ed avere un confronto su questi temi è davvero interessante come cosa a parer mio
Ho pensato pure ad un eventuale AI per questo problema però non è una soluzione votata alla velocità secondo me..

 

[St3ve]

Ho spulciato un po' in giro per internet e ho trovato queste due pagine di wikipedia: Formulas for generating Pythagorean triples e Tree of primitive Pythagorean triples. In particolare, l'albero delle triple pitagoriche primitive mi è sembrato molto semplice da implementare e quindi ci ho provato. Il codice è poco più lungo del precedente (8 linee in più) e come velocità ovviamente non c'è storia rispetto alle soluzioni bruteforce che testano tutti i possibili valori. Il vantaggio principale infatti è che funziona molto meglio su numeri molto grandi: dove il mio ci impiegava 30 secondi e quello di nullptr ci mette 10 secondi, questo ci mette 20 millisecondi.

Linguaggio: C
Tempo di esecuzione: circa mezzo millisecondo su base massima comune 2000 (input 2000)
Modalità d'uso: time ./nomeprog base > filename.txt

#include <stdio.h>
#include <stdlib.h>

const long first[3] = {3, 4, 5};
const long mat[3][9] = {{  1, -2,  2,  2, -1,  2,  2, -2,  3 },
                       {  1,  2,  2,  2,  1,  2,  2,  2,  3 },
                       { -1,  2,  2, -2,  1,  2, -2,  2,  3 }};

void pythagorean(const long sol[3], long limit) {
  if (sol[2] > limit) return;

  printf("%ld^2 + %ld^2 = %ld^2\n", sol[0], sol[1], sol[2]);

  long res[9];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      res[i * 3 + j] =
        sol[0] * mat[i][0 + j * 3] +
        sol[1] * mat[i][1 + j * 3] +
        sol[2] * mat[i][2 + j * 3];
    }

    pythagorean(res + 3 * i, limit);
  }

  for (int j = 2; j <= limit / sol[2]; j++)
    printf("%ld^2 + %ld^2 = %ld^2\n", sol[0]*j, sol[1]*j, sol[2]*j);
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("usage: time %s LIMIT > FILENAME.txt\n", argv[0]);
    exit(1);
  }

  long limit = strtol(argv[1], NULL, 0);
  pythagorean(first, limit);
  return 0;
}

Io sono ancora curioso della versione in CUDA C di cui parlavi

Ho il brutto vizio di programmarli direttamente in /tmp questi esercizi che faccio solo qualcuno sul forum chiede aiuto o cose simili... ho riavviato per aggiornare il sistema e quel codice è andato perso. In questo momento non posso manco riscriverlo al volo perché il kernel 5.9 pare che dia problemi con i driver Nvidia e CUDA non mi funziona. Ricordamelo più tra qualche settimana e te lo riscrivo. Comunque, come già detto nell'altro post, l'algoritmo non era differente da quello che avevo già postato... cambia solo la modalità di implementazione. La parallelizzazione è banale.

Ho pensato pure ad un eventuale AI per questo problema però non è una soluzione votata alla velocità secondo me..

Non ho idea di cosa avevi in mente, ma... mi sembra che non abbia proprio alcun senso. You're choosing the wrong tool for the job. Magari spiega meglio cosa avevi in mente di fare perché io non vedo nessuna evidente relazione tra questi due argomenti.

EDIT: ho modificato il codice per mettere le stampe in ordine crescente.

 

[nullptr]

Ho spulciato un po' in giro per internet e ho trovato queste due pagine di wikipedia: Formulas for generating Pythagorean triples e Tree of primitive Pythagorean triples. In particolare, l'albero delle triple pitagoriche primitive mi è sembrato molto semplice da implementare e quindi ci ho provato. Il codice è poco più lungo del precedente (7 linee in più) e come velocità ovviamente non c'è storia rispetto alle soluzioni bruteforce che testano tutti i possibili valori. Il vantaggio principale infatti è che funziona molto meglio su numeri molto grandi: dove il mio ci impiegava 30 secondi e quello di nullptr ci mette 10 secondi, questo ci mette 20 millisecondi.

Linguaggio: C
Tempo di esecuzione: circa mezzo millisecondo su base massima comune 2000 (input 2000)
Modalità d'uso: time ./nomeprog base > filename.txt

#include <stdio.h>
#include <stdlib.h>

const long first[3] = {3, 4, 5};
const long mat[3][9] = {{  1, -2,  2,  2, -1,  2,  2, -2,  3 },
                       {  1,  2,  2,  2,  1,  2,  2,  2,  3 },
                       { -1,  2,  2, -2,  1,  2, -2,  2,  3 }};

void pythagorean(const long sol[3], long limit) {
  if (sol[2] > limit) return;

  printf("%ld^2 + %ld^2 = %ld^2\n", sol[0], sol[1], sol[2]);
  for (int j = 2; j <= limit / sol[2]; j++)
    printf("%ld^2 + %ld^2 = %ld^2\n", sol[0]*j, sol[1]*j, sol[2]*j);

  long res[9];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      res[i * 3 + j] =
        sol[0] * mat[i][0 + j * 3] +
        sol[1] * mat[i][1 + j * 3] +
        sol[2] * mat[i][2 + j * 3];
    }

    pythagorean(res + 3 * i, limit);
  }
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("usage: time %s LIMIT > FILENAME.txt\n", argv[0]);
    exit(1);
  }

  long limit = strtol(argv[1], NULL, 0);
  pythagorean(first, limit);
  return 0;
}

Ho il brutto vizio di programmarli direttamente in /tmp questi esercizi che faccio solo qualcuno sul forum chiede aiuto o cose simili... ho riavviato per aggiornare il sistema e quel codice è andato perso. In questo momento non posso manco riscriverlo al volo perché il kernel 5.9 pare che dia problemi con i driver Nvidia e CUDA non mi funziona. Ricordamelo più tra qualche settimana e te lo riscrivo. Comunque, come già detto nell'altro post, l'algoritmo non era differente da quello che avevo già postato... cambia solo la modalità di implementazione. La parallelizzazione è banale.


Non ho idea di cosa avevi in mente, ma... mi sembra che non abbia proprio alcun senso. You're choosing the wrong tool for the job. Magari spiega meglio cosa avevi in mente di fare perché io non vedo nessuna evidente relazione tra questi due argomenti.

ggwp amico mio. Fatti sentire su Skype e ne parliamo meglio.

 

[roothunter]

Ho spulciato un po' in giro per internet e ho trovato queste due pagine di wikipedia: Formulas for generating Pythagorean triples e Tree of primitive Pythagorean triples. In particolare, l'albero delle triple pitagoriche primitive mi è sembrato molto semplice da implementare e quindi ci ho provato. Il codice è poco più lungo del precedente (7 linee in più) e come velocità ovviamente non c'è storia rispetto alle soluzioni bruteforce che testano tutti i possibili valori. Il vantaggio principale infatti è che funziona molto meglio su numeri molto grandi: dove il mio ci impiegava 30 secondi e quello di nullptr ci mette 10 secondi, questo ci mette 20 millisecondi.

Linguaggio: C
Tempo di esecuzione: circa mezzo millisecondo su base massima comune 2000 (input 2000)
Modalità d'uso: time ./nomeprog base > filename.txt

#include <stdio.h>
#include <stdlib.h>

const long first[3] = {3, 4, 5};
const long mat[3][9] = {{  1, -2,  2,  2, -1,  2,  2, -2,  3 },
                       {  1,  2,  2,  2,  1,  2,  2,  2,  3 },
                       { -1,  2,  2, -2,  1,  2, -2,  2,  3 }};

void pythagorean(const long sol[3], long limit) {
  if (sol[2] > limit) return;

  printf("%ld^2 + %ld^2 = %ld^2\n", sol[0], sol[1], sol[2]);
  for (int j = 2; j <= limit / sol[2]; j++)
    printf("%ld^2 + %ld^2 = %ld^2\n", sol[0]*j, sol[1]*j, sol[2]*j);

  long res[9];
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      res[i * 3 + j] =
        sol[0] * mat[i][0 + j * 3] +
        sol[1] * mat[i][1 + j * 3] +
        sol[2] * mat[i][2 + j * 3];
    }

    pythagorean(res + 3 * i, limit);
  }
}

int main(int argc, char *argv[]) {
  if (argc != 2) {
    printf("usage: time %s LIMIT > FILENAME.txt\n", argv[0]);
    exit(1);
  }

  long limit = strtol(argv[1], NULL, 0);
  pythagorean(first, limit);
  return 0;
}

Ho il brutto vizio di programmarli direttamente in /tmp questi esercizi che faccio solo qualcuno sul forum chiede aiuto o cose simili... ho riavviato per aggiornare il sistema e quel codice è andato perso. In questo momento non posso manco riscriverlo al volo perché il kernel 5.9 pare che dia problemi con i driver Nvidia e CUDA non mi funziona. Ricordamelo più tra qualche settimana e te lo riscrivo. Comunque, come già detto nell'altro post, l'algoritmo non era differente da quello che avevo già postato... cambia solo la modalità di implementazione. La parallelizzazione è banale.


Non ho idea di cosa avevi in mente, ma... mi sembra che non abbia proprio alcun senso. You're choosing the wrong tool for the job. Magari spiega meglio cosa avevi in mente di fare perché io non vedo nessuna evidente relazione tra questi due argomenti.

Mi spiego meglio, l'idea principale si discosta dalla "traccia", fai bene a dire che non c'entra niente perché è così, scusa ma sono stato troppo sintetico, il mio era più un test, ovvero creare un programma che legge banalmente tutte le possibili equazioni sempre di quel tipo, in un range, sia quelle errate che non.. flaggando(passatemi il termine) le equazioni che per noi sono giuste come target in modo da passare questo "dataset" contente tuple del tipo (x, y, z, {si, no}), ad un algoritmo di apprendimento, la mia era più una curiosità, se potesse avere senso una cosa del genere oppure no.

Messaggio unito automaticamente: 10 Novembre 2020

In merito al nuovo codice da te postato non vedo l'ora di studiarlo per bene

Messaggio unito automaticamente: 11 Novembre 2020

Mi spiego meglio, l'idea principale si discosta dalla "traccia", fai bene a dire che non c'entra niente perché è così, scusa ma sono stato troppo sintetico, il mio era più un test, ovvero creare un programma che legge banalmente tutte le possibili equazioni sempre di quel tipo, in un range, sia quelle errate che non.. flaggando(passatemi il termine) le equazioni che per noi sono giuste come target in modo da passare questo "dataset" contente tuple del tipo (x, y, z, {si, no}), ad un algoritmo di apprendimento, la mia era più una curiosità, se potesse avere senso una cosa del genere oppure no.

Messaggio unito automaticamente: 10 Novembre 2020

In merito al nuovo codice da te postato non vedo l'ora di studiarlo per bene

P. S ho finito le reazioni per oggi, però il tuo programma ne merita una sicuramente

 

[St3ve]

Mi spiego meglio, l'idea principale si discosta dalla "traccia", fai bene a dire che non c'entra niente perché è così, scusa ma sono stato troppo sintetico, il mio era più un test, ovvero creare un programma che legge banalmente tutte le possibili equazioni sempre di quel tipo, in un range, sia quelle errate che non.. flaggando(passatemi il termine) le equazioni che per noi sono giuste come target così da passare questo "dataset" contente tuple del tipo (x, y, z, {si, no}), così da usare questi dati come dati di apprendimento, la mia era più una curiosità, se potesse avere senso una cosa del genere oppure no.

È plausibile che qualcosa possa funzionare, perché dalla spiegazione di wikipedia del programma che ho scritto fa proprio vedere che c'è una combinazione lineare che ci permette di generare le triple. Potresti lavorare di reverse engineering: sapendo com'è fatta questa combinazione lineare (i.e., tre matrici 3x3), implementi un'intelligenza artificiale predisposta per indirizzarsi verso quella strada. Però secondo me il problema è proprio di fondo: cosa deve fare questa intelligenza artificiale? Se gli passi una tripla (x,y,z) e ti aspetti una predizione sì/no, beh allora tanto vale verificare se x^2 + y^2 == z^2. Se gli passi una tripla e gli chiedi di generarti la successiva, uhm... si può provare, ma probabilmente non con il genere di AI che pensi tu.

P. S ho finito le reazioni per oggi, però il tuo programma ne merita una sicuramente

Provalo, è un proiettile.

 

[roothunter]

È plausibile che qualcosa possa funzionare, perché dalla spiegazione di wikipedia del programma che ho scritto fa proprio vedere che c'è una combinazione lineare che ci permette di generare le triple. Potresti lavorare di reverse engineering: sapendo com'è fatta questa combinazione lineare (i.e., tre matrici 3x3), implementi un'intelligenza artificiale predisposta per indirizzarsi verso quella strada. Però secondo me il problema è proprio di fondo: cosa deve fare questa intelligenza artificiale? Se gli passi una tripla (x,y,z) e ti aspetti una predizione sì/no, beh allora tanto vale verificare se x^2 + y^2 == z^2. Se gli passi una tripla e gli chiedi di generarti la successiva, uhm... si può provare, ma probabilmente non con il genere di AI che pensi tu.

Io pensavo più alla seconda opzione sinceramente, ovvero, con i programmi che stiamo postando creare il dataset(nel modo più veloce possibile), poi da quel dataset riuscire a trovare in modo autonomo le successive triple, dal punto di vista implementativo sono ancora lontano, però mi sembrava un buon argomento di discussione, sempre rimandendo in tema, aspettando altri partecipanti

Messaggio unito automaticamente: 11 Novembre 2020

Linguaggio: C
Tempo di esecuzione: 0.041 sec(senza stampa a console), 0.39 sec(stampa senza newline), 0.67 sec(stampa con newline)
Base massima comune: 2000

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void stampa(long MAX ,long m[MAX][3], int size){
    for(int i = 0; i < size; ++i){
        //printf("%lu^2+%lu^2=%lu^2", m[i][0], m[i][1], m[i][2]);
        printf("%lu^2+%lu^2=%lu^2\n", m[i][0], m[i][1], m[i][2]);

    }
}

void my_calc(long MAX){
    long x = 0;
    long y = 0;
    double z = 0;
    int cont = 0;

    long mat[MAX*2][3];

    for(int i = 2; i < MAX; ++i){
        x = i*i;
        for(int j = i; j < x; ++j){
            y = j*j;
            z = sqrt(x+y);

            if(z > MAX) break;
            if(z - (unsigned int) z != 0) continue;

            mat[cont][0] = i;
            mat[cont][1] = j;
            mat[cont][2] = z;

            ++cont;
        }
    }

    stampa(MAX*2,mat, cont);
}

int main(int argc, char **argv){

    if(argc != 2){
        printf("usage: time %s LIMIT\n", argv[0]);
        exit(1);
    }

    long MAX = strtol(argv[1], NULL, 0);
    my_calc(MAX);

    return 0;
}

Non sarà performante come i vostri..(quasi ahah) però rispetto al mio precedente programma è davvero più rapido, questo è quello che mi è venuto in mente a quest'ora..
So bene di poter spremere ancora un pò dal programma, nei prossimi giorni vedrò di aggiornarlo, fatemi sapere cosa ne pensate.

Messaggio unito automaticamente: 11 Novembre 2020

Io pensavo più alla seconda opzione sinceramente, ovvero, con i programmi che stiamo postando creare il dataset(nel modo più veloce possibile), poi da quel dataset riuscire a trovare in modo autonomo le successive triple, dal punto di vista implementativo sono ancora lontano, però mi sembrava un buon argomento di discussione, sempre rimandendo in tema, aspettando altri partecipanti

Messaggio unito automaticamente: 11 Novembre 2020

Linguaggio: C
Tempo di esecuzione: 0.041 sec(senza stampa a console), 0.39 sec(stampa senza newline), 0.67 sec(stampa con newline)
Base massima comune: 2000

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void stampa(long MAX ,long m[MAX][3], int size){
    for(int i = 0; i < size; ++i){
        //printf("%lu^2+%lu^2=%lu^2", m[i][0], m[i][1], m[i][2]);
        printf("%lu^2+%lu^2=%lu^2\n", m[i][0], m[i][1], m[i][2]);

    }
}

void my_calc(long MAX){
    long x = 0;
    long y = 0;
    double z = 0;
    int cont = 0;

    long mat[MAX*2][3];

    for(int i = 2; i < MAX; ++i){
        x = i*i;
        for(int j = i; j < x; ++j){
            y = j*j;
            z = sqrt(x+y);

            if(z > MAX) break;
            if(z - (unsigned int) z != 0) continue;

            mat[cont][0] = i;
            mat[cont][1] = j;
            mat[cont][2] = z;

            ++cont;
        }
    }

    stampa(MAX*2,mat, cont);
}

int main(int argc, char **argv){

    if(argc != 2){
        printf("usage: time %s LIMIT\n", argv[0]);
        exit(1);
    }

    long MAX = strtol(argv[1], NULL, 0);
    my_calc(MAX);

    return 0;
}

Non sarà performante come i vostri..(quasi ahah) però rispetto al mio precedente programma è davvero più rapido, questo è quello che mi è venuto in mente a quest'ora..
So bene di poter spremere ancora un pò dal programma, nei prossimi giorni vedrò di aggiornarlo, fatemi sapere cosa ne pensate.

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

Messaggio unito automaticamente: 11 Novembre 2020

Pubblico la versione che non ha limiti sulla base massima, il precedente programma invece ha dei limiti dovuti all'allocazione dell'array, però più utile in caso si volessero mantenere le triple trovate in una struttura.

Spoiler: CODICE

#include <stdio.h>
#include <stdlib.h>
#include <math.h>


void my_calc(long MAX){
    long x = 0;
    long y = 0;
    double z = 0;
    int cont = 0;


    for(int i = 2; i < MAX; ++i){
        x = i*i;
        for(int j = i; j < x; ++j){
            y = j*j;
            z = sqrt(x+y);

            if(z > MAX) break;
            if(z - (unsigned int) z != 0) continue;

            printf("%lu^2+%lu^2=%lu^2\n", i, j, z);
            ++cont;
        }
    }

    printf("EQ = %d", cont);
}

int main(int argc, char **argv){

    if(argc != 2){
        printf("usage: time %s LIMIT\n", argv[0]);
        exit(1);
    }

    long MAX = strtol(argv[1], NULL, 0);
    my_calc(MAX);

    return 0;
}