Cos'è più efficiente, una singola radice quadrata o più divisioni?

Una radice quadrata non è così lunga da calcolare per le moderne CPU. È meglio calcolare la radice quadrata piuttosto che continuare a eseguire il ciclo fino a n / 2. Tranne forse per n molto piccole.

Ci sono modi per ridurre il costo delle radici quadrate: Precarica la radice quadrata:

int max = (int)Math.sqrt(n);
for(int k=2 ; k <= max ; k++)...

o utilizzare una moltiplicazione intera nel test

for(int k=2 ; k*k <= n ; k++)...

Prima di iniziare,

• Sapere che cos'è il caso d'uso
• Scopri come misurare le prestazioni in modo scientifico, come un professionista. Ci vogliono anni per imparare, ma non ci sono costi ricorrenti che applicano la conoscenza.

In primo luogo, ottimizza per caso d'uso.

• Per un colloquio, usa la libreria standard sqrt , floored to integer, prendi il fattore 2 come caso speciale, in modo da basarti solo su numeri interi dispari che iniziano con 3.
• Per la bellezza assoluta, implementa Setaccio di Eratostene -
  • Ma non cercare di impressionare con un intervistatore con questo (a parte il solo fare un salto di nome) - non vuoi rischiare timeout o errori di battitura proporzionali alla quantità di codice.

Se per qualche motivo si deve implementare root-quadrato su CPU senza supporto nativo,

• La tua libreria standard potrebbe averla; se è così, usalo.
• Altrimenti, le prime due strategie citate spesso sono:
  • Metodo di bisezione, ricerca binaria o bit-indovinando. Funziona 1 bit di stima radice alla volta.
    • Dato r^2 <= floor(n/4) < (r+1)^2 , test (2*r+1)^2 contro n
    • Utilizza l'identità (2*r+1)^2 == (4*r^2 + 4*r + 1)
  • Metodo Newton-Raphson.
  • La scelta dipende dal fatto che la CPU abbia buone prestazioni di divisione o meno.
    • Il metodo di bisezione richiede solo spostamenti di bit rapidi, addizioni, sottrazioni e confronti.
    • Newton-Raphson richiede una divisione (integer o float).
• Se stai sintetizzando l'hardware, puoi utilizzare una ricerca tabella per i 10 bit più alti o giù di lì, quindi continuare con il metodo bisection o Newton-Raphson.

Tutte le informazioni di cui sopra possono essere raccolte cercando su Google, Wikipedia, Stackoverflow e altri siti hobbisti.

• link
• link

Al giorno d'oggi i processori 'godono' di lavorare su numeri float e forniscono supporto per radici quadrate e poteri. Penso che gli Engeeners che hanno implementato il metodo Math.sqrt(n) , si siano presi cura dell'efficienza meglio della moltiplicazione in un ciclo.