java - multiplicar - ¿Los enteros de ancho fijo son distributivos sobre la multiplicación?

tabla de multiplicar del 1 al 10 en netbeans

Question

Para tres enteros con signo de n bits a , b y c (como 32 bits), ¿es siempre cierto que a * (b + c) == (a * b) + (a * c) , teniendo en cuenta ¿desbordamiento de enteros?

Creo que esto es independiente del lenguaje, pero si no lo es, estoy específicamente interesado en la respuesta para Java.

Answer 1

La propiedad distributiva se mantiene para el módulo aritmético; ya que, la aritmética de enteros del complemento de dos bits de longitud fija es aritmética de módulo a homogénea para la misma longitud de bit (sin signo), la propiedad distributiva se mantiene cuando se usa la aritmética de complemento de dos.

Una explicación más detallada se puede encontrar https://math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic .

Answer 2

Para las matemáticas de complemento de 2 en un entero con signo, la pregunta se reduce a:

is (a*(b+c))%(2**32) === (a*b+a*c)%(2**32)

así que para el complemento matemático entero con signo de 2 es siempre cierto.

Para las matemáticas de enteros con signo no complementarias del 2, supongo que depende de cómo se manejen los desbordamientos. Si refleja modulo matematico entonces es verdad.

Answer 3

Sí, esto siempre es cierto .

Es una propiedad que se mantiene porque usted está haciendo efectivamente el módulo aritmético 2 ^ 32. El hecho de que los int Java estén firmados complica un poco las cosas (y significa que no puede asumir que está haciendo el equivalente de aritmética de módulo en general), pero no afecta esta propiedad distributiva en particular.

Un experimento mental consiste en considerar su implementación utilizando una suma repetida , y considerar qué sucede cuando se desborda. Dado que el orden de hacer adiciones no afecta el resultado con int s (incluso con desbordamientos), tampoco lo hace las multiplicaciones como adiciones repetidas en un orden diferente. Y dado que la multiplicación int es siempre equivalente a una suma repetida, los resultados también deben ser los mismos para la multiplicación reordenada. QED

Answer 4

Sí, se mantiene en Java, incluso en el caso de desbordamiento. (Ciertos otros idiomas no especifican el comportamiento de desbordamiento, en cuyo caso no se ofrecen garantías).

Answer 5

Sí, se sostiene, porque la aritmética de enteros es aritmética de módulo sobre anillos finitos.

Puede ver una discusión teórica aquí: https://math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic