Perché la divisione è più costosa della moltiplicazione?

Question

Non sto davvero cercando di ottimizzare nulla, ma ricordo di averlo sentito dai programmatori tutto il tempo, che l'ho preso come una verità. Dopotutto, dovrebbero sapere queste cose.

Ma mi chiedo perché la divisione è effettivamente più lenta della moltiplicazione? La divisione non è solo una sottrazione glorificata e la moltiplicazione è un'aggiunta glorificata? Quindi matematicamente non vedo perché andare in un modo o nell'altro abbia costi computazionalmente molto diversi.

Qualcuno può chiarire il motivo/la causa di ciò, così so, invece di ciò che ho sentito da altri programmatori che ho chiesto prima di quale è: "perché".

Answer 1

CPU ALU (Arithmetic-Logic Unit) esegue algoritmi, sebbene siano implementati nell'hardware. Gli algoritmi di moltiplicazione classica includono Wallace tree e Dadda tree. Ulteriori informazioni sono disponibili here. Tecniche più sofisticate sono disponibili nei nuovi processori. Generalmente, i processori si sforzano di parallelizzare le operazioni di coppie di bit per minimizzare i cicli di clock richiesti. Gli algoritmi di moltiplicazione possono essere parallelizzati in modo abbastanza efficace (sebbene siano necessari più transistor).

Division algorithms non può essere parallelizzato in modo efficiente. Gli algoritmi di divisione più efficienti sono piuttosto complessi (The Pentium FDIV bug dimostra il livello di complessità). Generalmente, richiedono più cicli di clock per bit. Se cerchi ulteriori dettagli tecnici, here è una bella spiegazione di Intel. Intel in realtà patented loro algoritmo di divisione.