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

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

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

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

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

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

Ответ 1

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

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

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

Однако, чтобы ответить на ваш вопрос: я считаю, что точно сказать, что система base-2 ^ n действительно является "проверенным и истинным" представлением, которое используется большинством популярных библиотек bignum. Я думаю, что я помню, что существуют существующие библиотеки на основе CRT на основе CRT, хотя в последнее время я не проверял, все ли они вокруг.