Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

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

Raccolta di codici sorgenti

Moderatore: Foto UtentePaolino

13
voti

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

Messaggioda Foto UtenteTardoFreak » 9 apr 2014, 19:20

Un saluto a tutti i partecipanti,
Mi sono imbattuto in un problema: calcolare la radice quadrata di un intero senza utilizzare variabili floating point per motivi di velocità. Mi era sufficiente un risultato troncato e senza resto.
Spero di fare cosa gradita nel postare la funzione che ho scritto e che va aggiungersi alla libreria di quelle di uso generale perché l' esecuzione è molto veloce.

Codice: Seleziona tutto
// Calcola la radice quadrata di un numero intero senza segno
uint32_t uintSqrt(uint32_t n) __pure
{
  uint32_t i,val;
 
  // se n vale 0 ritorna 0
  if (!n) return 0;
 
  // calcola il numero di bit di n
  i = 0;
  val = n;
  do
  {
    val = val >> 1;
    if (val) i++;
  } while (val);
 
  // assume val come 2^(i/2)
  if (!i) val=1; else val = 1 << (i>>1);
 
  // Calcola la radice babilonese.
  // 4 passaggi sono sufficienti
  for(i=0; i<4; i++) val = (val + n/val) >> 1;
 
  return val;
}


Se provate a fare uintSqrt(4281346624) vi darà come risultato 65432.

O_/
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

2
voti

[2] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto Utentecarlomariamanenti » 9 apr 2014, 19:25

Grazie Stefano. :ok:
Avatar utente
Foto Utentecarlomariamanenti
58,5k 5 10 13
G.Master EY
G.Master EY
 
Messaggi: 4268
Iscritto il: 18 gen 2012, 10:44

0
voti

[3] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto UtenteTardoFreak » 9 apr 2014, 21:19

Interessanti sono la determinazione del primo valore e poi il controllo del ciclo della radice babilonese.

Codice: Seleziona tutto
while (g1 < g0)

Invece di un numero fisso di cicli mi piace. :-)
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

0
voti

[4] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto Utentedaniele1996 » 9 apr 2014, 22:05

Scusate la mia ignoranza, ma "__pure" a cosa serve?
Avatar utente
Foto Utentedaniele1996
570 2 7 11
Sostenitore
Sostenitore
 
Messaggi: 1143
Iscritto il: 29 ago 2011, 11:29

1
voti

[5] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto Utentesimo85 » 9 apr 2014, 22:13

Avatar utente
Foto Utentesimo85
30,8k 7 12 13
Disattivato su sua richiesta
 
Messaggi: 9930
Iscritto il: 30 ago 2010, 4:59

9
voti

[6] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto UtenteTardoFreak » 9 apr 2014, 22:38

Per la cronaca,
Sto utilizzando la funzione proprio in questo preciso istante.
Mi serve per calcolare la velocità di un motore stepper nelle rampe di accelerazione/decelerazione per ogni passo del motore.
Sto usando un STM32 a soli 24MHz, per di più il task che muove il motore non è l' unico che gira. :cool:
E' incredibile la fluidità e la precisione del movimento (Vmax= 1000 step/s).

Scusatemi ma quando vedo certe cose non riesco a non esserne contento.
E dire che dopo 30 anni dovrei averci fatto il callo ... ma tant'è. :mrgreen:
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

3
voti

[7] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto UtenteDirtyDeeds » 9 apr 2014, 22:56

TardoFreak ha scritto:Mi serve per calcolare la velocità di un motore stepper nelle rampe di accelerazione/decelerazione per ogni passo del motore.


Se le rampe sono sempre le stesse, ci si può anche precalcolare la rampa per poi memorizzarla in una look-up table. Avevo usato questa soluzione per il pilotaggio di uno stepper lineare.
It's a sin to write sin instead of \sin (Anonimo).
...'cos you know that cos ain't \cos, right?
You won't get a sexy tan if you write tan in lieu of \tan.
Take a log for a fireplace, but don't take log for \logarithm.
Avatar utente
Foto UtenteDirtyDeeds
55,7k 7 11 13
G.Master EY
G.Master EY
 
Messaggi: 7013
Iscritto il: 13 apr 2010, 16:13
Località: Somewhere in nowhere

2
voti

[8] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto UtenteTardoFreak » 9 apr 2014, 23:22

E' vero,
Tuttavia dall' ultimo posto sto sfruttando spudoratamente la potenza del calcolo per trovare i migliori valori di velocità minima, massima e accelerazione.
Avrò fatto almeno un ventina di prove. Lo so, dovrei anche staccarmi un po' dal lavoro ma la vita è dura.
Poi magari a prove terminate implementerò la tabella.
Per ora sperimento e metto a punto.
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

2
voti

[9] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto Utenteeimiar » 10 apr 2014, 20:56

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
Avatar utente
Foto Utenteeimiar
248 5
Frequentatore
Frequentatore
 
Messaggi: 107
Iscritto il: 3 feb 2011, 16:41

2
voti

[10] Re: [C] Funzione di calcolo della radice quadrata di un inte

Messaggioda Foto UtenteTardoFreak » 10 apr 2014, 21:29

Mah!

Comunque ho capito il messaggio: d' ora in poi mi farò esclusivamente i caxxi miei.

Saluti. O_/
"La follia sta nel fare sempre la stessa cosa aspettandosi risultati diversi".
"Parla soltanto quando sei sicuro che quello che dirai è più bello del silenzio".
Rispondere è cortesia, ma lasciare l'ultima parola ai cretini è arte.
Avatar utente
Foto UtenteTardoFreak
73,4k 8 12 13
-EY Legend-
-EY Legend-
 
Messaggi: 15764
Iscritto il: 16 dic 2009, 11:10
Località: Torino - 3° pianeta del Sistema Solare

Prossimo

Torna a Firmware e programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti