Dovrei usare la moltiplicazione o la divisione?

Ecco una domanda divertente stupida:

Diciamo che dobbiamo eseguire una semplice operazione in cui abbiamo bisogno della metà del valore di una variabile. Ci sono in genere due modi per farlo:

y = x / 2.0; // or... y = x * 0.5; 

Supponendo che stiamo usando gli operatori standard forniti con la lingua, quale ha prestazioni migliori?

Immagino che la moltiplicazione sia in genere migliore, quindi cerco di attenermi a ciò quando eseguo il codice, ma vorrei confermarlo.

Anche se personalmente sono interessato alla risposta per Python 2.4-2.5, sentitevi liberi di pubblicare anche una risposta per altre lingue! E se lo desideri, sentiti libero di pubblicare altri modi fantasiosi (come utilizzare gli operatori di spostamento bit a bit).

Pitone:

 time python -c 'for i in xrange(int(1e8)): t=12341234234.234 / 2.0' real 0m26.676s user 0m25.154s sys 0m0.076s time python -c 'for i in xrange(int(1e8)): t=12341234234.234 * 0.5' real 0m17.932s user 0m16.481s sys 0m0.048s 

la moltiplicazione è del 33% più veloce

Lua:

 time lua -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end' real 0m7.956s user 0m7.332s sys 0m0.032s time lua -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end' real 0m7.997s user 0m7.516s sys 0m0.036s 

=> nessuna vera differenza

LuaJIT:

 time luajit -O -e 'for i=1,1e8 do t=12341234234.234 / 2.0 end' real 0m1.921s user 0m1.668s sys 0m0.004s time luajit -O -e 'for i=1,1e8 do t=12341234234.234 * 0.5 end' real 0m1.843s user 0m1.676s sys 0m0.000s 

=> è solo il 5% più veloce

conclusioni: in Python è più veloce moltiplicare che dividere, ma man mano che ci si avvicina alla CPU usando VM o JIT più avanzati, il vantaggio scompare. È abbastanza probabile che una futura macchina virtuale Python lo renderebbe irrilevante

Usa sempre ciò che è più chiaro. Qualsiasi altra cosa tu faccia sta cercando di superare in astuzia il compilatore. Se il compilatore è del tutto intelligente, farà del suo meglio per ottimizzare il risultato, ma nulla può far sì che il prossimo non ti odierà per la tua paccheta soluzione bithifting (adoro la manipolazione dei bit a proposito, è divertente.) Ma divertente! = Leggibile )

L’ottimizzazione prematura è la radice di tutto il male. Ricorda sempre le tre regole di ottimizzazione!

  1. Non ottimizzare.
  2. Se sei un esperto, vedi la regola n
  3. Se sei un esperto e puoi giustificare la necessità, usa la seguente procedura:

    • Codice non ottimizzato
    • determinare quanto velocemente è “abbastanza veloce” – Nota quale requisito / storia utente richiede quella metrica.
    • Scrivi un test di velocità
    • Prova il codice esistente – Se è abbastanza veloce, hai finito.
    • Ricodifica ottimizzata
    • Prova codice ottimizzato. Se non soddisfa la metrica, buttala via e mantieni l’originale.
    • Se incontra il test, mantieni il codice originale come commenti

Inoltre, fare cose come rimuovere i loop interni quando non sono richiesti o scegliere un elenco collegato su un array per un ordinamento di inserimento non sono ottimizzazioni, ma solo programmazione.

Penso che questo diventi così pignolo da farti fare meglio a rendere il codice più leggibile. Se non esegui le operazioni a migliaia, se non milioni, di volte, dubito che nessuno noterà mai la differenza.

Se davvero devi fare la scelta, il benchmarking è l’unica strada da percorrere. Trova quali sono le funzioni che ti danno problemi, quindi scopri in che punto della funzione si verificano i problemi e fissa quelle sezioni. Tuttavia, dubito ancora che una singola operazione matematica (anche una ripetuta molte, molte volte) sarebbe una causa di qualsiasi collo di bottiglia.

