Являются ли целые числа фиксированной ширины дистрибутивными по умножению?

Question

Для трех n-битных целых чисел со знаком a, b, а также c (например, 32-разрядный), всегда ли это правда, что a * (b + c) == (a * b) + (a * c)с учетом целочисленного переполнения?

Я думаю, что это не зависит от языка, но если это не так, меня особенно интересует ответ для Java.

Answer 1

Да, это так, потому что целочисленная арифметика является модульной арифметикой над конечными кольцами.

Вы можете увидеть некоторые теоретические обсуждения здесь: https://math.stackexchange.com/questions/27336/associativity-commutativity-and-distributivity-of-modulo-arithmetic

Answer 2

Да, это всегда так.

Это свойство имеет место, потому что вы эффективно выполняете арифметику по модулю 2^32. Тот факт, что Java ints подписаны, что немного усложняет (и означает, что вы не можете предполагать, что вы делаете эквивалент по модулю арифметики в целом), но не влияет на это конкретное свойство распределения.

Мысленный эксперимент состоит в том, чтобы рассмотреть возможность его реализации с использованием многократного сложения и рассмотреть, что произойдет, если он переполнится. Поскольку порядок выполнения дополнений не влияет на результат с ints (даже с переполнением), то ни один не делает умножения как повторяющиеся сложения в другом порядке. И с тех пор int умножение всегда эквивалентно повторному сложению, результаты также должны быть одинаковыми для переупорядоченного умножения. QED

Answer 3

Распределительное свойство верно для арифметики по модулю; поскольку целочисленная арифметика с дополнительным битом длины два гомоморфна арифметике по модулю для той же длины (без знака), свойство распределения сохраняется при использовании арифметики с дополнением до двух.

Более подробное объяснение можно найти здесь.

Answer 4

Да, это действительно в Java, в том числе и в случае переполнения. (Некоторые другие языки не определяют поведение переполнения, в этом случае никаких гарантий не делается.)

Answer 5

Для математики дополнения 2 к целому числу со знаком вопрос сводится к:

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

так что для дополнения 2 со знаком целочисленная математика это всегда верно.

Для математики целых чисел, не являющейся дополнением к 2, я думаю, это зависит от того, как обрабатываются переполнения. Если это отражает модулю математики, тогда это правда.