Почему реализации BigInteger используют величину знака вместо дополнения до двух?

Question

Знаковые целые числа с произвольной точностью почти всегда реализуются с использованием представления величины знака:

• (Java) BigInteger в OpenJDK
• (Python) Bigint реализация встроенного типа Python int в CPython
• (C) mpz_t в GMP, арифметическая библиотека GNU с множественной точностью
• (C ++) BigInteger в библиотеке bigint. Автор Matt McCutchen
• (Rust) BigInt в библиотеке num-bigint

Четкое предпочтение величины знака отличается от почти универсального предпочтения дополнения до двух в целочисленных типах со знаком фиксированной ширины. Вопрос в том, почему величина знака так явно предпочтительна для BigIntegers? (Я приветствую контрпримеры, если вы не согласны с предпосылкой.)

Обратите внимание, что API BigInteger обычно определяют семантику "как если бы два дополняют" (например, Java , Python ) для побитовых операций, где это важно. Это обеспечивает соответствие с обычным значением этих операций. Это не диктует фактическое внутреннее представление (просто детали реализации), но это должно быть точкой в ​​пользу использования внутреннего дополнения до двух, если все остальные были равны.

Числа с плавающей точкой используют величину знака, в отличие от целых чисел, которые используют дополнение до двух. Тем не менее, с плавающей точкой на самом деле это не является прецедентом, поскольку поведение и алгоритмы арифметики с плавающей точкой существенно отличаются от целочисленной арифметики. Бигнум гораздо больше похож на целые, чем на поплавки.

Мы знаем «учебник» о причинах того, почему дополнение к двум математически работает и почему оно имеет преимущества. Мне кажется, что эти причины в равной степени применимы как к int, так и к BigIntegers. Насколько это действительно так?

Существует, конечно, огромная разница между конструктивными ограничениями аппаратных целых чисел с фиксированной точностью и программными целыми числами произвольной точности. В этом смысле неудивительно, что дизайнеры сделали разные компромиссы в этих разных областях. Каковы же тогда компромиссы между величиной знака и дополнением к двум применительно к целым числам произвольной точности? Например, это может быть связано с производительностью или простотой некоторых важных алгоритмов.

Я надеюсь, что ваш ответ осветит конструктивные соображения, которые входят в арифметику BigInteger, а также поможет мне пересмотреть то, что я знаю о дополнении двух с новой точки зрения.

(Для ясности: когда я говорю, что два дополняют два для целых чисел произвольной точности, я имею в виду представление, использующее массив слов, чей битовый образец, если сложить, является представлением дополнения двух к желаемому числу - возможно, с дополнительным требованием, чтобы не было «ненужных начальных 0» (для неотрицательных чисел) или «ненужных ведущих 1» (для отрицательных чисел).)

Answer 1

Поскольку я строю несколько своих bignum библиотек, я согласен с ответом rcgldr (+1), дополняющим два, возникают проблемы в более высоких операциях, а не только *,/.

Вдобавок ко всему этому некоторые библиотеки bignum не используют мощность 2 в качестве базы, и использование дополнения до двух также является хитрым. Причина неиспользования мощности 2 заключается в том, что мы вычисляем на базе 10, поэтому мы ожидаем ввода и результата в таком виде. Преобразование между основанием 2 (или степенью 2) и основанием 10 является задачей IIRC ~O(n^2), и для действительно больших чисел обычно стоит больше, чем операция, выполняемая над ними. Таким образом, библиотеки используют самую большую мощность 10, которая подходит к используемому слову ALU ... например, в 32 битах это 1 000 000 000 Это делает небольшую трату пространства, но упрощает преобразования ввода и вывода между числовыми и строковыми представлениями до O(n). Где n - количество использованных цифр или слов ...

Кроме того, два дополнения усложняют арифметику по модулю, необходимую для многих подстилающих операций, таких как умножение на NTT

Обработка и восстановление двух дополнений займет O(n), в то время как отдельный знак просто O(1), что, я думаю, является основной причиной этого.

Answer 2

Дополнение Two упрощает сложение и вычитание для чисел одинаковой длины, но усложняет умножение и деление. Для аппаратной реализации может быть штраф времени, но не всегда. Если посмотреть на таблицу инструкций X86 «Ivy Bridge», то единственный случай, когда дополнение до двух занимает больше времени, - это 128-разрядное знаковое деление, деленное на 64-разрядное знаковое делитель. Так что это в основном проблема для математики на основе программного обеспечения.

Большие целочисленные библиотеки могут использовать более сложные, но более быстрые представления для больших чисел. Вот несколько ссылок на примеры статей:

https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic

https://cp -algorithms.com / алгебра / большой integer.html

http://www.apfloat.org/ntt.html

Более сложные методы в большинстве случаев быстрее для довольно больших чисел, для чисел среднего размера более простые реализации будут быстрее.