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

Question

Я думаю о различных способах реализации арифметики произвольной точности (иногда называемой Bignum, Integer или BigInt).

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

Точнее, кажется, что размер в битах элементов массива часто является вторым по величине поддерживаемым размером (возможно, чтобы сделать вычисления с переполнением проще в реализации?), например, язык / платформа поддерживает 128-битные числа -> массив 64-битных чисел + 128-битная переменная для обработки переполнения.

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

Мой вопрос касается базовой структуры данных, а не алгоритмов операций.Я знаю Карацубу, Тоом-Кука и др.

Answer 1

Можно использовать Китайскую теорему остатка до , представляющую большие целые числа , принципиально отличную от обычной системы base-2 ^ n.

Iполагаю, что основанное на CRT представление все еще будет использовать массив элементов, которые, как и традиционное представление, основаны на наиболее удобной доступной нативной арифметике.Однако эти элементы содержат остатки числа, когда они разделены последовательностью простых чисел, а не цифрами base-2 ^ n.

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

Однако, чтобы ответить на ваш вопрос: я считаю, что правильно сказать, чтоСистема 2 ^ n действительно является «проверенным и верным» представлением, которое используется большинством популярных библиотек bignum.Думаю, я вспоминаю, что существуют существующие библиотеки bignum на основе ЭЛТ, хотя в последнее время я не проверял, существуют ли они до сих пор ...