La moltiplicazione è più veloce, la divisione è più accurata. Perderai un po ‘di precisione se il tuo numero non è una potenza di 2:

 y = x / 3.0; y = x * 0.333333; // how many 3's should there be, and how will the compiler round? 

Anche se si lascia che il compilatore calcoli la costante invertita con precisione perfetta, la risposta può ancora essere diversa.

 x = 100.0; x / 3.0 == x * (1.0/3.0) // is false in the test I just performsd 

È probabile che il problema di velocità sia importante in linguaggio C / C ++ o JIT e anche in questo caso solo se l’operazione si trova in un ciclo a collo di bottiglia.

Se vuoi ottimizzare il tuo codice ma essere ancora chiaro, prova questo:

 y = x * (1.0 / 2.0); 

Il compilatore dovrebbe essere in grado di fare la divisione al momento della compilazione, in modo da ottenere un multiplo in fase di esecuzione. Mi aspetto che la precisione sia la stessa del caso y = x / 2.0 .

Dove questo può essere importante, un LOT si trova in processori embedded dove è richiesta l’emulazione in virgola mobile per calcolare l’aritmetica in virgola mobile.

Sto solo aggiungendo qualcosa per l’opzione “altre lingue”.
C: Poiché questo è solo un esercizio accademico che non fa alcuna differenza, ho pensato di contribuire con qualcosa di diverso.

Ho compilato l’assembly senza ottimizzazioni e ho esaminato il risultato.
Il codice:

 int main() { volatile int a; volatile int b; asm("## 5/2\n"); a = 5; a = a / 2; asm("## 5*0.5"); b = 5; b = b * 0.5; asm("## done"); return a + b; } 

compilato con gcc tdiv.c -O1 -o tdiv.s -S

la divisione per 2:

 movl $5, -4(%ebp) movl -4(%ebp), %eax movl %eax, %edx shrl $31, %edx addl %edx, %eax sarl %eax movl %eax, -4(%ebp) 

e la moltiplicazione per 0,5:

 movl $5, -8(%ebp) movl -8(%ebp), %eax pushl %eax fildl (%esp) leal 4(%esp), %esp fmuls LC0 fnstcw -10(%ebp) movzwl -10(%ebp), %eax orw $3072, %ax movw %ax, -12(%ebp) fldcw -12(%ebp) fistpl -16(%ebp) fldcw -10(%ebp) movl -16(%ebp), %eax movl %eax, -8(%ebp) 

Tuttavia, quando ho cambiato quelle int s per double s (che è ciò che probabilmente Python farebbe), ho ottenuto questo:

divisione:

 flds LC0 fstl -8(%ebp) fldl -8(%ebp) flds LC1 fmul %st, %st(1) fxch %st(1) fstpl -8(%ebp) fxch %st(1) 

moltiplicazione:

 fstpl -16(%ebp) fldl -16(%ebp) fmulp %st, %st(1) fstpl -16(%ebp) 

Non ho benchmarkato alcuno di questo codice, ma solo esaminando il codice puoi vedere che usando gli interi, la divisione per 2 è più breve della moltiplicazione per 2. Usando il doppio, la moltiplicazione è più breve perché il compilatore usa gli opcode in virgola mobile del processore, che probabilmente corri più veloce (ma in realtà non lo so) piuttosto che non usarli per la stessa operazione. Quindi, in definitiva, questa risposta ha dimostrato che le prestazioni della multiplazione di 0,5 rispetto alla divisione di 2 dipendono dall’implementazione del linguaggio e dalla piattaforma su cui gira. In definitiva, la differenza è trascurabile ed è qualcosa di cui non dovresti mai preoccuparti mai, tranne in termini di leggibilità.

Come nota a margine, puoi vedere che nel mio programma main() restituisce a + b . Quando togli la parola chiave volatile, non indovinerai mai a cosa assomigli l’assemblaggio (esclusa la configurazione del programma):

 ## 5/2 ## 5*0.5 ## done movl $5, %eax leave ret 

ha fatto sia la divisione, la moltiplicazione e l’aggiunta in un’unica istruzione! Chiaramente non devi preoccuparti di questo se l’ottimizzatore è di qualche tipo rispettabile.

Ci scusiamo per la risposta troppo lunga.

Scrivi quale è più chiaramente dichiara il tuo intento.

Dopo che il tuo programma ha funzionato, scopri cosa è lento e fallo più velocemente.

Non farlo al contrario.

Fai tutto ciò che ti serve. Pensa innanzitutto al tuo lettore, non preoccuparti delle prestazioni finché non sei sicuro di avere un problema di prestazioni.

Lascia che il compilatore esegua le tue prestazioni.

Innanzitutto, a meno che tu non stia lavorando in C o ASSEMBLY, probabilmente sei in un linguaggio di livello superiore in cui la memoria si blocca e le spese generali di chiamata superano assolutamente la differenza tra moltiplicare e dividere fino al punto di irrilevanza. Quindi, scegli ciò che legge meglio in quel caso.

Se stai parlando da un livello molto alto, non sarà più lento in modo misurabile per qualsiasi cosa tu possa usarlo. Vedrai in altre risposte che le persone devono fare un milione di moltiplicazioni / divisioni solo per misurare una differenza di alcuni millisecondi tra i due.

Se sei ancora curioso, da un punto di vista dell’ottimizzazione di basso livello:

Dividere tende ad avere una pipeline significativamente più lunga di quella moltiplicata. Ciò significa che è necessario più tempo per ottenere il risultato, ma se si riesce a mantenere il processore occupato con attività non dipendenti, non si finisce per costare più di un multiplo.

Quanto è lunga la differenza della pipeline dipende completamente dall’hardware. L’ultimo hardware che ho usato era qualcosa come 9 cicli per un FPU moltiplicato e 50 cicli per una divisione FPU. Sembra molto, ma poi perdi 1000 cicli per una mancanza di memoria, in modo che possa mettere le cose in prospettiva.

Un’analogia sta mettendo una torta in un forno a microonde mentre guardi uno show televisivo. Il tempo totale che ti ha portato via dal programma televisivo è quanto tempo è passato per metterlo nel microonde e portarlo fuori dal microonde. Per il resto del tuo tempo hai continuato a guardare lo show televisivo. Quindi, se la torta impiegava 10 minuti per cucinare invece di 1 minuto, in realtà non consumava più tempo per guardare la TV.

In pratica, se si arriva al livello di attenzione alla differenza tra Multiply e Divide, è necessario comprendere pipeline, cache, stalli di filiali, previsione out-of-order e dipendenze della pipeline. Se questo non suona come se avessi intenzione di andare con questa domanda, allora la risposta corretta è ignorare la differenza tra i due.

Molti (molti) anni fa era assolutamente fondamentale evitare le divisioni e usare sempre i multipli, ma a quel tempo i colpi di memoria erano meno rilevanti e le divisioni erano molto peggiori. In questi giorni valuto la leggibilità più in alto, ma se non c’è differenza di leggibilità, penso che sia una buona abitudine optare per i multipli.

Se stai lavorando con numeri interi o non in virgola mobile, non dimenticare gli operatori di bitshifting: << >>

  int y = 10; y = y >> 1; Console.WriteLine("value halved: " + y); y = y << 1; Console.WriteLine("now value doubled: " + y); 

La moltiplicazione è solitamente più veloce, certamente mai più lenta. Tuttavia, se non è critico per la velocità, scrivi quello che è più chiaro.

In realtà c’è una buona ragione per cui una moltiplicazione della regola generale sarà più veloce della divisione. La divisione in virgola mobile nell’hardware è fatta sia con algoritmi di sottrazione shift e condizionale (“long division” con numeri binari) o – più probabilmente in questi giorni – con iterazioni come l’ algoritmo di Goldschmidt . Spostamento e sottrazione richiede almeno un ciclo per bit di precisione (le iterazioni sono quasi impossibili da parallelizzare come lo spostamento e l’aggiunta della moltiplicazione) e gli algoritmi iterativi eseguono almeno una moltiplicazione per iterazione . In entrambi i casi, è molto probabile che la divisione richiederà più cicli. Ovviamente questo non tiene conto di stranezze nei compilatori, nello spostamento dei dati o nella precisione. In generale, però, se si sta codificando un loop interno in una parte sensibile al tempo di un programma, scrivere 0.5 * x o 1.0/2.0 * x piuttosto che x / 2.0 è una cosa ragionevole da fare. La pedanteria del “codice più chiaro” è assolutamente vera, ma tutti e tre sono così vicini nella leggibilità che la pedanteria è in questo caso semplicemente pedante.

La divisione in virgola mobile è (generalmente) particolarmente lenta, quindi mentre la moltiplicazione in virgola mobile è anche relativamente lenta, è probabilmente più veloce della divisione in virgola mobile.

Ma sono più propenso a rispondere “non ha molta importanza”, a meno che la profilazione non abbia dimostrato che la divisione è un po ‘il collo di bottiglia e la moltiplicazione. Suppongo, tuttavia, che la scelta della moltiplicazione rispetto alla divisione non abbia un grande impatto sulle prestazioni nella tua applicazione.

Questo diventa più una domanda quando si programma in assembly o forse C. Penso che con la maggior parte dei linguaggi moderni si stia facendo un’ottimizzazione come questa per me.

Fai attenzione a “supporre che la moltiplicazione sia in genere migliore, quindi cerco di attenermi a ciò quando eseguo il codice”

Nel contesto di questa domanda specifica, meglio qui significa “più veloce”. Che non è molto utile

Pensare alla velocità può essere un grave errore. Vi sono profonde implicazioni di errore nella specifica forma algebrica del calcolo.

Vedi aritmetica in virgola mobile con analisi degli errori . Vedi Problemi di base in aritmetica in virgola mobile e analisi degli errori .

Mentre alcuni valori in virgola mobile sono esatti, la maggior parte dei valori in virgola mobile è un’approssimazione; sono un valore ideale più un errore. Ogni operazione si applica al valore ideale e al valore dell’errore.

I maggiori problemi derivano dal tentativo di manipolare due numeri quasi uguali. I bit più a destra (i bit di errore) arrivano a dominare i risultati.

 >>> for i in range(7): ... a=1/(10.0**i) ... b=(1/10.0)**i ... print i, a, b, ab ... 0 1.0 1.0 0.0 1 0.1 0.1 0.0 2 0.01 0.01 -1.73472347598e-18 3 0.001 0.001 -2.16840434497e-19 4 0.0001 0.0001 -1.35525271561e-20 5 1e-05 1e-05 -1.69406589451e-21 6 1e-06 1e-06 -4.23516473627e-22 

In questo esempio, è ansible vedere che quando i valori si riducono, la differenza tra numeri quasi uguali genera risultati diversi da zero in cui la risposta corretta è zero.

Ho sempre imparato che la moltiplicazione è più efficiente.

Ho letto da qualche parte che la moltiplicazione è più efficiente in C / C ++; Nessuna idea riguardo le lingue interpretate – la differenza è probabilmente trascurabile a causa di tutte le altre spese generali.

A meno che non diventi un problema con ciò che è più mantenibile / leggibile – lo odio quando la gente mi dice questo, ma è così vero.

Suggerirei la moltiplicazione in generale, perché non devi passare i cicli assicurando che il tuo divisore non sia 0. Questo non si applica, ovviamente, se il tuo divisore è una costante.

Android Java, profilato su Samsung GT-S5830

 public void Mutiplication() { float a = 1.0f; for(int i=0; i<1000000; i++) { a *= 0.5f; } } public void Division() { float a = 1.0f; for(int i=0; i<1000000; i++) { a /= 2.0f; } } 

Risultati?

 Multiplications(): time/call: 1524.375 ms Division(): time/call: 1220.003 ms 

La divisione è circa il 20% più veloce della moltiplicazione (!)

Come per i post 24 (la moltiplicazione è più veloce) e # 30 – ma a volte sono entrambi altrettanto facili da capire:

 1*1e-6F; 1/1e6F; 

