[C] Funzione di calcolo della radice quadrata di un intero

[eimiar]

Ehi ehi, frena! Non so se hai recepito il mio messaggio come una critica, ma ti assicuro che non lo è e né lo voleva essere.
Io ho solamente cercato di trovare una funzione più performante perché con un micro da 24 MHz gli algoritmi devono essere ottimizzati al massimo.
Ovviamente non voglio neanche spacciare la mia soluzione come la più veloce nel mondo dell'informatica, però è quella che conosco.
Volevo solo condividere la mia conoscenza

Quindi per piacere, la prossima volta non ti fare i caxxi tuoi...
Se ognuno si facesse i cosi suoi il forum diventerebbe un posto triste e desolato

[TardoFreak]

Infatti lo è, e penso che d' ora in poi lo sarà ancora di più.
Vedi, in questo forum, in tutti i suoi articoli e discussioni, non si trova una caxxo di funzione in C per calcolare la radice quadrata di un intero.
Ho spulciato l' intero forum ma niente, nada, nothing, nisba, hakuna.
Ma come se ne posta una arrivano i professoroni a dire di tutto, caxxate comprese.
Però prima d' ora una funzione del caxxo scritta e pronta da incollare in un sorgente non c' era.

E anche adesso, in questa discussione, non ho ancora trovato scritto fra i tag "code" un codice più veloce. Link ad articoli, libri, di tutto e di più ma non una funzione da copiare ed incollare nel programma.

Ed ho detto tutto.

[eimiar]

Non sono d'accordo su nulla di ciò che hai detto.
Andiamo con ordine:

Infatti lo è, e penso che d' ora in poi lo sarà ancora di più.
Vedi, in questo forum, in tutti i suoi articoli e discussioni, non si trova una caxxo di funzione in C per calcolare la radice quadrata di un intero.
Ho spulciato l' intero forum ma niente, nada, nothing, nisba, hakuna.

Posso scommetterci che non è il primo caso in cui una discussione non l'abbia mai iniziata nessuno sul forum, soprattutto su un argomento specifico e dettagliato come questo.

Ma come se ne posta una arrivano i professoroni a dire di tutto, caxxate comprese.
Però prima d' ora una funzione del caxxo scritta e pronta da incollare in un sorgente non c' era.

Non ti devi arrabbiare se nessuno ci ha mai pensato prima di te e nel momento in cui fai partire la discussione ti arrivano le risposte, questo è un forum e quindi si discute. Se non sei d'accordo con le risposte che ti scrivono allora con un po' di pazienza rispondi cercando di mantenere il buonsenso. Qui non mi pare che nessuno si sia atteggiato da professorone.

E anche adesso, in questa discussione, non ho ancora trovato scritto fra i tag "code" un codice più veloce. Link ad articoli, libri, di tutto e di più ma non una funzione da copiare ed incollare nel programma.

Il codice che ti ho fornito io è stato testato e funziona, ti ho anche fornito un benchmark specifico per cui dovrebbe essere più veloce, come documentato anche dai link che ho incluso. Se sostieni che non è più veloce allora per cortesia pubblica i tuoi dati perché mi interessa. Non so per quanto riguarda il codice che ti ha fornito simo85, tanto meno per la lookup table (ma sono convinto che senz'altro la lookup table sarà il metodo più veloce in assoluto). Inoltre non puoi pretendere di avere la pappa pronta di aprire la pagina e copincollare il codice nel tuo programma senza ritoccarlo perché 1) non siamo i tuoi servi 2) devi adattare il codice alle tue esigenze.

[TardoFreak]

... non puoi pretendere di avere la pappa pronta di aprire la pagina e copincollare il codice nel tuo programma senza ritoccarlo perché 1) non siamo i tuoi servi 2) devi adattare il codice alle tue esigenze.

Fammi capire, stai dicendo questa cosa ... a me?

[eimiar]

Avrò capito male, ma nel post che ho quotato ti sei lamentato di non riuscire a trovare una funzione da copincollare nel tuo programma.
Comunque, cercando di non andare troppo fuori tema, potresti spiegare perché il codice che ti è stato fornito non va bene? Se dici che è più lento di quello che hai scritto tu a me interesserebbe vedere dei dati a tuo sostegno, questo non è un processo dove devi dimostrare di essere "immocente", ma semplicemente ho bisogno di sapere se il mio codice è sbagliato oppure è fatto male. Altrimenti mi metto l'anima in pace e lascio stare.
Però per adesso a me sembra che la velocità della tua funzione sia pressoche pari alla velocità della funzione pow della libreria math dello standard C, e a mio sostegno ho pubblicato anche un benchmark che ho fatto sul mio processore con architettura x86.
Gradirei vedere un benchmark sulla architettura del tuo micro.

[TardoFreak]

Micro: STM32F100C8T6
Clock 24 MHz.
Compilatore KEIL v5
Misurato con: oscilloscopio delle balle philips del 1989

Codice: Seleziona tutto

uint32_t i;
i=sqrt(4281346624);

