Stavo leggendo gli Algorithms e ho trovato l'algoritmo di moltiplicazione di Karatsuba e un piccolo wiki ha portato agli algoritmi di Schonhage-Strassen e Furer per la moltiplicazione.
Mi chiedevo quali sono gli algoritmi utilizzati sull'operatore * in C #? Pur moltiplicando una coppia di numeri interi o doppi, utilizza una combinazione di algoritmi con un qualche tipo di strategia basata sulla dimensione dei numeri? Come posso scoprire i dettagli di implementazione per C #?
Come tutti i dettagli dell'implementazione, è specifico dell'implementazione (duh), ma questo è praticamente universale: se la CPU supporta il tipo e l'operazione del numero (i processori ragionevolmente recenti fanno, per i float, i double e gli fixed- interi di larghezza), lo usi. Potrebbero esserci molti livelli intermedi, come un interprete, un compilatore JIT per l'IL o qualcosa di completamente diverso, ma si tratta solo di wrapper e l'operazione effettiva è delegata all'hardware.
Avrai difficoltà a battere una buona implementazione hardware nel software, indipendentemente dalla scelta dell'algoritmo - con una sola eccezione "comune": una FPU lenta può a volte essere battuta sacrificando alcune funzionalità, ma questo è molto ottimizzazione a basso livello. Ma questo non è qualcosa che le implementazioni linguistiche di solito fanno.
Per numeri interi / numeri arbitrari di precisione (come BigInt e BigDecimal ), non è possibile (interamente) fare affidamento sulle operazioni hardware, poiché sono troppo vincolate nella dimensione della parola. In questi casi, gli algoritmi iniziano a essere importanti, ma ancora una volta è specifico per l'implementazione e non posso dare alcuna generalizzazione. Si noti che la base è in genere molto maggiore di 10, per ottenere il massimo dalle operazioni a precisione fissa. So che più di un pacchetto aritmetico di precisione arbitrario altamente utilizzato (in particolare, il tipo long di CPython e PyPy e il pezzo rilevante di Mathematica) utilizzano o almeno considerano l'algoritmo di Karatsuba.
MSIL aka CIL, in cui il codice sorgente C # è digerito, ha codici opcode per tre varianti su "multiply"; "mul", "mul.ovf" e "mul.ovf.un". Questi sono usati per la maggior parte dei tipi di valore incorporati, da byte a doppio. Traducono abbastanza direttamente in comandi nativi simili.
Il primo codice è di uso generale; value1 e value2 vengono inseriti nello stack di valutazione, quindi viene chiamato "mul"; value1 e value2 vengono spuntati, moltiplicati e il risultato viene inviato allo stack di valutazione. Le due varianti sono solo per la moltiplicazione intera e definiscono il comportamento di overflow "controllato"; "mul.ovf" afferma che il valore del risultato firmato si adatta al tipo di risultato determinato senza overflow, mentre "mul.ovf.un" asserisce che il valore senza segno si adatta al tipo di risultato.
Il comando "mul", come la maggior parte degli opcode, produce un risultato di un tipo basato sulle specifiche; le regole di base sono che l'operazione è definita per due input, entrambi devono essere dello stesso tipo e uno dei seguenti: int32, uint32, int64, uint64, float o double. Per la moltiplicazione di tipi diversi, o tipi non presenti nell'elenco come byte, sbyte e short, viene eseguita una conversione di allargamento sul valore della dimensione più piccola o precisione rispetto a quella del più grande (o al minimo). Questo accade praticamente di default per i tipi di interi più piccoli; la CPU non si occuperà di qualcosa di più piccolo di una parola (16 bit), e alcuni non si occuperanno più di meno di una dword contemporaneamente, quindi l'implementazione CLR semplicemente alimenterà i valori più piccoli alla CPU come password.
Giù al livello nativo, ci sono due comandi di base nell'assemblatore 80x86 per eseguire la moltiplicazione sugli stessi tipi di base: "MUL" moltiplicherà ogni due numeri interi (usando word, dword o word64 lengths), mettendo il risultato in una certa lunghezza variante indipendente del registro AXE, mentre FMUL e FMULP eseguono l'operazione equivalente su tipi in virgola mobile utilizzando la FPU del chip, eventualmente facendo scoppiare il risultato fuori dallo stack eval della FPU nel registro AX.
Per quanto riguarda esattamente quale algoritmo binario viene utilizzato per arrivare alla risposta prodotta dai comandi, non dovresti davvero preoccuparti; qualunque cosa venga utilizzata, puoi essere certo che è molto più performante di qualsiasi altra cosa tu possa fare nel codice sorgente gestito.
Ora, per i tipi di struttura più grandi, come Decimal e BigInteger, le operazioni di moltiplicazione native incorporate non esistono e quei tipi do si basano su algoritmi di moltiplicazione. Ecco il codice per BigInteger, implementato in un helper nascosto BigIntegerBuilder: link . Decimal usa una chiamata a FCallMultiply; sfortunatamente questo è un metodo esterno che lega gli MFC quindi non riesco a trovare il codice sorgente.
Leggi altre domande sui tag c# algorithms