~ Trovo che entrambi siano altrettanto facili da leggere e devono ripeterli miliardi di volte. Quindi è utile sapere che la moltiplicazione è di solito più veloce.

C’è una differenza, ma dipende dal compilatore. All’inizio su vs2003 (c ++) non ho ottenuto alcuna differenza significativa per i doppi tipi (virgola mobile a 64 bit). Tuttavia, eseguendo di nuovo i test su vs2010, ho rilevato un’enorme differenza, fino al fattore 4 più veloce per le moltiplicazioni. Rintracciandolo, sembra che vs2003 e vs2010 generino codice fpu differente.

Su un Pentium 4, 2,8 GHz, vs2003:

  • Moltiplicazione: 8.09
  • Divisione: 7,97

Su un Xeon W3530, vs2003:

  • Moltiplicazione: 4.68
  • Divisione: 4.64

Su un Xeon W3530, vs2010:

  • Moltiplicazione: 5.33
  • Divisione: 21.05

Sembra che su vs2003 una divisione in un ciclo (quindi il divisore sia stato usato più volte) sia stata tradotta in una moltiplicazione con l’inverso. Su vs2010 questa ottimizzazione non è più applicata (suppongo perché c’è un risultato leggermente diverso tra i due metodi). Si noti inoltre che la CPU esegue le divisioni più rapidamente non appena il numeratore è 0.0. Non conosco l’algoritmo preciso cablato nel chip, ma forse dipende dal numero.

Modifica 18-03-2013: l’osservazione per vs2010

Bene, se supponiamo che un’operazione di addizione / sottotraccia costi 1, moltiplica i costi 5 e divide i costi circa 20.

Dopo una discussione tanto lunga e interessante, ecco la mia opinione su questo: non c’è una risposta definitiva a questa domanda. Come alcuni hanno sottolineato, dipende da entrambi, l’hardware (cf piotrk e gast128 ) e il compilatore (cfr . I test di @Javier ). Se la velocità non è critica, se la tua applicazione non ha bisogno di elaborare in tempo reale un’enorme quantità di dati, puoi optare per chiarezza usando una divisione, mentre se la velocità di elaborazione o il carico del processore sono un problema, la moltiplicazione potrebbe essere la più sicura. Infine, a meno che tu non sappia esattamente su quale piattaforma verrà implementata la tua applicazione, il benchmark non ha senso. E per chiarezza del codice, un solo commento farebbe il lavoro!

Ecco una divertente risposta:

x / 2.0 non è equivalente a x * 0.5

Diciamo che hai scritto questo metodo il 22 ottobre 2008.

 double half(double x) => x / 2.0; 

Ora, 10 anni dopo impari che puoi ottimizzare questo pezzo di codice. Il metodo è referenziato in centinaia di formule in tutta la tua applicazione. Così lo cambi, e sperimenta un notevole miglioramento delle prestazioni del 5%.

 double half(double x) => x * 0.5; 

E ‘stata la decisione giusta per cambiare il codice? In matematica, le due espressioni sono davvero equivalenti. Nell’informatica, questo non sempre è vero. Si prega di leggere Minimizzare l’effetto dei problemi di accuratezza per maggiori dettagli. Se i tuoi valori calcolati sono – ad un certo punto – rispetto ad altri valori, cambierai il risultato dei casi limite. Per esempio:

 double quantize(double x) { if (half(x) > threshold)) return 1; else return -1; } 

La linea di fondo è; una volta che ti sarai accontentato di uno dei due, seguitelo!

Tecnicamente non esiste una divisione, c’è solo moltiplicazione per elementi inversi. Ad esempio Non dividi mai per 2, in effetti moltiplica per 0,5.

‘Divisione’ – pensiamoci che esiste per un secondo – è sempre più difficile quella moltiplicazione perché per ‘dividere’ x per y si deve prima calcolare il valore y^{-1} tale che y*y^{-1} = 1 e poi fai la moltiplicazione x*y^{-1} . Se già conosci y^{-1} allora il calcolo da y deve essere un’ottimizzazione.