Livello ottimizzazione 0 82 us.
Livello ottimizzazione 3 72 us.

Codice: Seleziona tutto

i = pow(4281346624, 0.5);

Livello ottimizzazione 0 76 us.
Livello ottimizzazione 3 76 us.

Codice: Seleziona tutto

i = uintSqrt(4281346624);

Livello ottimizzazione 0 12 us.
Livello ottimizzazione 3 9 us.

Inutile dire che lo sapevo già altrimenti non avrei speso del tempo per riscrivermi la funzione.
Inutile dire il tuo test su un x86 non ha nessun senso perché sarebbe come comparare un cavolfiore con una chiave inglese.
Inutile dire che tu non hai idea del perché di questa differenza.
Inutile dire che se vuoi sapere il perché te lo farai spiegare da qualcun altro.

Adios.

[eimiar]

Questo benchmark non dice abbastanza. Quei risultati erano prevedibili.
Ma soprattutto mancano i test alla mia funzione, alle funzioni di simo85, il codice del benchmark e il metodo di misura.
Per quanto riguarda il resto non mi prendere per un cretino ma io so che le operazioni su floating point sono più lente delle operazioni su integer.

Inoltre nei codici che hai utilizzato hai passato un int e un double alla funzione pow, causando la chiamata a pow(double,double) mentre nella chiamata a sqrt hai usato un int per cui il compilatore ti avrebbe dovuto generare un errore a causa di conflicting types non avrebbe potuto scegliere quale funzione chiamare, se sqrt(float) o sqrt(double).
Inutile dire che le operazioni su float sono più veloci delle operazioni su double.
Insomma 'sto test non è credibile.
Se effettui il test come si deve sono anche pronto a darti ragione.

[TardoFreak]

Tieniti la ragione, ne faccio volentieri a meno.

Altri test non ne faccio. Non ho tempo da perdere con queste caxxate, devo lavorare.

[eimiar]

Vabbè allora buon lavoro, spero di leggere i risultati del test non appena hai del tempo libero.

[Shockwaver]

Giusto per curiosità, non fai calcoli in floating point solamente per motivi di performance?
Questa funzione calcola il reciproco di una radice quadrata, però in floating point.
È molto veloce nel farlo, ma non è molto preciso (un piccolo prezzo da pagare).

Qui la funzione

Codice: Seleziona tutto

float Q_rsqrt( float number )
{
   long i;
   float x2, y;
   const float threehalfs = 1.5F;

   x2 = number * 0.5F;
   y  = number;
   i  = * ( long * ) &y;                       // evil floating point bit level hacking
   i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
   y  = * ( float * ) &i;
   y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

   return y;
}

Qui un esempio di imprecisione
http://ideone.com/X2w19T

Qui un benchmark abbastanza rozzo effettuato sul mio computer (leggi i commenti in cima)
http://pastebin.com/dja2fCC1
(Secondo il mio benchmark la tua funzione è a pari velocità della funzione pow() dello standard C, mentre sqrt() e Q_rsqrt() sono veloci circa il doppio, ma tutto questo ovviamente non conta in un STM32 a 24MHz)

Qui un articolo dettagliato su wikipedia
http://en.wikipedia.org/wiki/Fast_inverse_square_root


// EDIT
Mi sono accorto solo dopo che per aumentare la precisione della funzione è sufficiente aggiungere iterazioni, che nel codice sono commentate

Ma la smetti di sparare cazzate???
Ho cercato di volgere altrove le mie attenzioni ma non ci sono riuscito non di fronte a certe cose..
Quoto questo post non perché sia l'unico verso il quale io non sia d'accordo ma solo perché è quello che mi ha fatto maggiormente accaponare la pelle.
Il tuo bench non è semplicemente rozzo e fuori luogo come tu stesso (quantomeno) hai ammesso, è soprattutto, tecnicamemente parlando, ASSURDO E FUORI DA OGNI GRAZIA DIVINA e segno di una profonda presunzione.
Ascolta, ma tu veramente stai accostando l'esecuzione di codice all'interno di uno su centinaia di thread che girano su un processore magari multicore a 64 bit con circuiteria dedicata per operazioni in floating point a doppia precisione, con quello che gira su di una MCU come quella in oggetto??
Guarda, ti consiglio caldamente, prima di parlare, di prendere una IDE per la programmazione dei micro, buttarci dentro il codice, compilare e leggerti il disassembly generato. E se vedi anche solo una istruzione asm in più (perché a naso mi vien di dire così) ricordati della frequenza in oggetto e del tipo di applicazione di cui stiamo parlando, un'aiutino? Si è persino parlato di tabelle per la referenziazione diretta al valore interessato pur di andar veloci....

... assurdo...

TardoFreak sicuramente utilizza quella routine, perché è quella di cui ha bisogno, perché probabilmente l'errore generato dalla mancanza di valori decimali è irrilevante ai fini dell'applicazione e anche solo qualche istruzione assembly in meno gli fa molto comodo