Per tre interi con segno n bit a, e c (ad esempio 32 bit), è sempre vero che a * (b + c) == (a * b) + (a * c), tenendo conto dell'overflow di numeri interi?I numeri interi a larghezza fissa sono distribuiti sulla moltiplicazione?
Penso che questo sia indipendente dalla lingua, ma se non lo è, sono specificamente interessato alla risposta per Java.
Sì, contiene perché l'aritmetica dei numeri interi è modulo aritmetico su anelli finiti.
Potete vedere alcuni discussione teorica qui: https://math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic
Sì, questo è sempre vero.
È una proprietà che viene trattenuta perché si sta effettivamente eseguendo il modulo aritmetico 2^32. Il fatto che Java int sia firmato complica leggermente le cose (e significa che non si può presumere che si stia facendo l'equivalente dell'aritmetica dei moduli in generale), ma non influisce su questa particolare proprietà distributiva.
Un esperimento di pensiero consiste nel prendere in considerazione l'implementazione utilizzando aggiunta ripetuta e considerare cosa succede quando viene espulso. Poiché l'ordine delle aggiunte non influisce sul risultato con int s (anche con overflow), quindi non fa le moltiplicazioni come aggiunte ripetute in un ordine diverso. E dal momento che il moltiplicare int equivale sempre a un'aggiunta ripetuta, i risultati devono essere uguali anche per la moltiplicazione riordinata. Come volevasi dimostrare
Sì, è contenuto in Java, incluso nel caso di overflow. (Alcune altre lingue non specificano il comportamento di overflow, nel qual caso non vengono fornite garanzie.)
Potete fornire anche una fonte o una spiegazione? – phant0m
La proprietà distributiva vale per l'aritmetica modulo; poiché, l'aritmetica dei numeri interi a complemento della lunghezza di bit fissa è homomorphic per l'aritmetica modulo per la stessa lunghezza di bit (senza segno), la proprietà distributiva vale quando si utilizza l'aritmetica del complemento a due.
Una spiegazione più dettagliata può essere trovata here.
Per 2 di matematica complemento sulla integer firmato la domanda si riduce a:
is (a*(b+c))%(2**32) === (a*b+a*c)%(2**32)
così per 2 complemento firmato numeri in virgola fissa è sempre vero.
Per complemento matematico di interi non firmati da 2, suppongo che dipenda da come vengono gestiti gli overflow. Se riflette modulo matematico, allora è vero.
+1 L'utilizzo di underflow e overflow è raramente utile, e anche quando lo è, confonde la maggior parte delle persone. Se ti affidi a questo comportamento, dovresti documentarlo in dettaglio. –
concordato. In questo caso, sto facendo l'ottimizzazione del compilatore delle espressioni aritmetiche e devo fare attenzione a non cambiare la semantica. – Taymon