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

[daniele1996]

Scusate se rianimo questo post, (premetto che non sono nessuno per dirlo) ma non sarebbe meglio metterlo in cima alle discussioni? in quel riquadro messo separato? secondo me sarebbe meglio... oppure linkarlo in un singolo topic insieme ad altri link che possono tornar utili per raggiungere topic del genere... alla fin fine può tornar utile a tutti!

[TardoFreak]

Ieri ho scoperto che l' analisi di correttezza parziale del calcolo della radice con il metodo babilonese è stato oggetto di lezione nel di programmazione 1 corso A di informatica (unito) 2014/2015.

[angel99]

Ciao Freak.

Premetto che il C lo uso ben poco dato che scrivo programmini semplici in assembler, quindi è possibile stia dicendo una castroneria. Guardavo questa parte del programma che hai scritto e mi domandavo il perché di quel condizionale all'interno del loop

Codice: Seleziona tutto

// calcola il numero di bit di n
  i = 0;
  val = n;
  do
  {
    val = val >> 1;
    if (val) i++;
  } while (val);


Visto che in caso di false si esce subito dal loop, non si potrebbe partire da -1 invece che da 0 e togliere il confronto che fa perdere tempo ad ogni interazione? Così per intenderci

Codice: Seleziona tutto

// calcola il numero di bit di n
  i = -1;
  val = n;
  do
  {
    val = val >> 1;
    i++;
  } while (val);


E' probabile che abbia detto una castronata, non te la prendere.

[eAlucarD]

non puoi scrivere -1 in un unsigned
non grave perché potresti sottrarlo alla fine

per quanto mi riguarda è più lodevole che qualcuno abbia condiviso un risultato ottenuto
per di più ha risolto ilproblema della radice,nella radice del tempoche ci metteva prima (affermazione degna del sig Baggings )

questa è da stampare e incorniciare


goodjob

[angel99]

Sapevo che c'era l'inghippo... ecco la correzione.

Codice: Seleziona tutto

/ calcola il numero di bit di n
  i = 0;
  val = n;
  do
  {
    val = val >> 1;
    i++;
  } while (val);
  n--;


E' una routine molto interessante (grazie Freak).
Appena posso la trascrivo in asm...

[TardoFreak]

Visto che oggi ho ripreso questa routine integrerò questo post o con una versione aggiornata o con l' output in assembler per il Cortex-M3.
Stay tuned

[PietroBaima]

ficus!

[TardoFreak]

Non ci ho ancora messo le mani ma ho voluto dare uno sguardo a come il compilatore lavora.
Come si può notare utilizzare un processore SERIO con un set d' istruzioni furbo porta a produrre codice macchina compatto. Una funzione come questa, se compilata per un 8bit avrebbe prodotto molto più codice macchina. Quindi è bene farsene una ragione e passare ai 32bit.
Diciamo che fare i cicli che contano verso lo 0 avrebbero fatto risparmiare qualche istruzione, ma questo non avrebbe portato risultati apprezzabili.
Questo è l' output in assembler

Codice: Seleziona tutto

                  uintSqrt PROC
;;;130    // Utilizza il metodo di calcolo della radice babilonese
;;;131    uint32_t uintSqrt(uint32_t n) __pure
00012a  0001              MOVS     r1,r0
;;;132    {
00012c  d004              BEQ      |L1.312|
;;;133      uint32_t i,val;
;;;134     
;;;135      // se n vale 0 ritorna 0
;;;136      if (!n) return 0;
;;;137     
;;;138      // calcola il numero di bit di n
;;;139      i = 0;
00012e  2200              MOVS     r2,#0
                  |L1.304|
;;;140      val = n;
;;;141      do
;;;142      {
;;;143        val = val >> 1;
000130  0840              LSRS     r0,r0,#1
;;;144        if (val) i++;
000132  d003              BEQ      |L1.316|
000134  1c52              ADDS     r2,r2,#1
000136  e7fb              B        |L1.304|
                  |L1.312|
000138  2000              MOVS     r0,#0                 ;136
;;;145      } while (val);
;;;146     
;;;147      // assume val come 2^(i/2)
;;;148      if (!i) val=1; else val = 1 << (i>>1);
;;;149     
;;;150      // Calcola la radice babilonese.
;;;151      // 4 passaggi sono sufficienti
;;;152      for(i=0; i<4; i++) val = (val + n/val) >> 1;
;;;153     
;;;154      return val;
;;;155    }
00013a  4770              BX       lr
                  |L1.316|
00013c  b162              CBZ      r2,|L1.344|
00013e  0852              LSRS     r2,r2,#1              ;148
000140  2001              MOVS     r0,#1                 ;148
000142  4090              LSLS     r0,r0,r2              ;148
                  |L1.324|
000144  f05f0200          MOVS.W   r2,#0                 ;152
                  |L1.328|
000148  fbb1f3f0          UDIV     r3,r1,r0              ;152
00014c  4418              ADD      r0,r0,r3              ;152
00014e  0840              LSRS     r0,r0,#1              ;152
000150  1c52              ADDS     r2,r2,#1              ;152
000152  2a04              CMP      r2,#4                 ;152
000154  d3f8              BCC      |L1.328|
000156  4770              BX       lr
                  |L1.344|
000158  2001              MOVS     r0,#1                 ;148
00015a  e7f3              B        |L1.324|
;;;156   
                          ENDP


Poi ho voluto vedere come compila ottimizzando per le prestazioni.
Il compilatore ha deciso di smontare i cicli e tradurli in una serie di operazioni perché ancora conveniente in termini di occupazione di FLASH.
E questo manda a gambe all' aria tutte le disquisizioni su come ottimizzare a livello di sorgente. Ci pensa lui e lo fa molto ma molto bene.
Con buona pace dei "vecchi" programmatori come il sottoscritto
Questo è l' output

Codice: Seleziona tutto

                  uintSqrt PROC
;;;130    // Utilizza il metodo di calcolo della radice babilonese
;;;131    uint32_t uintSqrt(uint32_t n) __pure
0001c4  2800              CMP      r0,#0
;;;132    {
;;;133      uint32_t i,val;
;;;134     
;;;135      // se n vale 0 ritorna 0
;;;136      if (!n) return 0;
;;;137     
;;;138      // calcola il numero di bit di n
;;;139      i = 0;
0001c6  bf1a              ITTE     NE
0001c8  2200              MOVNE    r2,#0
;;;140      val = n;
0001ca  4601              MOVNE    r1,r0
;;;141      do
;;;142      {
;;;143        val = val >> 1;
;;;144        if (val) i++;
;;;145      } while (val);
;;;146     
;;;147      // assume val come 2^(i/2)
;;;148      if (!i) val=1; else val = 1 << (i>>1);
;;;149     
;;;150      // Calcola la radice babilonese.
;;;151      // 4 passaggi sono sufficienti
;;;152      for(i=0; i<4; i++) val = (val + n/val) >> 1;
;;;153     
;;;154      return val;
;;;155    }
0001cc  4770              BXEQ     lr
                  |L1.462|
0001ce  0849              LSRS     r1,r1,#1              ;143
0001d0  bf18              IT       NE                    ;144
0001d2  1c52              ADDNE    r2,r2,#1              ;144
0001d4  d1fb              BNE      |L1.462|
0001d6  2a00              CMP      r2,#0                 ;148
0001d8  bf0f              ITEEE    EQ                    ;148
0001da  2101              MOVEQ    r1,#1                 ;148
0001dc  0851              LSRNE    r1,r2,#1              ;148
0001de  2201              MOVNE    r2,#1                 ;148
0001e0  fa02f101          LSLNE    r1,r2,r1              ;148
0001e4  fbb0f2f1          UDIV     r2,r0,r1              ;152
0001e8  4411              ADD      r1,r1,r2              ;152
0001ea  0849              LSRS     r1,r1,#1              ;152
0001ec  fbb0f2f1          UDIV     r2,r0,r1              ;152
0001f0  4411              ADD      r1,r1,r2              ;152
0001f2  0849              LSRS     r1,r1,#1              ;152
0001f4  fbb0f2f1          UDIV     r2,r0,r1              ;152
0001f8  4411              ADD      r1,r1,r2              ;152
0001fa  0849              LSRS     r1,r1,#1              ;152
0001fc  fbb0f0f1          UDIV     r0,r0,r1              ;152
000200  4408              ADD      r0,r0,r1              ;152
000202  0840              LSRS     r0,r0,#1              ;152
000204  4770              BX       lr
;;;156   
                          ENDP


Inoltre questi esempi dimostrano la (quasi) totale inutilità di programmare in assembler, con buona pace di coloro che lo amano ancora.